栈

原文参考： （1）http://www.cnblogs.com/skywang12345/p/3562239.html （2）http://c.biancheng.net/view/3351.html （3）http://c.biancheng.net/view/3350.html

什么是栈（stack）

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

当栈中没有数据元素时称为空栈；向一个栈插入元素又称为 进栈或 入栈；从一个栈中删除元素又称为 出栈或 退栈。由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈，所以又把堆栈称为 后进先出表（Last In First Out，简称 LIFO）。 出栈示意图： 出栈前：栈顶元素是30。此时，栈中的元素依次是 30 --> 20 --> 10 出栈后：30出栈之后，栈顶元素变成20。此时，栈中的元素依次是 20 --> 10

入栈示意图： 入栈前：栈顶元素是20。此时，栈中的元素依次是 20 --> 10 入栈后：40入栈之后，栈顶元素变成40。此时，栈中的元素依次是 40 --> 20 --> 10

栈的基本操作

堆栈的基本操作除了进栈、出栈操作外，还有判空、取栈顶元素等操作。下面给出堆栈的抽象数据类型定义：

序号方法功能描述⑴getSzie ()输入参数：无 返回参数：非负整数 功能：返回堆栈的大小，即数据元素的个数。⑵isEmpty ()输入参数：无 返回参数：boolean 功能：如果堆栈为空返回 true，否则返回 false。⑶push(e)输入参数：Object 对象 e 返回参数：无 功能：数据元素 e 入栈。⑷pop()输入参数：无 返回参数：Object 对象 功能：栈顶元素出栈。⑸peek()输入参数：无 返回参数：Object 对象 功能：获取栈顶元素，但不出栈

java 中栈的接口：

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,2,3,4}，其存储状态如图所示：

顺序栈元素入栈

（1）最初，栈是"空栈"，即数组是空的，top 值为初始值 -1，如图所示： 首先向栈中添加元素 1，我们默认数组下标为 0 一端表示栈底，因此，元素 1 被存储在数组 a[0] 处，同时 top 值 +1： 采用以上的方式，依次存储元素 2、3 和 4，最终，top 值变为 3：

顺序栈元素出栈

top 变量的设置对模拟数据的 “入栈” 操作没有实际的帮助，它是为实现数据的 “出栈” 操作做准备的。

比如，将图中的元素 2 出栈，则需要先将元素 4 和元素 3 依次出栈。需要注意的是，当有数据出栈时，要将 top 做 -1 操作。因此，元素 4 和元素 3 出栈的过程分别如图 所示：

注意，图 中数组中元素的消失仅是为了方便初学者学习，其实，这里只需要对 top 值做 -1 操作即可，因为 top 值本身就表示栈的栈顶位置，因此 top-1 就等同于栈顶元素出栈。并且后期向栈中添加元素时，新元素会存储在类似元素 4 这样的旧元素位置上，将旧元素覆盖。

Stack 的顺序存储实现

public class StackArray implements Stack { private final int LEN = 8; //数组的默认大小 private Object[] elements; //数据元素数组 private int top; //栈顶指针 public StackArray() { top = -1; elements = new Object[LEN]; } //返回堆栈的大小 public int getSize() { return top+1; } //判断堆栈是否为空 public boolean isEmpty() { return top<0; } //数据元素 e 入栈 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; } //栈顶元素出栈 public Object pop() throws StackEmptyException { if (getSize()<1) throw new StackEmptyException("错误，堆栈为空。"); Object obj = elements[top]; elements[top--] = null; return obj; } //取栈顶元素 public Object peek() throws StackEmptyException { if (getSize()<1) throw new StackEmptyException("错误，堆栈为空。"); return elements[top]; } }

栈的链表实现

链栈，即用链表实现栈存储结构。链栈的实现思路同顺序栈类似，顺序栈是将数顺序表（数组）的一端作为栈底，另一端为栈顶；链栈也如此，通常我们将链表的头部作为栈顶，尾部作为栈底，如图 所示：

将链表头部作为栈顶的一端，可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶，意味着： 在实现数据"入栈"操作时，需要将数据从链表的头部插入； 在实现数据"出栈"操作时，需要删除链表头部的首元节点；

链栈元素入栈

例如，将元素 1、2、3、4 依次入栈，等价于将各元素采用头插法依次添加到链表中，每个数据元素的添加过程如图 所示：

链栈元素出栈

若要将元素 3 出栈，根据"先进后出"的原则，要先将元素 4 出栈，也就是从链表中摘除，然后元素 3 才能出栈，整个操作过程如图 所示：

Stack 的链式存储实现

public class StackSLinked implements Stack { private SLNode top; //链表首结点引用 private int size; //栈的大小 public StackSLinked() { top = null; size = 0; } //返回堆栈的大小 public int getSize() { return size; } //判断堆栈是否为空 public boolean isEmpty() { return size==0; } //数据元素 e 入栈 public void push(Object e) { SLNode q = new SLNode(e,top); top = q; size++; } //栈顶元素出栈 public Object pop() throws StackEmptyException { if (size<1){ throw new StackEmptyException("错误，堆栈为空。"); } Object obj = top.getData(); top = top.getNext(); size--; return obj; } //取栈顶元素 public Object peek() throws StackEmptyException { if (size<1){ throw new StackEmptyException("错误，堆栈为空。"); } return top.getData(); } }