1，首先总结一下线性表（分为顺序表和链接表，【即顺序存储结构和链式存储结构的区别】）和栈（顺序栈和链接栈）还有队列（顺序队列和链接队列）的JAVA类库中的实现：

java.util.ArrayList 实现了顺序表，java.util.LinkedList 实现了链接表的功能。

java.util.ArrayDeque实现了顺序栈和顺序队列（该类中即定义了与栈操作有关的方法，也定义了与队列操作有关的方法）、java.util.LinkedList实现了链接栈和链接队列。

2，定义了一个Stack接口，指明该栈实现了哪些具体的操作。接口如下：

public interface Stack {
? ? 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 implements Stack {
? ?
? ? 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();
? ? ? ? }
? ? }
}