1.栈 List

定义

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶。

栈有时又叫做LIFO（后进先出）表，即last-in，first-out

现实中的栈

栈的接口

public interface StackInterface
     
       {    /**     * 将新元素加到站定     * @param newEntry 带插入站的对象 */    public void push(T newEntry);    /**     * 删除并返回栈顶     * @return 栈顶的对象，如果栈为空则返回null */    public T pop();    /**     * 取出栈顶     * @return 栈顶的对象，如果栈为空则返回null */    public T peek();    /**     * 检查栈是否为空     * @return 如果栈为空返回true */    public boolean isEmpty();    /**     * 从栈中删除所有元素 */    public void clear();}
     

程序栈

当一个程序执行时，一个被称为程序计数器的专用存储单元指向当前指令。当一个方法被调用时，程序的运行时环境为这个方法创建一个称为活动记录或栈帧的对象，这个活动记录显示该方法在执行过程中的状态。具体说，活动记录含有方法的实参、局部变量和当前指令的引用，即程序计数器的一个副本。在这个方法被调用时，活动记录被压入称为程序栈（或者称为Java栈）中。

由于一个方法可以调用另一个方法，程序栈往往含有多个活动记录。位于栈顶的活动记录，属于当前正在执行的方法，紧接在栈顶下的记录，属于调用当前方法的方法。

当main开始执行，他的活动记录位于程序栈顶，如图A

当main调用methodA时，一个新的记录被压入栈，此时程序计数器为50，图B展示methodA刚开始执行时，main更新记录与methodA的新纪录

当methodA调用methodB时，程序计数器为120，一个新的活动记录被压入栈。图C展示当methodB刚开始执行时main为改变的记录、methodA更新后的记录以及methodB的新纪录。

在methodB执行过程中，活动记录被更新，但main和methodA的记录保持不变。

Java类库：类Stack

public class Stack
     
       {                                  public T push(T item);    public T pop();    public T peek();    public boolean empty();    /**     * 在栈中查找指定对象     * @param desiredItem 待查找的对象     * @return 如果desiredItem在栈中，则返回其位置；如果不在则返回-1；栈顶的位置是-1 */    public int search(T desiredItem);    /**     * @return 栈的一个遵循Java接口的Iterator的迭代器 */    public Iterator
      
        iteraotr();    /**     * @return 栈的一个遵循Java接口ListIterator的迭代器 */    public ListIterator
       
         listIterator();}
       
      
     

2.基于链表的实现

如果用链表表示栈，则第一个结点应该引用栈顶元素。

类的框架

栈的链表实现有一个数据域topNode，它是链表的表头引用，默认构造函数将这个数据域设置为null。

public class LinkedStack
     
       implements StackInterface
      
       , Serializable {    private Node topNode; //引用链表中第一个结点    public LinkedStack() {        topNode = null;    }    private class Node implements Serializable {        private T data; //栈的元素        private Node next; //指向下一个结点的连接    }    // 在栈顶插入    public void push(T newEntry) {        Node newNode = new Node(newEntry, topNode);        topNode = newNode;    }    // 删除栈顶    public T pop() {        T top = null;        if (topNode != null) {            top = topNode.getData();            topNode = topNode.getNext();        }        return top;    }    // 检索栈顶    public T peek() {        T top = null;        if (topNode != null)            top = topNode.getData();        return top;    }    public boolean isEmpty() {        return topNode == null;    }    public void clear() {        topNode = null;    }}
      
     

3.基于数组的实现

public class ArrayStack
     
       implements StackInterface
      
       , Serializable {    private T[] stack; //存放栈元素的数组    private int topIndex; // 栈顶元素索引    private static final int DEFAULT_MAX_SIZE = 50;    public ArrayStack() {        this(DEFAULT_MAX_SIZE);    }    public ArrayStack(int initialCapacity) {        stack = (T[]) new Object[initialCapacity];        topIndex = -1;    }    // 在栈顶插入    public void push(T newEntry) {        topIndex++;        if (topIndex >= stack.length) {            //若数组已满，扩展数组        }        stack[topIndex] = newEntry;    }    // 删除栈顶    public T pop() {        T top = null;        if (!isEmpty()) {            top = stack[topIndex];            stack[topIndex] = null;            topIndex--;        }        return top;    }    // 检索栈顶    public T peek() {        T top = null;        if (!isEmpty())            top = stack[topIndex];        return top;    }    public boolean isEmpty() {        return topIndex < 0;    }    public void clear() {        stack = null;    }}
      
     

4.基于向量的实现

public class VectorStack
     
       implements StackInterface
      
       , Serializable {    private Vector
       
         stack; //栈顶是最后一个元素    public VectorStack() {        stack = new Vector(); // 需要时向变量大小将成倍增加    }    public VectorStack(int maxSize) {        stack = new Vector(maxSize);    }    // 在栈顶插入    public void push(T newEntry) {        stack.addElement(newEntry);    }    // 删除栈顶    public T pop() {        T top = null;        if (!isEmpty()) {            top = stack.lastElement();            stack.removeElement(stack.size() - 1);        }        return top;    }    // 检索栈顶    public T peek() {        T top = null;        if (!isEmpty())            top = stack.lastElement();        return top;    }    public boolean isEmpty() {        return stack.isEmpty();    }    public void clear() {        stack.removeAllElements();    }}
       
      
     

关联：

参考数据：《Java数据结构和算法》