栈（stack）

在第一节有介绍过，栈是一种后进先出（LIFO）策略的集合类型。想象一个薯片桶，最后一块放进去的薯片，总是被最先取出来。栈就是这样的一个容器。放进去叫“入栈”，取出来叫“出栈”。

在 Java 语言中内置了 Stack 数据类型，我们可以直接拿来用。

Stack<String> chips = new Stack<>();

// 入栈
chips.push("hello");
chips.push("world");

// 出栈
chips.pop();

// 访问栈顶元素（不会出栈）
chips.peek();

用链表实现栈

1. 将链表的头节点作为栈顶
2. 入栈时，将新的节点作为新的栈顶（头插法）
3. 出栈时，先获取链表头节点（栈顶）的值，再把下一个节点置为栈顶，返回原来的栈顶值（即把头节点从链表中删除）

用数组实现栈

1. 将数组的尾部作为栈顶
2. 入栈时，将新的节点添加到数组尾部
3. 出栈时，先获取数组尾部元素的值，再把尾部元素从数组中删除，最后返回（即删除数组尾部）

栈的典型应用

1. 逆序输出（十进制转其他进制）
2. 括号匹配
3. undo操作
4. Dijkstra双栈算式表达式求值法。将操作数和运算符分别放入两个栈中，遇到左括号“（” 则忽略，遇到操作数则将操作数压入栈1中，遇到运算符将它压入栈2中，遇到右括号，则弹出运算符和操作数，计算结果后重新压入栈中。

队列（queue）

队列是一种先进先出（FIFO）策略的集合类型。就像排队队伍，先到的先得。

在 Java 中，LinkedList 和 ArrayList 就是队列的实现，可以直接使用。

Queue<String> list = new LinkedList<>();

list.add("hello");
list.add("world");

// 访问队首元素
list.peek();

// 取出队首元素
list.poll();

用链表实现队列

1. 将链表的头节点和尾节点分别作为队头和队尾
2. 出队时，取走头节点
3. 入队时，添加到尾节点

声明数据类型时，最好是在类里面声明好头、尾的引用，这样访问尾节点就不需要遍历整个链表

/* 基于链表实现的队列 */
class LinkedListQueue {
    private ListNode head, 
    private ListNode tail, 
    private int size = 0;
    ...
}

用数组实现队列

1. 将数组索引从小到达依次作为队头到队尾
2. 入队时，只需要在数组末尾添加元素
3. 出队时，删除索引最小的元素，同时，需要有一个变量来指示当前的队头（因为数组是不可变的，前面的元素如果出队过，数组则存在脏位置）
4. 为了避免多次入队出队后数组空间不够了，可以在空间用完后，把队尾重置到 index 0 的位置，就像是一个“环形数组”一样（前提是不要头尾撞车）。或者直接一点，用“数组扩容机制”搬运到一个更大的数组中去

队列的典型应用

1. 餐厅排位
2. 打印机的任务队列
3. 当然，在工程实践中，大多数队列只是拿来当一堆数据的集合

扩展：如何用两个栈实现一个队列？

1. 添加元素时往A栈添加
2. 删除元素时，先判断B栈是否为空，如果非空，直接从B栈取出最顶元素删除，如果为空，先把A栈里的元素全部倒入B栈中，然后删除最顶元素。