栈与队列：LIFO 与 FIFO 的两种世界观

你有没有想过，为什么编辑器里按 Ctrl+Z 能一步步撤销，而打印机却老老实实按提交顺序一张张出？这两件事看似无关，底层却是同一对"基础设施"的两种相反用法：一个只许从同一端进出，一个必须从两端分工。

这就是本篇的主角——栈（Stack） 和 队列（Queue）。它们都属于上篇讲过的 ADT：只规定"能做什么"，不规定"怎么存"。但正是这两种最朴素的秩序观，撑起了从函数调用、表达式求值到任务调度、消息队列的半壁江山。我们先把"世界观"立住，再动手实现，最后看两个几乎人人都踩过的坑。

一、栈（Stack）：后进先出（LIFO）的世界观

栈 = 只允许在同一端（栈顶）进行插入和删除的 ADT，语义是 LIFO（Last-In-First-Out，后进先出）。

想象一摞盘子：你只能在最上面放新盘子（push），也只从最上面拿走（pop），永远碰不到底下那个。最后放上去的，必然第一个被取走——这就是"后进先出"。

栈暴露给客户的契约只有四个操作：

操作	含义	异常
`push(x)`	把 `x` 压入栈顶	栈满时溢出
`pop()`	移除并返回栈顶元素	栈空时下溢
`peek()`	只看栈顶、不移除	栈空时下溢
`isEmpty()`	是否为空	—

下面用数组实现一个 ArrayStack，top 指向下一个可写入的位置（即"栈顶之上"）：

public class ArrayStack {
    private int[] data;
    private int top;  // 指向下一个可写入的位置（栈顶之上）

    public ArrayStack(int capacity) {
        data = new int[capacity];
        top = 0;
    }

    public void push(int x) {
        if (top == data.length) throw new IllegalStateException("stack overflow");
        data[top++] = x;
    }

    public int pop() {
        if (isEmpty()) throw new IllegalStateException("stack underflow");
        return data[--top];
    }

    public int peek() {
        if (isEmpty()) throw new IllegalStateException("stack empty");
        return data[top - 1];
    }

    public boolean isEmpty() { return top == 0; }
    public int size() { return top; }
}

用一个小程序验证 LIFO 语义——注意 push(40) 发生在两次 pop 之后，它占据的是腾出来的栈顶空位：

public static void main(String[] args) {
    ArrayStack s = new ArrayStack(3);
    s.push(10); s.push(20); s.push(30);
    System.out.println("size=" + s.size());      // 3
    System.out.println("peek=" + s.peek());      // 30
    System.out.println("pop=" + s.pop());        // 30
    System.out.println("pop=" + s.pop());        // 20
    s.push(40);
    System.out.println("peek=" + s.peek());      // 40
}

运行输出：

size=3
peek=30
pop=30
pop=20
peek=40

这张图把"同一端进出"画出来——所有动作都发生在栈顶那一侧：

二、队列（Queue）：先进先出（FIFO）的世界观

队列 = 只允许在一端入队、另一端出队的 ADT，语义是 FIFO（First-In-First-Out，先进先出）。

它像现实中的排队：新来的人站到队尾（enqueue），轮到的人从队首离开（dequeue）。先来的先服务，谁也别插队。

队列的契约：

操作	含义	异常
`enqueue(x)`	从队尾插入 `x`	队列满时溢出
`dequeue()`	从队首移除并返回	队列空时下溢
`peek()`	只看队首、不移除	队列空时下溢
`isEmpty()`	是否为空	—

坑的第一步就在这：如果用一个"普通数组 + head 指针"实现，每次 dequeue 都把后面所有元素整体前移一位，代价是 O(n)。这在高频出队的场景（如消息队列）完全不可接受。

正确解法是循环数组（circular array / ring buffer）：把数组首尾相接，head 和 tail 都用"取模"绕回。这样 enqueue / dequeue 都是 O(1)。我们用一个额外的 size 字段来区分"空"和"满"（否则 head == tail 既可能空也可能满）：

public class ArrayQueue {
    private int[] data;
    private int head;   // 队首（下一个出队位置）
    private int tail;   // 队尾（下一个入队位置）
    private int size;   // 当前元素个数

    public ArrayQueue(int capacity) {
        data = new int[capacity];
        head = 0; tail = 0; size = 0;
    }

    public void enqueue(int x) {
        if (size == data.length) throw new IllegalStateException("queue full");
        data[tail] = x;
        tail = (tail + 1) % data.length;  // 绕回
        size++;
    }

    public int dequeue() {
        if (size == 0) throw new IllegalStateException("queue empty");
        int v = data[head];
        head = (head + 1) % data.length;  // 绕回
        size--;
        return v;
    }

    public int peek() {
        if (size == 0) throw new IllegalStateException("queue empty");
        return data[head];
    }

    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }
}

验证循环特性：容量为 3，入满 1/2/3 后出队一个，再 enqueue(4) 会绕回到下标 0 那个腾出的空位：

public static void main(String[] args) {
    ArrayQueue q = new ArrayQueue(3);
    q.enqueue(1); q.enqueue(2); q.enqueue(3);
    System.out.println("size=" + q.size());        // 3
    System.out.println("dequeue=" + q.dequeue());  // 1
    q.enqueue(4);                                  // 绕回到下标 0
    System.out.println("peek=" + q.peek());        // 2
    System.out.println("dequeue=" + q.dequeue());  // 2
    System.out.println("dequeue=" + q.dequeue());  // 3
    System.out.println("dequeue=" + q.dequeue());  // 4
}

运行输出：

size=3
dequeue=1
peek=2
dequeue=2
dequeue=3
dequeue=4

循环数组的指针长这样——tail 在出队后可以从末尾"跳"回开头：

三、两个最容易写错的坑

坑一：栈的"静默溢出"。 上篇我们强调 ADT 不规定实现，但实现一旦选了定长数组，push 超过容量就必须显式抛异常或扩容。最阴险的错误是"忘了检查就直接 data[top++] = x"——数组越界在大多数语言里会直接崩，但在某些手写 C 代码里可能悄悄写到别的内存。永远在 push 前判断满。

坑二：队列的"假满"与空满歧义。 不用 size 字段时，head == tail 既表示空也表示满，必须用"额外布尔 flag"或"故意空一个槽位"来区分。循环数组的取模 (tail + 1) % n 一定要写对，漏掉取模会让指针一路越界。另一个常见写法是用链表实现队列：head 指向首节点、tail 指向尾节点，这样 enqueue/dequeue 都是 O(1) 且天然不用操心容量——但前提是 tail 指针要维护好，否则入队退化成 O(n) 的"走到队尾"。

本质一句话（提前剧透）：栈和队列都是"受限的线性表"——限制访问端，就用秩序换来了 O(1) 的确定性；选数组还是链表，本质是在"容量固定但要循环"和"容量无限但要管指针"之间二选一。

四、C++ 对照：STL 把栈和队列做成"适配器"

Java 这边，Stack 类其实是个历史包袱（它继承自 Vector，设计上有缺陷），现代写法更推荐用 ArrayDeque——它既是双端队列，又能当栈（push/pop/peek）又能当队列（add/poll/peek）用，性能也更稳。

C++ 的 std::stack / std::queue 则是典型的容器适配器（adapter）：它们自己不存数据，而是"套"在一个底层序列容器（默认 std::deque）之上，只暴露受限接口：

#include <stack>
#include <queue>

std::stack<int> s;        // 默认基于 std::deque
s.push(10);
int t = s.top();          // 等价于 peek
s.pop();                  // 注意：pop 不返回值，需先 top 再 pop

std::queue<int> q;        // 默认基于 std::deque
q.push(10);
int f = q.front();        // 队首，等价于 peek
q.pop();                  // 出队，同样不返回值

对照表一目了然：

维度	Java（ArrayDeque / 手写）	C++（std::stack / std::queue）
栈顶/队首查看	`peek()` 返回元素	`top()` / `front()` 返回元素
弹出	`pop()` 返回元素	`pop()` 不返回，先取再弹
底层	`ArrayDeque` 自己管数组	适配器，默认套 `deque`
容量	动态扩容	取决于底层容器
类型安全	泛型 `Stack<E>`	模板 `stack<T>`

最该记住的是 C++ 那个反直觉点：pop() 不返回被弹出的元素——很多新手写出 int x = q.pop(); 直接编译报错。这是为了避免"返回时拷贝构造可能抛异常"的歧义，设计上刻意如此。

五、收尾：什么时候用哪个

需要"最近操作优先回退"——栈：撤销栈、函数调用栈、括号匹配、表达式求值、深度优先搜索（DFS）的隐式栈。
需要"按到达顺序公平处理"——队列：打印队列、任务调度、消息缓冲、广度优先搜索（BFS）的显式队列。
两者都想要两端灵活——用双端队列（deque），Java 的 ArrayDeque 和 C++ 的 std::deque 都是它。

🐾 小结

对比项	栈 Stack	队列 Queue
秩序观	LIFO 后进先出	FIFO 先进先出
操作端	同一端（栈顶）	两端（尾入 / 首出）
数组实现关键	`top` 指针	`head`/`tail` + 循环取模 + `size`
出队代价（朴素）	不适用	O(n) 搬移 → 循环数组降为 O(1)
最易错点	满栈未判溢	`head==tail` 空满歧义、漏写取模
典型应用	撤销 / 调用栈 / DFS	调度 / 缓冲 / BFS
语言落地	Java `ArrayDeque`；C++ `std::stack`	Java `ArrayDeque`；C++ `std::queue`

一句话收束：栈和队列不是"更高级的数据结构"，而是"更克制的数据结构"——用对访问端的限制，把混乱的数组管成了可预测、O(1) 的工具。