1，首先总结一下线性表（分为顺序表和链接表，【即顺序存储结构和链式存储结构的区别】）和栈（顺序栈和链接栈）还有队列（顺序队列和链接队列）的Java类库中的实现：
java.util.ArrayList 实现了顺序表，java.util.LinkedList 实现了链接表的功能。
java.util.ArrayDeque实现了顺序栈和顺序队列（该类中即定义了与栈操作有关的方法，也定义了与队列操作有关的方法）、java.util.LinkedList实现了链接栈和链接队列。
2，定义了一个Stack<E>接口，指明该栈实现了哪些具体的操作。接口如下：
public interface Stack<E> {
public int length();//返回栈的长度
public E pop();//出栈
public void push(E element);//进栈
public E peek();//访问栈顶元素
public boolean empty();//判断栈是否为空
public void clear();//清空栈
}
3，在JAVA类库中，java.util.ArrayDeque类实现了顺序栈的功能。ArrayDeque可以实现动态地扩展栈的大小，但是不支持多线程访问。同时，ArrayDeque还实现了顺序队列的功能。
4，定义了一个Object[] 类型的数组，用来保存顺序栈中的元素。具体实现类SequenceStack.java 如下：
import java.util.Arrays;
public class SequenceStack<E> implements Stack<E> {
private int DEFAULT_SIZE = 16;//定义栈的初始默认长度
private int capacity;//保存顺序栈的长度
private int size;//保存顺序栈中元素的个数
private Object[] elementData;//定义一个数组用于保存顺序栈中的元素
public SequenceStack() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//以指定的大小来创建栈
public SequenceStack(int initSize){
capacity = 1;
while(capacity < initSize)
capacity <<= 1;//将capacity设置成大于initSize的最小2次方
elementData = new Object[capacity];
}
//返回当前顺序栈中元素的个数
public int length() {
return size;
}
public E pop() {
if(empty())
throw new IndexOutOfBoundsException("栈空，不能出栈");
E oldValue = (E)elementData[size - 1];
elementData[--size] = null;//让垃圾回收器及时回收，避免内存泄露
return oldValue;
}
public void push(E element) {
ensureCapacity(size + 1);
elementData[size++] = element;
}
private void ensureCapacity(int minCapacity){
if(minCapacity > capacity){
while(capacity < minCapacity)
capacity <<= 1;
elementData = Arrays.copyOf(elementData, capacity);
}
}
//获取栈顶元素，不会将栈顶元素删除
public E peek() {
if(size == 0)
throw new ArrayIndexOutOfBoundsException("栈为空");
return (E)elementData[size - 1];
}
public boolean empty() {
return size == 0;
}
public void clear() {
// Arrays.fill(elementData, null);
for(int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
public String toString(){
if(size == 0)
return "[]";
else{
StringBuilder sb = new StringBuilder("[");
for(int i = size - 1; i >= 0; i--)
sb.append(elementData[i].toString() + ", ");
int len = sb.length();
//删除由于上面for循环中最后添加的多余的两个字符 (一个是逗号，一个是空格符号)
return sb.delete(len - 2, len).append("]").toString();
}
}
}