02.3.2 栈与队列、单调栈
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列
这个知识域解决什么问题
栈与队列是受限线性结构,分别对应回溯嵌套与顺序处理两类场景。本知识域围绕一条主线展开:栈基础与括号表达式求值 → 单调栈与柱状图、接雨水 → 队列、双端队列与循环队列 → 优先队列、堆与栈队列综合。重点讲清结构语义、模拟推导与单调化维护过程,代码以 Java 为主并标注边界条件。
知识地图
栈基础与括号表达式求值(1)
→ 单调栈与柱状图、接雨水(2)
→ 队列、双端队列与循环队列(3)
→ 优先队列、堆与栈队列综合(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.3.2.1 | 栈基础与括号表达式求值 | LIFO、数组/链表实现、有效括号、逆波兰求值、中缀转后缀、计算器、字符串解码、调用栈与 DFS | 20 |
| 02.3.2.2 | 单调栈与柱状图、接雨水 | 单调方向、每日温度、下一个更大、循环数组、柱状图最大矩形、接雨水栈/DP/双指针、均摊 O(n) | 20 |
| 02.3.2.3 | 队列、双端队列与循环队列 | FIFO、链表队列、两栈队列、Deque、循环队列判空判满、队列实现栈、BFS 与层序遍历 | 20 |
| 02.3.2.4 | 优先队列、堆与栈队列综合 | 堆数组表示、上浮下沉、建堆 O(n)、Top-K、第 K 大、双堆中位数、单调队列窗口最大、最小栈、复杂度对比 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。
学习路径
先 1 掌握栈语义与括号/表达式求值,再 2 练熟单调栈的弹栈结算模板与柱状图、接雨水三种解法,3 理解队列语义、两栈模拟与循环队列设计,最后 4 掌握堆、优先队列与单调队列的选型和复杂度推导。
自检
- [ ] 能手写有效括号与逆波兰求值,说明减法除法顺序
- [ ] 能讲清单调栈弹栈结算时左右边界与当前元素角色
- [ ] 能写出柱状图最大矩形与接雨水单调栈代码,并对照 DP/双指针空间口径
- [ ] 能设计循环队列并说明判空判满两种口径
- [ ] 能说清两栈实现队列的均摊 O(1) 推导
- [ ] 能手写双堆数据流中位数与窗口最大值单调队列
- [ ] 每题能报出时间、空间与口径,并列边界用例