04. 栈与队列

0. 本章先解决什么问题

栈和队列都是“受限访问”的结构。

它们不让你随便从中间取元素,而是规定严格顺序:

• 栈:后进先出
• 队列:先进先出

这种限制反而很有用,因为它让很多问题变简单:

• 函数调用和递归。
• 括号匹配。
• 表达式求值。
• 浏览器前进后退。
• 任务排队。
• 广度优先搜索。
• 生产者消费者缓冲。
• 单调栈、单调队列优化。

本章讲栈、队列、双端队列、环形队列和单调结构。

先看这些结构的共同点:它们都通过限制访问位置来表达顺序。

这张图怎么读

这张图的主线是“限制访问位置”。栈只允许一端进出,所以天然表达撤销、调用栈、括号匹配;队列一端进一端出,所以表达等待、公平和层序;双端队列放开两端,适合滑动窗口;单调队列再加一个顺序不变量,用删除无用元素换取快速得到窗口最值。

1. 栈:后进先出

栈的规则:

最后放进去的,最先拿出来。

操作:

示意:

push A
push B
push C

栈顶 -> C
B
栈底 -> A

pop -> C

2. 栈的底层实现

栈可以用数组或链表实现。

数组栈:

[A][B][C]
^
top

优点:

• 连续内存。
• cache 友好。
• 操作简单。

缺点:

• 容量不够时可能扩容。

链表栈:

top -> C -> B -> A

优点:

• 不需要连续空间。
• 头部插入删除方便。

缺点:

• 指针开销。
• cache 不友好。

3. 栈和函数调用

函数调用天然像栈。

main 调用 f
f 调用 g
g 返回
f 返回
main 继续

调用栈:

栈顶: g
f
栈底: main

最后进入的函数最先返回。

递归也依赖调用栈。如果递归没有终止条件,栈会不断增长,最终栈溢出。

4. 栈适合的问题

栈适合处理“最近未完成”的东西。

核心直觉:

如果问题要求处理最近加入且尚未完成的对象,考虑栈。

5. 队列:先进先出

队列的规则:

最先进入的,最先离开。

操作:

示意:

入队方向 ->
[A][B][C]
^
出队方向

dequeue -> A

6. 队列适合的问题

队列适合处理“按到达顺序服务”的问题。

核心直觉:

如果问题要求公平地按顺序处理,考虑队列。

7. 环形队列

用数组实现队列时,如果不断出队,前面会空出来。

普通数组队列:

[ ][ ][C][D][E]
^
head
^
tail

环形队列把数组看成一个圈:

tail 到末尾后回到开头

示意:

capacity = 5
index: 0 1 2 3 4
data: D E _ B C
head: 3
tail: 2

通过取模:

next = (index + 1) % capacity

环形队列常用于固定大小缓冲区。

边界条件:head == tail 到底是空还是满?

环形队列最经典的 bug,是用 head == tail 同时表示空和满。

假设容量为 4:

index: 0 1 2 3

一开始:

head = 0
tail = 0

这显然表示空。但如果你连续放入 4 个元素,tail 绕回 0:

head = 0
tail = 0

这又像满。于是必须额外设计区分规则。

常见做法有两种:

这不是实现细节小事,而是抽象不变量:

head 指向下一个出队位置
tail 指向下一个入队位置
任何时刻都必须能唯一判断空/满

如果这个不变量不清楚,队列堆积、覆盖旧数据、少读一个元素、无限等待都会出现。

8. 双端队列

双端队列支持两端插入和删除。

它比栈和普通队列更灵活。

应用:

• 滑动窗口。
• 单调队列。
• 双向任务队列。
• 维护候选元素。

9. 单调栈

单调栈维护栈内元素单调。

常见用途:

• 找下一个更大元素。
• 找下一个更小元素。
• 计算柱状图最大矩形。
• 处理区间边界。

基本思想:

新元素进来时
把不可能再成为答案的旧元素弹出

单调栈的价值在于:

每个元素最多入栈一次、出栈一次
总成本 O(n)

10. 单调队列

单调队列常用于滑动窗口最值。

窗口向右移动时:

移除过期元素
移除比新元素更差的候选
加入新元素
队头就是当前最优

它把每个窗口都扫描一遍的 O(nk),优化成 O(n)。

核心是:

队列里只保留未来仍可能成为答案的候选。

11. 常见坑

环形队列常用两种方式区分满和空:

• 额外保存 size。
• 浪费一个位置,让满条件和空条件不同。

手推:单调栈为什么每个元素最多进出一次

以“找每个元素右边第一个更大的数”为例。维护一个递减栈:

新元素 x 到来时:
栈顶比 x 小 -> 栈顶的答案就是 x,弹出
继续比较新的栈顶
最后把 x 入栈

关键不是某一轮会弹多少个,而是总账:

每个元素只会入栈一次;
被弹出后不会再回来;

所以所有弹出次数加起来最多 n 次。

即使某一轮弹出很多元素,其他轮就少弹了。总成本是:

n 次入栈 + 最多 n 次出栈 = O(n)

这叫摊还分析。单调栈的本质不是“栈里排好序”,而是删掉未来不可能成为答案的候选。

反例:队列保证顺序,不保证系统稳定

队列经常被用来“削峰”,但它只是在管理等待顺序。

假设:

生产速度 = 每秒 1000 个任务
消费速度 = 每秒 800 个任务

队列每秒净增长:

200 个任务

只要这个差值长期存在,队列一定会越来越长。表现是:

所以队列设计必须回答:

队列最大长度是多少?
满了以后阻塞、拒绝、丢弃还是降级?
任务是否有过期时间?
消费者是否能扩容?
是否需要优先级或公平性?

队列是控制流和背压工具,不是无限容量的保险箱。

12. 联系实际:任务系统如何用队列

一个任务系统可能这样:

生产者提交任务
-> 队列缓存任务
-> worker 从队头取任务
-> 处理任务

队列带来:

• 解耦生产者和消费者。
• 吸收短期流量波动。
• 保持处理顺序。

但如果长期生产速度大于消费速度:

队列会越来越长
延迟会升高
内存会增长
最终需要背压、限流或丢弃策略

所以队列不是无限缓冲,它只是管理等待。

建模卡:用栈和队列描述一次任务处理

把一个任务系统拆成两类顺序:

练习:假设有 5 个任务按时间进入系统,但其中一些任务会生成子任务。什么时候应该用队列保证公平?什么时候应该用栈快速处理当前链路?什么时候要限制队列长度防止内存被撑爆?这个练习能把“先进先出/后进先出”变成系统设计判断。

13. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 栈和队列的访问规则有什么区别?
2. 为什么函数调用和递归天然对应栈?
3. 为什么 BFS 需要队列,DFS 可以用栈?
4. 环形队列如何复用数组空间?
5. 双端队列适合哪些场景?
6. 单调栈和单调队列为什么能把某些问题优化到 O(n)?
7. 队列堆积为什么会造成延迟升高和内存压力?

栈和队列的力量来自限制。限制访问顺序,反而让状态管理更清楚。

延伸阅读

• from - zero · data-structures
• ArrayBlockingQueue