外观
05 - 栈与队列:浏览器回退、消息消费和单调结构
前置阅读:03 - 数组与链表的真实取舍。
后续阅读:07 - 双指针与滑动窗口、17 - 图的 DFS 与 BFS。生产者—消费者与背压见BlockingQueue 与生产者消费者。
摘要
校验嵌套括号时,需要先匹配最近打开的括号;处理排队任务时,通常需要先取出最早到达的任务。栈和队列分别保存这两种处理顺序。本文先说明基本操作,再通过括号匹配、循环队列和滑动窗口最大值,解释单调结构如何减少重复扫描,以及工程队列还需要哪些约束。
1. 两种顺序模型
- Stack(栈):LIFO(Last In, First Out,后进先出)。元素从同一端进入和取出,这一端称为栈顶;压栈是放入元素,出栈是取出栈顶元素。
- Queue(队列):FIFO(First In, First Out,先进先出)。元素从队尾进入、从队首取出,因此先进入的元素先被取出。
例如依次放入 A、B、C,栈的取出顺序是 C、B、A,队列的取出顺序是 A、B、C。选择结构前,先确定“下一步应该处理谁”,再决定如何存储。
浏览器回退可以用栈模型理解:最近访问的页面先被回退;这只是顺序模型,不代表浏览器内部只有一个栈。函数调用也存在嵌套关系,内层调用返回后,外层调用才能继续。任务排队和消息缓冲可以用队列保存到达顺序;BFS(Breadth-First Search,广度优先搜索)借助队列先处理较早发现的节点,逐层扩展。消息的取出顺序与并发处理后的完成顺序还需分别定义。
本文包含四种相关但职责不同的模型:
| 结构 | 保留的信息 | 典型问题 |
|---|---|---|
| 普通栈 | 最近进入且尚未完成的元素 | 括号、调用链、表达式 |
| 普通队列 | 到达顺序 | BFS、任务排队 |
| 单调栈 | 尚未找到左/右侧答案的候选 | 下一个更大值、柱状图 |
| 单调队列 | 当前窗口仍可能成为极值的候选 | 滑动窗口最大/最小值 |
双端队列(Deque)允许在两端放入和取出元素,既能用作普通栈或队列,也能支持后文的窗口算法。单调结构是在这些容器上增加筛选规则,使候选值始终按某个方向排列。“不变量”指每轮处理后都成立的状态约束,例如从栈底到栈顶的值始终不增;后文会说明如何维护它,以及为什么可以删除候选。
2. 括号匹配
左括号表示尚未完成的匹配。遇到右括号时,必须先匹配最近一个未匹配的左括号,这正是栈的顺序。比如 ([)] 读到 ) 时,栈顶是 [,即使更早有 (,也不能跳过栈顶去匹配,否则就破坏了嵌套关系。
下面是需放入类中的局部方法片段,text 应为非 null 字符串。pairs 保存右括号到左括号的映射,push、pop 分别压栈和出栈。代码忽略非括号字符,空字符串返回 true;它校验的是括号的配对与嵌套,不是完整的表达式语法。
java
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
static boolean valid(String text) {
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
Deque<Character> stack = new ArrayDeque<>();
for (char ch : text.toCharArray()) {
if (pairs.containsValue(ch)) {
stack.push(ch);
} else if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.pop() != pairs.get(ch)) {
return false;
}
}
}
return stack.isEmpty();
}Java 中通常优先用 ArrayDeque 代替旧的 Stack 类;ArrayDeque 不接受 null。
遇到右括号时,空栈意味着没有左括号可匹配;栈顶类型不符意味着嵌套错误,两者都立即返回 false。扫描结束后还要检查空栈,因为剩余左括号同样属于不完整匹配。设字符串长度为 n,括号类型固定,每个字符最多触发一次压栈或出栈,时间为 O(n),最坏额外空间为 O(n)。
3. 循环队列
固定数组实现队列时,不必在每次取出队首后搬动剩余元素。只需记录队首位置,入队和出队时更新位置;到达数组末尾后,用取模运算回到开头,复用已经空出的槽位。
必须明确一种判满策略:保留一个空槽、维护 size,或使用额外状态位,不能混用。下面的类片段使用 size:head 是队首下标,size 是当前元素数,下一次入队的位置由 (head + size) % data.length 推导,不另存 tail。空队列满足 size == 0,满队列满足 size == data.length。
java
class CircularQueue {
private final int[] data;
private int head;
private int size;
CircularQueue(int capacity) {
data = new int[capacity];
}
boolean offer(int value) {
if (size == data.length) return false;
data[(head + size) % data.length] = value;
size++;
return true;
}
int poll() {
if (size == 0) throw new IllegalStateException("empty");
int value = data[head];
head = (head + 1) % data.length;
size--;
return value;
}
}容量为 2 时,放入 10、20 后队列已满;取出 10 后,head 变为 1、size 变为 1。下一次入队的位置是 (1 + 1) % 2 = 0,正好复用原来保存 10 的槽位,取出顺序仍符合 FIFO。
这个示例不扩容,也不提供并发控制。正常使用应传入正容量,并假设 head + size 不发生整数溢出。原代码对容量 0 的行为是始终拒绝入队、出队抛出异常;负容量会在数组创建时失败。offer 满载时返回 false,poll 空队列时抛出 IllegalStateException,调用方需要处理这两种结果。
4. 单调栈:下一个更大元素
问题是:对每个元素,寻找它右侧第一个严格大于它的值,找不到则返回 -1。直接为每个位置向右扫描,会反复比较同一批元素。
从左到右扫描时,可以把尚未找到答案的位置放入栈。读到新值后,只要它大于栈顶对应的值,就为栈顶确定答案并出栈,再继续检查新的栈顶。因为扫描按下标递增进行,而该位置此前一直没有找到更大值,所以当前值就是它右侧第一个更大值。
下面是局部方法片段,需放入类中,并使用第 2 节的 ArrayDeque、Deque 导入;values 应非 null。保存下标是为了把答案写回原位置。每轮结束时,从栈底到栈顶的值单调不增,允许相等值同时留在栈中。
java
static int[] nextGreater(int[] values) {
int[] answer = new int[values.length];
java.util.Arrays.fill(answer, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < values.length; i++) {
while (!stack.isEmpty() && values[i] > values[stack.peek()]) {
answer[stack.pop()] = values[i];
}
stack.push(i);
}
return answer;
}例如输入 [2,1,3],读到 3 时先弹出值为 1 的下标,再弹出值为 2 的下标,两处答案都是 3;最后的 3 没有更大值,保留 -1。比较使用 >,因此相等值不能充当“更大”的答案。这里 -1 是未找到答案的标记;若实际答案也可能为 -1,返回值本身无法区分两种情况。
设数组长度为 n。虽然有嵌套循环,但每个下标最多入栈、出栈一次,总时间为 O(n),栈的最坏额外空间为 O(n)。这类分析称为均摊分析:统计整段操作的总成本,而不是认为每一轮都只做常数次操作。
5. 单调队列与滑动窗口最大值
滑动窗口是连续的一段元素,左右边界随扫描向右移动。设数组长度为 n、窗口大小为 k,且 1 <= k <= n,需要输出每个长度为 k 的窗口最大值。逐个扫描窗口的成本为 O((n-k+1)k),通常简写为 O(nk);单调队列把总时间降为 O(n)。
这里用双端队列保存候选下标,而不是窗口中的全部元素。处理下标 i 时,当前窗口左边界为 i-k+1,所以先从队首删除下标 <= i-k 的过期元素。再从队尾删除值小于等于新值的候选,最后把 i 放入队尾。
删除队尾候选的依据是:新元素更晚到达,离开窗口也更晚,且值不小于旧候选。此后只要旧候选还在窗口内,新元素也在,旧候选就无需再参与最大值竞争。这样,下标从队首到队尾递增,对应值严格递减,队首就是最大值的位置。
当前实现需要保存下标来判断过期,并区分重复值各自的离开时间。使用 <= 会删除较早的相等值、保留较晚的相等值;若只改成 <,相等候选会一起保留,对应值则单调不增,仍可求最大值,但候选不再严格递减。
6. 完整可运行示例:括号、循环队列与窗口最大值
下面的完整类对应文件名 StackQueueDemo.java,包含 main 入口。环境需支持 Map.of 等所用 API;两个括号方法行为一致,完整示例用直接比较识别左括号。maxWindow 要求非 null 数组和合法的 k;空数组没有合法窗口,非法 k 抛出 IllegalArgumentException。
java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Map;
/**
* 可运行示例:栈与队列:浏览器回退、消息消费和单调结构。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class StackQueueDemo {
static boolean validBrackets(String text) {
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
Deque<Character> stack = new ArrayDeque<>();
for (char ch : text.toCharArray()) {
// 左括号代表一个尚未完成的匹配任务,压入栈顶。
if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
else if (
pairs.containsKey(ch) &&
(stack.isEmpty() || stack.pop() != pairs.get(ch))
) return false;
}
return stack.isEmpty();
}
static int[] maxWindow(int[] values, int k) {
if (k <= 0 || k > values.length) throw new IllegalArgumentException(
"invalid k"
);
int[] result = new int[values.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < values.length; i++) {
// 先淘汰已经离开窗口左边界的下标。
while (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.pollFirst();
// 尾部更小的值不可能再成为最大值,可永久删除。
while (!deque.isEmpty() && values[deque.peekLast()] <= values[i])
deque.pollLast();
deque.offerLast(i);
// 队首始终保存当前窗口最大值的下标。
if (i >= k - 1) result[i - k + 1] = values[deque.peekFirst()];
}
return result;
}
static class CircularQueue {
private final int[] data;
private int head, size;
CircularQueue(int capacity) {
data = new int[capacity];
}
boolean offer(int value) {
if (size == data.length) return false;
// 通过 head + size 推导尾位置,取模实现数组环绕。
data[(head + size) % data.length] = value;
size++;
return true;
}
int poll() {
if (size == 0) throw new IllegalStateException("empty");
int result = data[head];
head = (head + 1) % data.length;
size--;
return result;
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
System.out.println(validBrackets("{[()]}"));
System.out.println(
Arrays.toString(maxWindow(new int[] { 1, 3, -1, -3, 5, 3, 6, 7 }, 3))
);
CircularQueue queue = new CircularQueue(2);
queue.offer(10);
queue.offer(20);
System.out.println(queue.poll());
}
}手工推演单调队列
窗口大小为 3,输入 [1,3,-1,-3,5]。下表中的候选以“下标:值”表示,按队首到队尾排列;未凑齐 3 个元素时不输出。
| 当前下标 | 处理后的候选 | 当前窗口最大值 |
|---|---|---|
| 0 | 0:1 | 尚未形成完整窗口 |
| 1 | 1:3,删除较小的 0:1 | 尚未形成完整窗口 |
| 2 | 1:3, 2:-1 | 3 |
| 3 | 1:3, 2:-1, 3:-3 | 3 |
| 4 | 4:5,先删除过期的 1:3,再删除尾部两个较小值 | 5 |
按代码推演,main 的预期输出如下。括号完整匹配得到 true,六个窗口分别输出最大值,循环队列先取出 10。
text
true
[3, 3, 5, 5, 6, 7]
10虽然代码包含嵌套 while,每个下标最多入队、出队一次,总时间仍为 O(n),额外空间为 O(k)。
当需求是窗口中位数或任意分位数(排序后指定比例位置的值)时,单调队列无法保留足够信息:被淘汰的较小值虽然不影响最大值,却可能影响排序位置。应考虑双堆或有序计数结构,并处理窗口移出与重复值;双堆是用两组堆维护较小、较大两部分,有序计数结构则按值保存顺序及出现次数。
7. 工程队列不是只有 FIFO
前面的算法只讨论元素怎样进出,并按输入规模分析空间,不涉及消费者失败、线程等待或持续过载。生产队列除了取出顺序,还必须定义:
- 容量上限与满载策略;
- 阻塞、超时、拒绝或丢弃语义;
- 任务失败后的重试和幂等,即重复处理同一任务时如何避免重复产生业务副作用;
- 关闭时是否排空以及如何唤醒等待者;
- 队列长度、等待时间和最老任务年龄等指标。
如果任务持续到达得比处理得快,积压就会增长。无界队列没有主动设置容量上限,并不意味着内存无限;它会把持续过载表现为内存占用增加和排队延迟上升。背压是把下游处理能力不足反馈给上游,让上游减速、等待或拒绝新任务;具体策略需按业务选择。完整并发协议见BlockingQueue 与生产者消费者。
8. 容易踩的坑
复查实现时,可以把问题落到具体边界:
- 是否需要原位置或过期判断?需要时应保存下标或等价的位置信息,而不只是值。
- 判满策略是否一致?用
size计数时,不应再套用保留一个空槽的容量规则。 - 相等元素应保留还是淘汰?下一个严格更大值不能由相等值回答,窗口最大值则可以保留较晚的相等候选。
- 调用方是否处理满载、空队列及非法窗口大小?容量和失败语义属于使用契约。
9. 总结
栈和队列的核心价值,是把“下一步处理谁”的顺序编码进数据结构。
- 栈适合处理最近未完成关系,队列适合按到达顺序扩展。
- 单调结构通过及时淘汰无效候选,把重复扫描变成均摊线性处理。
- 工程队列还必须考虑容量、背压和失败处理,不能只看 API。
查找主线继续阅读:二分查找与答案搜索。窗口状态见双指针与滑动窗口,队列分层应用见图的 DFS 与 BFS。