1. 怎么看栈与队列题
栈和队列都不是“为了用数据结构而用数据结构”,它们真正解决的是访问顺序问题。
栈是后进先出。最后放进去的元素最先被处理,所以它适合处理“最近的、还没有匹配完的东西”。比如最近的左括号、最近的数字、最近还没被抵消的字符、最近还没结算的状态。
队列是先进先出。先来的元素先被处理,所以它适合处理“按层、按时间、按进入顺序推进”的问题。比如 BFS、任务队列、窗口里过期元素的清理。
刷这一类题时,我先问三个问题:
- 题目是不是在找“最近的未匹配对象”?如果是,优先想栈。
- 题目是不是要求“先进先出、按层推进、按时间顺序处理”?如果是,优先想队列。
- 题目是不是在一个滑动窗口里反复问最大值或最小值?如果是,优先想单调队列。
Python 里最常用的写法是:
1 | stack = [] # append / pop 当栈 |
不要用普通列表的 pop(0) 当队列。pop(0) 会移动后面所有元素,复杂度是 。如果需要从左边弹出,用 deque.popleft()。
这篇笔记按方法讲:先看普通栈,再看两个栈/队列互相模拟,然后看单调队列和优先队列。每一类都要说清楚容器里到底存的是什么,而不是只背 API。
2. 栈:处理最近还没匹配完的东西
栈最典型的信号是“遇到一个东西,先放着;遇到另一个东西,再和最近放着的那个配对”。括号匹配就是最直观的例子。
20. 有效的括号 给一个只包含括号的字符串,判断括号是否正确闭合。扫描字符串时,遇到左括号就入栈;遇到右括号时,它必须和栈顶的左括号匹配。为什么只看栈顶?因为括号必须就近闭合,最近打开的括号一定最先关闭。
1 | def is_valid(s: str) -> bool: |
这题容易错在只判断遇到右括号时是否匹配,却忘了最后还要检查栈是否为空。比如 "(((" 扫描时不会遇到错误的右括号,但它显然不合法,因为还有左括号没闭合。
1047. 删除字符串中的所有相邻重复项 也是栈题。题目要求不断删除相邻且相同的字符,直到不能再删。比如 "abbaca" 最后变成 "ca"。
这题看起来像字符串模拟,但核心是“当前字符能不能和最近保留的字符抵消”。最近保留的字符就是栈顶:
1 | def remove_duplicates(s: str) -> str: |
为什么这样能处理连续反应?因为删除一对字符后,新的相邻关系会自然暴露在栈顶。比如 abba:先放 a、b,遇到第二个 b 时弹出,最后一个 a 又能和栈顶 a 抵消。
844. 比较含退格的字符串 也可以用栈。# 表示退格,等价于删除最近输入且还没被删除的字符:
1 | def build(s: str) -> str: |
这类题的共同点是:操作影响的是“最近的一个有效元素”。只要看到最近、撤销、匹配、抵消,就先想栈。
3. 表达式与计算:栈保存还没结算的数字
表达式题里的栈通常存数字。扫描到运算符时,从栈里取出最近的两个数字做运算,再把结果放回去。
150. 逆波兰表达式求值 给一个后缀表达式,比如:
1 | ["2", "1", "+", "3", "*"] |
它表示 (2 + 1) * 3。后缀表达式的好处是没有括号优先级歧义:遇到数字就入栈,遇到运算符就弹出两个数字计算。
1 | def eval_rpn(tokens: list[str]) -> int: |
这里最容易错的是弹出顺序。先弹出的是右操作数 b,后弹出的是左操作数 a。减法和除法不能写反,a - b 和 b - a 完全不同。
另一个细节是 Python 的除法。题目要求向 0 截断,所以可以用 int(a / b)。如果用 a // b,负数时会向下取整,比如 -3 // 2 == -2,不符合向 0 截断的结果 -1。
栈在表达式题里承担的是“暂存还没被上层表达式消化的结果”。看到逆波兰、括号内计算、路径简化、最近结果合并,都可以往这个方向想。
4. 用栈模拟队列:改变弹出顺序
232. 用栈实现队列 要用两个栈实现先进先出的队列。一个栈负责输入,一个栈负责输出:
in_stack:新元素都先压到这里。out_stack:弹出元素时从这里弹。
当 out_stack 为空时,把 in_stack 里的元素全部倒过去。倒过去以后,原来最早进入的元素会跑到 out_stack 的栈顶,于是就能先进先出。
1 | class MyQueue: |
这题的关键不是“两个栈”,而是“什么时候倒”。不要每次 push 都倒,也不要每次 pop 都倒。只有当 out_stack 为空且需要取队头时,才把 in_stack 全部倒过去。这样每个元素最多进出两个栈一次,摊还复杂度是 。
举个过程:
1 | push 1, push 2, push 3 |
这个倒置过程正好把“后进先出”变成了“先进先出”。
5. 用队列模拟栈:保留最后进入的元素
225. 用队列实现栈 反过来,要求用队列实现后进先出的栈。常见写法是每次 push 后,把队列前面的旧元素依次转到队尾,让新元素永远排在队头。
1 | from collections import deque |
比如原来队列是 [1, 2],现在 push(3),先得到 [1, 2, 3]。为了让 3 最先弹出,把前面的 1、2 转到队尾,变成 [3, 1, 2]。这样 popleft() 就能弹出最新进入的元素。
这题和“用栈实现队列”的差别是:队列本身只能从头出、从尾进,所以想实现栈,就要在入队时调整顺序,让队头始终是最新元素。
真实刷题里,这两题更多是帮助理解栈和队列的顺序差异。面试时说明清楚每个结构承担的角色,比把代码背得很熟更重要。
6. 单调队列:窗口最大值只保留有竞争力的元素
普通队列按进入顺序排队,单调队列在这个基础上多维护一个性质:队列里的元素按某种单调顺序排列。
239. 滑动窗口最大值 给一个数组和窗口大小 k,要求返回每个窗口的最大值。如果每个窗口都重新扫一遍,复杂度是 。单调队列的思路是:窗口向右滑动时,只保留那些还有可能成为最大值的元素。
队列里通常存下标,而不是直接存值。原因是我们既要比较大小,也要判断下标是否已经滑出窗口。
1 | from collections import deque |
下面用 nums = [4, 2, 1, 3, 0]、k = 3 拆开这段代码。这个例子会同时出现两种删除:下标 1、2 因为不再有竞争力而从队尾弹出;下标 0 则因为离开窗口而从队首弹出。
读取 nums[i]
while ...: q.pop()
q.append(i)
if q[0] <= i-k: q.popleft()
ans.append(nums[q[0]])
这段代码维护队列时有三个核心动作:
第一,入队前从队尾弹出所有小于等于当前值的下标。因为当前元素更靠右、值还更大,前面那些元素以后不可能再成为最大值。
第二,把当前下标入队。队列保持从队头到队尾对应的值递减,所以队头永远是当前窗口最大值候选。
第三,检查队头是否过期。如果 q[0] <= i - k,说明这个下标已经不在窗口 [i-k+1, i] 里,要弹出。
为什么通常弹出 <= num,而不是 < num?两种都能做,但用 <= 会把相等的旧元素弹掉,保留更新的下标。更新的下标更晚过期,队列会更短一些。
这题最容易错的地方是过期判断。当前窗口右端是 i,长度是 k,左端就是 i - k + 1。所以过期条件是:
1 | q[0] < i - k + 1 |
等价写法就是:
1 | q[0] <= i - k |
单调队列不是把所有元素都存下来,而是删掉“已经没有竞争力”的元素。它适合窗口最大值、窗口最小值这类问题;如果窗口条件本身不是固定长度,就要小心是不是应该用滑动窗口、前缀和或堆。
7. 堆与优先队列:动态维护最大或最小值
有些题不是按照进入顺序处理元素,而是每次都要取出“当前最小”“当前最大”或“优先级最高”的元素。典型信号包括:
- 动态加入元素,同时反复查询或删除最大值、最小值。
- 求前
K个、第K大或第K小。 - 从多条有序序列中,每次取当前最小的候选。
- 按任务优先级而不是到达顺序处理任务。
这类问题通常使用优先队列,而优先队列最常见的实现就是堆。
7.1 优先队列和普通队列有什么区别
普通队列是一种先进先出的容器,谁先进入,谁先离开。优先队列不关心进入先后,每次优先取出优先级最高的元素。
| 结构 | 下一个离开的元素 | 常见实现 |
|---|---|---|
| 普通队列 | 最早进入的元素 | deque、循环数组 |
| 优先队列 | 优先级最高的元素 | 二叉堆 |
“优先队列”和“堆”不是完全相同的概念:
- 优先队列是一种抽象功能,规定了插入元素、查看最高优先级、删除最高优先级等操作。
- 堆是一种数据结构,可以高效实现这些功能。
- 优先队列也可以用有序数组、平衡树等结构实现,只是二叉堆最常见。
7.2 二叉堆:用数组保存一棵完全二叉树
算法题中的堆通常指二叉堆。它首先是一棵完全二叉树:除最后一层外,其余层都填满;最后一层的节点从左到右连续排列。
完全二叉树适合直接存进数组,不需要为每个节点保存左右指针。例如下面的小根堆:
1 | 数组:[1, 3, 2, 7, 6, 5, 4] |
对于下标 i,父子节点下标是:
1 | parent = (i - 1) // 2 |
这三个公式建立在数组下标从 0 开始的前提下。判断孩子是否存在时,还要检查下标是否小于 len(heap)。
堆只保证父子之间的大小关系,不保证整个数组有序。上面的数组中,3 出现在 2 前面并不违反小根堆性质;只要每个父节点都不大于它的孩子即可。
7.3 小根堆和大根堆
小根堆满足:
1 | 每个父节点 <= 它的孩子 |
因此堆顶是整棵树的最小值。大根堆则相反:
1 | 每个父节点 >= 它的孩子 |
因此堆顶是最大值。
| 类型 | 堆顶 | 常见用途 |
|---|---|---|
| 小根堆 | 最小值 | 前 K 大、合并有序序列、最短任务优先 |
| 大根堆 | 最大值 | 前 K 小、动态最大值 |
为什么“求前 K 大”反而维护小根堆?因为堆里只保留当前最大的 K 个元素,堆顶是其中最小的一个,也就是最应该被新候选淘汰的门槛。
7.4 插入时上浮,删除堆顶时下沉
向小根堆插入一个值时,先把它放到数组末尾,保持完全二叉树的形状。新值可能小于父节点,因此不断和父节点交换,这个过程叫上浮。
1 | def heappush_min(heap: list[int], value: int) -> None: |
删除小根堆堆顶时,不能直接删除数组第一个元素,否则后面的所有元素都会移动。通常这样处理:
- 保存堆顶答案。
- 取出数组末尾元素并放到堆顶。
- 把新的堆顶和两个孩子中更小的那个交换。
- 重复交换,直到父子关系恢复,这个过程叫下沉。
1 | def heappop_min(heap: list[int]) -> int: |
下沉时必须和两个孩子中更小的那个交换。如果只看到左孩子更小就立刻交换,可能让父节点落到一个仍然大于右孩子的位置,堆性质就会被破坏。
下面把上浮和下沉拆成两条可切换的动画。树中的节点和下方数组是同一份数据;节点交换时,数组里的对应位置也会同步变化。
7.5 堆操作的复杂度
含有 n 个节点的完全二叉树高度是 。上浮和下沉最多走过一条从叶子到根或从根到叶子的路径,因此:
| 操作 | 时间复杂度 | 原因 |
|---|---|---|
| 查看堆顶 | 堆顶就是数组下标 0 | |
| 插入元素 | 末尾插入后向上调整 | |
| 删除堆顶 | 末尾补到堆顶后向下调整 | |
建堆 heapify |
从最后一个非叶子节点开始下沉 | |
逐个插入 n 个元素 |
每次插入都可能上浮 |
heapify 是 ,不是 。虽然单次下沉最坏是 ,但靠近底部的大量节点几乎不需要移动,所有节点的实际调整高度相加是线性的。
7.6 Python 的 heapq
Python 的 heapq 直接把普通列表原地维护成小根堆:
1 | import heapq |
已有一批数据时,用 heapify 一次建堆:
1 | nums = [7, 2, 5, 1, 9] |
常用接口可以这样区分:
| 接口 | 含义 |
|---|---|
heappush(heap, x) |
插入 x |
heappop(heap) |
删除并返回最小值 |
heapify(nums) |
把列表原地变成堆 |
heappushpop(heap, x) |
先加入 x,再弹出最小值 |
heapreplace(heap, x) |
先弹出原堆顶,再加入 x;要求堆非空 |
Python 常用取负数模拟大根堆:
1 | max_heap = [] |
堆里也可以放元组。Python 会先比较元组第一项,第一项相同再比较第二项,因此 (priority, item) 很适合表示“按优先级出队”。如果第二项对象不能互相比较,可以增加一个不会重复的序号:
1 | (priority, sequence, item) |
不要把堆数组误当成完整排序结果。只有 heap[0] 一定是最小值,其他位置只满足堆的父子关系;如果需要完整有序序列,必须反复 heappop 或另外排序。
7.7 前 K 个高频元素:小根堆保留最大的 K 个
347. 前 K 个高频元素 要返回出现频率最高的 k 个元素。可以先用 Counter 统计频率,再维护一个大小为 k 的小根堆。堆里存 (freq, num),频率最小的在堆顶。只要堆大小超过 k,就弹出频率最小的那个。
1 | from collections import Counter |
为什么用小根堆?因为我们要保留频率最大的 k 个元素。堆大小超过 k 时,最该淘汰的是当前堆里频率最小的元素,小根堆正好能用 的时间弹出它。
设数组长度为 n,不同数字数量为 u:统计频率是 ,每个不同数字最多进行一次入堆和出堆,堆大小不超过 k,所以总时间是 ,额外空间是 。
如果题目要求返回有序结果,再对答案排序;但如果只要求任意顺序,直接返回堆里的元素即可。
这类题的判断信号是“前 K 个”“第 K 大”“动态最大/最小”。如果一次性完整排序也可以解决,复杂度通常是 ;只维护大小为 k 的堆,通常可以减少到 。
8. Python 里怎么选容器
刷栈与队列题时,Python 容器选择可以简单记:
1 | stack = [] |
列表末尾入栈出栈都是 平均复杂度,很适合当栈。
1 | from collections import deque |
deque 适合两端操作,append、appendleft、pop、popleft 都是 。普通 list.pop(0) 是 ,不要在队列题里随手用。
1 | import heapq |
heapq 适合动态最值,每次入堆和出堆是 。它不是队列的先进先出,而是按优先级出队。
堆与图搜索结合的典型题是 407. 接雨水 II:小根堆始终取出当前最低的边界,再用 BFS 从这条边界向二维网格内部扩展;完整解释见图论笔记。
真正写题时,不要只问“该用哪个库”,要问容器里存什么:
- 栈里存字符、数字,还是下标?
- 队列里存节点、坐标,还是下标?
- 单调队列里存值还是下标?
- 堆里存单个值,还是
(优先级, 元素)?
容器的角色说清楚,代码基本就稳了。
9. 复习总览
- 栈解决“最近的未匹配对象”:括号、撤销、抵消、表达式计算。
- Python 里用
list当栈,append入栈,pop出栈。 - 有效括号:遇到左括号入栈,遇到右括号必须匹配栈顶,最后栈要为空。
- 删除相邻重复项:当前字符和栈顶相同就弹出,否则入栈。
- 逆波兰表达式:遇到数字入栈,遇到运算符弹出
b和a,注意顺序是a op b。 - 用栈实现队列:
in_stack负责输入,out_stack负责输出,只有out_stack空时才倒数据。 - 用队列实现栈:可以在
push后旋转队列,让最新元素到队头。 - 队列先进先出,Python 里用
deque,不要用list.pop(0)。 - 单调队列用于固定窗口最大/最小值,队列里通常存下标。
- 滑动窗口最大值:入队前弹掉队尾更小的元素,队头过期就弹出,队头就是最大值。
- 优先队列按优先级出队,二叉堆是它最常见的实现。
- 二叉堆用数组保存完全二叉树;父节点、左孩子、右孩子下标分别是
(i-1)//2、2*i+1、2*i+2。 - 小根堆的父节点不大于孩子,堆顶是最小值;插入时上浮,删除堆顶后下沉。
- 查看堆顶是 ,插入和删除堆顶是 ,
heapify建堆是 。 - Python 的
heapq默认维护小根堆,大根堆通常用负数模拟。 - 前 K 高频元素:
Counter统计频率,小根堆保留最大的k个频率。
栈和队列的本质是顺序控制。栈关注“最近”,队列关注“最早”,单调队列关注“窗口里谁还有资格成为答案”,堆关注“当前优先级最高或最低”。复习时把这个顺序关系说清楚,比单纯背代码更可靠。





