1.1. 栈的顺序存储和链式存储

栈和队列是两种重要的数据结构。从栈与队列的逻辑结构上来说，它们也是线性结构，

与线性表不同的是它们所支持的基本操作是受到限制的，它们是操作受限的线性表，是一种

限定性的数据结构。

栈（stack ）又称堆栈，它是运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为 栈顶（top） ），栈顶保存的元素称为 栈顶元素。相对的，表的另一端称为栈底（栈底（bottom） 。

Stack接口public interface Stack {    //返回堆栈的大小    public int getSize();    //判断堆栈是否为空    public boolean isEmpty();    //数据元素 e 入栈    public void push(Object e);    //栈顶元素出栈    public Object pop() throws StackEmptyException;    //取栈顶元素    public Object peek() throws StackEmptyException;}

顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈

中的数据元素。由于堆栈是一种特殊的线性表，因此在线性表的顺序存储结构的基础上，选

择线性表的一端作为栈顶即可。根据数组操作的特性，选择数组下标大的一端，即线性表顺

序存储的表尾来作为栈顶，此时入栈、出栈等操作可以在Ο(1)时间完成。

由于堆栈的操作都在栈顶完成，因此在顺序栈的实现中需要附设一个指针 top 来动态的

指示栈顶元素在数组中的位置。通常 top 可以用栈顶元素所在数组下标来表示，top= -1 时表

示空栈。

　　堆栈在使用过程中所需的最大空间很难估计，因此，一般来说在构造堆栈时不应设定堆

栈的最大容量。一种合理的做法和线性表的实现类似，先为堆栈分配一个基本容量，然后在

实际的使用过程中，当堆栈的空间不够时再倍增存储空间，这个过程所需的时间均摊到每个

数据元素时间为Θ(1)，不会影响操作实现的时间复杂度

public class StackArray implements Stack {    private final int LEN = 8;    //数组默认大小    private Object[] elements;  //数据元素数组    private int top;            //栈顶指针    public StackArray() {        top = -1;        elements = new Object[LEN];    }     //返回堆栈大小    @Override    public int getSize() {        return top + 1;    }    //判断堆栈是否为空    @Override    public boolean isEmpty() {        return top < 0;    }     /**     *对元素入栈     */    @Override    public void push(Object e) {        if (getSize()>=elements.length){            expandSpace();            elements[++top]=e;        }    }     private void expandSpace() {        Object[] a = new Object[elements.length*2];        for (int i=0; i<elements.length; i++)            a[i] = elements[i];        elements = a;    }    /**     *栈顶元素出栈     */    @Override    public Object pop() throws StackEmptyException {        if (getSize()<1){            throw new StackEmptyException("错误，堆栈为空");        }        Object obj = elements[top];        elements[top--]=null;        return obj;    }    @Override    public Object peek() throws StackEmptyException {        if (getSize()<1)            throw new StackEmptyException("错误，堆栈为空。");        return elements[top];    }}

链栈即采用链表作为存储结构实现的栈。当采用单链表存储线性表后，根据单链表的操

作特性选择单链表的头部作为栈顶，此时，入栈、出栈等操作可以在Ο(1)内完成。由于堆

栈的操作只在线性表的一端进行，在这里使用带头结点的单链表或不带头结点的单链表都可

以。使用带头结点的单链表时，结点的插入和删除都在头结点之后进行；使用不带头结点的

单链表时，结点的插入和删除都在链表的首结点上进行。

public class StackSLinked implements Stack {    private SLNode top; //链表首节点引用    private int size;     public StackSLinked() {        top=null;        size=0;    }     @Override    public int getSize() {        return size;    }     @Override    public boolean isEmpty() {        return size==0;    }     @Override    public void push(Object e) {        SLNode q=new SLNode(e,top);        top=q;        size++;    }     @Override    public Object pop() throws StackEmptyException {        if (size<1){            throw  new StackEmptyException("错误，堆栈为空");        }        Object obj = top.getData();        top=top.getNext();        size--;        return obj;    }     @Override    public Object peek() throws StackEmptyException {        if (size<1){            throw  new StackEmptyException("错误，堆栈为空");        }        Object obj = top.getData();        return obj;    }}