栈与队列

栈与队列是最常见的抽象数据结构之一。它们看起来简单，但会进一步引出单调栈、单调队列、BFS 等更重要的算法套路。

识别信号

• 出现”括号匹配、嵌套结构、表达式求值”→ 栈
• 出现”下一个更大/更小元素、柱状图面积”→ 单调栈
• 出现”层序遍历、按层扩展、最短步数”→ 队列/BFS
• 出现”滑动窗口最大值/最小值”→ 单调队列

反例：如果问题核心是排序或查找而非顺序关系，栈和队列通常不是首选。

怎么处理

1. 先判断题目需要的是”最近未处理元素”还是”按进入顺序推进”。
2. 需要回退、匹配、找最近关系时优先用栈。
3. 需要按层扩展、按时间顺序推进时优先用队列。
4. 如果题目要求窗口内最大值、最近更大元素，再进一步判断是否要用单调结构。

单调栈 / 单调队列快概

这两个名字听起来高级，但本质就是给普通栈/队列加一条不变式：所有元素从底到顶（或从头到尾）始终单调递增/递减。新元素入栈前，不断弹出违反单调性的旧元素。

结构	不变式	典型场景	平均复杂度
单调栈（递增）	栈顶 = 当前最小；新值 ≤ 栈顶 则弹出	上一个更小元素、柱状图最大矩形	O(n) 摊还（每个元素最多入出一次）
单调栈（递减）	栈顶 = 当前最大；新值 ≥ 栈顶 则弹出	下一个更大元素、每日温度	O(n)
单调队列（递减）	队头 = 当前最大；从尾弹出小于新值的；从头弹出已出窗口	滑动窗口最大值	O(n)

为什么是 O(n) 不是 O(n²)： 表面上每个元素要与栈中多个元素比较，但每个元素整个生命周期只入栈一次、出栈一次，摊还后总操作仍是 O(n)。这是单调结构最关键的复杂度论证，面试必须会讲。

典型实例

专题	关键差异	先看什么
顺序结构处理框架	覆盖普通栈、单调栈、单调队列三种模式	栈/队列选择 + 单调结构的维护逻辑

工程实战题

专题	先看什么
电梯调度系统（工程）	OOP + LOOK 调度算法 + 多梯成本函数派单——电梯 / 磁盘 / AGV / CPU 调度同一骨架

看到什么就先想到这类

• 出现“括号匹配、表达式、最近更大 / 更小元素”。
• 出现“层序遍历、最短步数、按层扩展”。
• 出现“窗口最大值 / 最小值”。