栈与队列专题导读

两种结构，两种秩序

栈和队列是最基础的两种"受限线性表"——它们只暴露少数几个口子让你存取数据，而正是这些限制决定了它们的用途：

结构	存取规则	一句话记忆	典型场景
栈 Stack	FILO，先进后出	只能从栈顶进出，像摞盘子	括号匹配、递归模拟、撤销操作
队列 Queue	FIFO，先进先出	从队尾进、队头出，像排队	层序遍历、BFS、任务调度

把直觉对上号：栈处理"最近发生的事"（最后进来的最先处理，匹配类问题的天然容器）；队列处理"按到达顺序的事"（保序，层层推进）。后面做题时，先问自己"这题关心的是最近一桩还是最早一桩"，容器选择往往就定了。

Java 实现选型：用 Deque，不用 Stack

Java 面试和刷题里有个经典劝退点：java.util.Stack 继承自 Vector，所有方法都加了 synchronized 锁，单个线程用不上却背上开销；更糟的是它暴露了 get(int)、insertElementAt 等随机访问接口，破坏了"只能操作栈顶"的语义。官方 Javadoc 早就建议用 Deque 接口替代。

实践结论只有一条：声明用 Deque 接口，实现用 ArrayDeque。

// 当作栈用：push/pop/peek 都操作队头
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);          // 等价 addFirst
stack.peek();           // 查看栈顶，不移除
stack.pop();            // 弹出栈顶，空栈抛异常
 
// 当作队列用：offer/poll/peek 操作两端
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);         // 队尾入，等价 addLast
queue.poll();           // 队头出，等价 pollFirst

为什么选 ArrayDeque：底层是可扩容的循环数组，两端操作均为均摊 O(1)，没有 LinkedList 每个节点的对象头和指针开销，缓存局部性也更好。注意一个坑：ArrayDeque 不允许存 null，而 LinkedList 允许——刷题时存的都是基本类型包装类，影响不大，但要心里有数。

另一个细节：pop / poll 在容器为空时的行为不同——pop 抛 NoSuchElementException，poll 返回 null。模板代码里通常先用 isEmpty() 判断，避免依赖这两种语义。

顺手备一张常用操作复杂度速查表，写题时不用再猜：

操作	ArrayDeque	LinkedList	说明
`push` / `pop`（栈语义）	均摊 O(1)	O(1)	均操作队头
`offer` / `poll`（队列语义）	均摊 O(1)	O(1)	尾进头出
`peek`	O(1)	O(1)	只看不取
`contains(x)`	O(n)	O(n)	两者都要线性扫
随机访问 `get(i)`	不支持	不支持	受限结构本就不该有

可见两者渐进复杂度几乎一致，ArrayDeque 胜在常数：连续内存对 CPU 缓存友好，每个元素没有额外的节点对象。只有当容量变化极端剧烈、或需要允许 null 时，才考虑 LinkedList。

互模拟：232 与 225 的核心思路

专题前两道题是"用一种结构模拟另一种"，目的不是刁难，而是逼你把两种顺序的差异想透。

用栈实现队列（LeetCode 232）：一个栈的顺序是反的，两个栈串起来负负得正。设入栈 in 和出栈 out：

入队：压入 in；
出队：out 为空时，把 in 全部倒灌进 out，再从 out 弹出。

每个元素最多进两次、出两次，均摊复杂度仍是 O(1)。关键细节：只要 out 非空就直接从它出队，不要急着倒灌，否则顺序会乱。倒灌一次的直观过程：

入队 1,2,3 后：in=[3,2,1]  out=[]
出队：out 为空 → 全部倒灌
      in=[3,2,1] --倒灌--> out=[1,2,3]
      从 out 弹出 1，正是最早入队的元素 ✓
之后入队 4：只进 in=[4]，出队继续从 out=[2,3] 弹 2 ✓

倒灌只在 out 空了的那一刻发生，in 里攒着的元素不会插队到 out 已有元素前面——这正是"out 非空就直接用"的全部理由。

用队列实现栈（LeetCode 225）：反过来用队列模拟栈，常见两种思路：

双队列：q1 存元素，q2 当辅助。入栈时新元素进 q2，再把 q1 全部接到 q2 后面（保证新元素总在队头），最后交换两个队列的引用。入栈 O(n)，出栈 O(1)。
单队列：入栈时先把新元素入队，再把队列里原有的 n-1 个元素依次出队又入队，让新元素转到队头。逻辑一样，只是少了一个容器。

互模拟做完，你会发现一个规律：两个 FIFO 凑出一个 FILO（代价是均摊），一个 FIFO 直接凑出 FILO（代价是每次入栈 O(n)）。顺序的翻转永远是要付出代价的。

专题知识地图

本专题从互模拟出发，一路通向四类经典应用。每类应用背后都藏着栈或队列的一个"性格"：

栈与队列
├── 互模拟：232 用栈实现队列 / 225 用队列实现栈
├── 匹配与消除（栈的"就近配对"）
│    ├── 20   有效的括号
│    ├── 1047 删除字符串中的所有相邻重复项
│    └── 150  逆波兰表达式求值
├── 单调队列（队头队尾都有"淘汰规则"）
│    └── 239  滑动窗口最大值
└── 优先队列/堆（按优先级出队）
     └── 347  前 K 个高频元素

匹配与消除：括号、相邻重复项、逆波兰表达式，本质都是"新元素进栈前，先和栈顶做个了断"——能配对就一起消失，配不上就进栈等待。栈天然维护了"尚未匹配"的集合。
单调队列：普通队列只按到达顺序出队，单调队列额外维护队内元素的递减性，让"窗口最大值"永远待在队头，把 O(nk) 的暴力压到 O(n)。
优先队列：当"最值"不再有滑动窗口这种局部性时（比如全局频率最高的 K 个），堆是更合适的武器——出队顺序由优先级决定，而不是到达顺序。

单调队列和优先队列是本专题的难度天花板，它们俩的选型对比会在第 3 篇专门展开。

LeetCode 题单

题号	题名	一句话考点
232	用栈实现队列	双栈倒灌，均摊 O(1) 的出队
225	用队列实现栈	入栈时把旧元素转到新元素身后
20	有效的括号	左括号进栈、右括号找栈顶配对，三种不匹配情形
1047	删除字符串中的所有相邻重复项	栈顶与当前字符相同则弹出，栈即结果
150	逆波兰表达式求值	遇运算符弹两个数，注意操作数顺序
239	滑动窗口最大值	单调递减队列，队头即窗口最大值
347	前 K 个高频元素	哈希计频 + 小顶堆（或桶排序）

建议顺序就按表格从上到下：先互模拟热身，再做三道消除题建立"栈顶匹配"的直觉，最后攻坚单调队列和优先队列。每道题写完，用自己的话说清"栈/队列里到底存的是什么、什么时候出、出了之后干嘛"——这三问能答上来，这道题才算过。

参考

代码随想录 · 栈与队列专题