概述

栈是一种用于存储数据的简单数据结构（与链表类似）。数据入栈的次序是栈的关键。可以把一堆盘子看成栈的例子。当盘子洗干净后，它们会添加到栈的顶端。当需要盘子时，也是从栈的顶端拿取。所以最后一个放入的盘子最先被拿走。

定义：具有一定操作约束的线性表。只在一端（栈顶，Top）做插入、删除。

基于链表实现栈

如何使用链表来实现栈呢，来个图加深理解：

名词解释

• 插入数据：入栈（push），类似于往栈顶放盘子。
• 删除数据：出栈（pop），类似于拿走栈顶的盘子。
• 后入先出：Last In First Out（LIFO）

通过上图，我们可知，栈顶就是链表的表头结点，push 操作本质就是链表表头插入；pop 操作本质就是链表表头删除。若还要实现对栈中所有元素的遍历操作，Stack 类需要实现 Iterable， 具体参考【背包】。

代码

public class Stack<Item> implements Iterable<Item>{
    private Node first; // 栈顶
    private int N;
    private class Node{ // 定义了结点的嵌套类
        Item item;
        Node next;
    }
    public boolean isEmpty() { return first == null; } // 或： N == 0
    public int size() { return N; }
    public void push(Item item){
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    public Item pop(){
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
    // iterator() 的实现参看背包
    public static void main(String[] args) {
        // 创建一个栈并根据StdIn中的指示压入或弹出字符串
        Stack<String> s = new Stack<String>();
        while(!StdIn.isEmpty()){
            String item = StdIn.readString();
            if(!item.equals("-"))
                s.push(item);
            else if(!s.isEmpty()) StdOut.print(s.pop() + " ");
        }
        StdOut.println("(" + s.size() + " left on stack)");
    }
}

运行结果