1. 栈：后进先出
1.1 栈的本质与应用
栈是 **LIFO（后进先出）**结构，只在一端操作。系统栈（函数调用）、撤销栈、括号匹配都是栈的经典舞台。
# 经典应用: 括号匹配
# 左括号入栈，右括号弹出配对
# 栈空或最终栈非空 → 括号不匹配
# 扩展: 带优先级（({}) 需要匹配时检查栈顶类型）
1.2 表达式求值
中缀转后缀（逆波兰）、后缀求值，是栈最「教科书」的应用：
# 后缀求值（伪代码）
# 遇数字入栈；遇运算符弹出两数运算，结果入栈
# 最终栈顶即结果
# 中缀→后缀: 运算符栈（优先级+括号控制弹出）
2. 单调栈
2.1 思想与模板
单调栈维护「栈内元素单调递增/递减」，用于快速找「每个元素左右第一个更大/更小」——O(n) 解决暴力 O(n²) 的问题（如柱状图最大矩形、每日温度）。
# 找每个元素右边第一个更大的元素（单调递减栈，存下标）
def next_greater(nums):
res, stack = [-1] * len(nums), []
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x: # 当前 x 是栈顶的下一个更大
res[stack.pop()] = x
stack.append(i)
return res
关键理解：出栈时，当前元素就是被弹出元素「下一个更大」的候选。单调栈在「区间最值相关」问题上非常好用（接雨水、最大矩形、子数组最小乘积）。
2.2 栈内单调方向的选择
找「下一个更大」用递减栈；找「下一个更小」用递增栈。单调方向决定谁先出栈，写错方向结果全反——按需求先定单调性再写循环。
3. 队列：先进先出
3.1 队列的变体
队列是 FIFO 结构，工程上常用三种变体：
# 循环队列: 数组 + 头尾指针，避免频繁搬移（消息缓冲常用）
# 双端队列 Deque: 两端都可进出，用于滑动窗口/回文
# 优先队列: 按优先级出队（见第 4 节堆）
3.2 BFS 与层序遍历
队列是 **BFS（广度优先）**的天然载体：先入队的先处理，保证「按层推进」。
# BFS 模板
# queue = [start]
# while queue:
# node = queue.pop(0)
# for neighbor in node.neighbors: queue.append(neighbor)
# 应用: 最短路径（无权图）、层序遍历、拓扑排序
4. 堆：优先队列的实现
4.1 堆的性质与表示
**堆（Heap）**是完全二叉树，父节点 ≥（或 ≤）子节点。数组下标表示：父 (i-1)/2，左子 2i+1，右子 2i+2。
# 最小堆的核心操作
# push: 尾部插入 → 上浮（与父比较交换）
# pop: 弹出堆顶 → 末尾补顶 → 下沉（与较小子交换）
# buildHeap: 从最后一个非叶节点向下调整（O(n) 建堆）
# 复杂度: push/pop O(log n)，top O(1)，buildHeap O(n)
4.2 堆排序
堆排序利用堆反复取最大/最小：建堆 + n 次 pop，O(n log n)，原地排序（不稳定）。相比快排，堆排序的最坏也是 O(n log n)，但常数大、缓存不友好，工程排序默认快排而非堆排。
5. 堆的经典应用
5.1 Top-K 问题
海量数据找 Top-K 用小根堆（存 K 个）：堆顶是当前第 K 大，新元素大于堆顶就替换下沉。时间复杂度 O(n log K)，空间 O(K)——比全排序省内存。
# 找最大 K 个：维护大小为 K 的最小堆
# for x in stream:
# if heap.size < K: heap.push(x)
# elif x > heap.top(): heap.pop(); heap.push(x)
# 结果: 堆里就是最大的 K 个
5.2 合并有序序列
多路归并（K 个有序数组/文件合并）用优先队列取最小头：每次从堆顶弹出一个元素，再从对应序列补一个。时间复杂度 O(n log K)。是外排序、归并索引的核心。
5.3 定时器与延迟任务
时间轮/最小堆定时器：把「到期时间」作为键放进最小堆，堆顶即最近到期任务——Redis 的过期键、Linux 定时器、任务调度器都用堆做「最近到期优先」。
6. 单调队列
6.1 滑动窗口最值
单调队列维护「窗口内单调递减」的索引序列，O(n) 求滑动窗口最大值（经典题）：
# 滑动窗口最大值（单调递减队列，存下标）
# 窗口左端出界 → 出队；新元素把队尾较小者弹出；队首即窗口最大
# 单调队列: 队首最大/最小，两端都能操作（Deque）
与单调栈对比：单调队列服务「滑动窗口/区间」，单调栈服务「全局左右最值」。两者都靠「维护有序 + 及时淘汰」把暴力 O(n·k) 降到 O(n)。
7. 工程实践清单
# 选型决策
# 需要"最后进来的先处理" → 栈（回退、括号、表达式）
# 需要"先进先出" → 队列（BFS、缓冲、任务）
# 需要"按优先级处理" → 优先队列/堆（Top-K、调度、定时）
# 需要"窗口内最值" → 单调队列
# 需要"左右第一个更大/更小" → 单调栈
语言内建优先：Python collections.deque、heapq；Java ArrayDeque、PriorityQueue——不要手写基础结构，除非追求极限或需要自定义比较器。
8. 常见陷阱
- 优先队列比较器写反：Java PriorityQueue 默认小顶堆，自定义 Comparator 方向容易搞反，先写 3 个元素自测。
- 堆数组越界：上浮/下沉的下标计算在边界要判空。
- 单调队列没清出界元素：窗口滑动后队首可能已出界，忘记出队导致结果错。
- 把 Deque 当栈用但方法混淆：push/pop 是头部操作（Deque 当栈），addLast/removeFirst 是队列操作，分清 API 语义。
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。