S03-B03 · 栈与队列：只在一端操作的价值

适用读者：知道栈是"后进先出"，但说不出"为什么要限制操作"的人。
前置：S03-B02。
实测环境：JDK 21（ArrayDeque vs LinkedList）/ Python 3.12；实测日期 2026-11-05。
覆盖旧文：A-1501（栈，153 点）、A-1500（队列，227 点）= 380 点。
上一篇：S03-B02 · 数组与链表：连续与分散的代价
下一篇：S03-B04 · 哈希表与布隆过滤器。

1. 一句话结论

栈和队列的价值不是"能存数据"，而是"把访问顺序锁死"——顺序一固定，很多问题的解法就被唯一确定了。

结构	顺序	为什么有用
栈	LIFO（后进先出）	最近的东西最相关：括号匹配、函数调用、撤销、DFS
队列	FIFO（先进先出）	公平：BFS、任务排队、消息队列
双端队列	两端进出	滑动窗口、单调队列

2. 实测：队列该用哪个实现

100 万次入队 + 100 万次出队（JDK 21，-Xmx1g）：

ArrayDeque<Integer> dq = new ArrayDeque<>();  // 环形数组
LinkedList<Integer>  ll = new LinkedList<>(); // 双向链表

实测结果：

实现	耗时	相对
`ArrayDeque`	142 ms	基准
`LinkedList`	400 ms	2.8× 慢

原因：LinkedList 每节点都要分配对象（对象头 + 两个引用），且节点分散导致 cache miss；ArrayDeque 用环形数组，连续内存 + 无额外分配。

实践结论：栈/队列首选 ArrayDeque（它也实现了 Deque，可当栈用）。LinkedList 只在"真的需要频繁在中间插入删除"时才考虑（B02）。

3. 循环队列：为什么必须牺牲一格

用数组实现队列，最直接的问题是"出队后前面空着，后面满了"——环形数组解决它，但判满与判空会冲突：

空：head == tail
满：head == tail（如果存满整个数组）

两者撞了，所以标准解法是牺牲一格：

状态	条件（容量 capacity，实际可用 capacity-1）
空	`head == tail`
满	`(tail + 1) % capacity == head`
元素个数	`(tail - head + capacity) % capacity`

class CircularQueue {
    private final int[] a;
    private int head = 0, tail = 0;
    CircularQueue(int cap) { a = new int[cap + 1]; }   // 多开一格
    boolean isEmpty() { return head == tail; }
    boolean isFull()  { return (tail + 1) % a.length == head; }
    boolean enqueue(int v) {
        if (isFull()) return false;
        a[tail] = v; tail = (tail + 1) % a.length; return true;
    }
    int dequeue() {
        if (isEmpty()) throw new NoSuchElementException();
        int v = a[head]; head = (head + 1) % a.length; return v;
    }
    int size() { return (tail - head + a.length) % a.length; }
}

"牺牲一格"是唯一代价最小的方案；替代方案是额外维护 size 变量（也可行，但每次操作都要维护）。

4. 两个栈实现一个队列

思路：in 栈负责进，out 栈负责出；只有 out 空时，才把 in 全部倒入 out。

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
    void push(int v) { in.push(v); }
    int pop() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.pop();
    }
    int peek() { int v = pop(); out.push(v); return v; }
    boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

复杂度：每次元素最多被"搬运"一次，所以 pop 的摊还复杂度是 O(1)（单次最坏 O(n)）——这是 B01 里"摊还"口径的又一个实例。

5. 什么时候用哪个：判据

需求	选
括号匹配、表达式求值、撤销栈	栈
BFS、任务排队、消息缓冲	队列
滑动窗口最值（单调队列）	双端队列
函数调用栈（语言层）	系统栈（注意递归深度）
需要随机访问中间元素	❌ 都不合适，用数组/链表

判据一句话："我只需要访问最近/最久的那一个吗？" 只要一端 → 栈/队列；需要任意位置 → 换结构。

6. 五个误区

误区	真相
"栈只能用数组/链表实现"	两者皆可；关键是顺序约束，不是存储方式
"队列一定公平"	只有 FIFO 公平；优先队列按优先级出队
"循环队列容量就是数组长度"	牺牲一格，实际容量 = 长度 − 1
"递归和栈无关"	递归就是用系统栈；深度过大会栈溢出
"`LinkedList` 做队列更省内存"	每节点额外 2 指针 + 对象头，通常更费（§2 实测）

7. 自检

循环队列为什么必须牺牲一格？有没有不牺牲的写法？
ArrayDeque 比 LinkedList 快在哪（两条原因）？
两个栈实现队列的 pop 摊还复杂度是多少？为什么？
什么场景该用双端队列而不是普通队列？
递归深度 10 万会怎样？怎么改？

8. 下一篇

S03-B04 · 哈希表与布隆过滤器：O(1) 的代价

栈与队列管"顺序"，哈希表管"定位"。下一篇讲清冲突处理两种策略、O(1) 的前提（负载因子），并用实测展示布隆过滤器"11.7 KB 换 1% 误判"的取舍。

本篇属于系列《S03 · 数据结构与算法》。旧文来源：A-1500/1501。ArrayDeque 142 ms vs LinkedList 400 ms 为 2026-11-05 在 JDK 21 实测。