LeetCode（十）：栈与队列

栈和队列看似平凡，尤其在图算法或动态规划面前更显不起眼，但它们却是面试题中的常客——因为大多数算法问题最终都归结于访问顺序的考察。栈遵循后进先出（LIFO）原则，而队列则是先进先出（FIFO）。加上单调栈、双端队列、优先队列等变体，许多经典问题如括号匹配、下一个更大元素、滑动窗口最值、前 K 大、 BFS 等都能通过它们高效解决。

这篇文章将从头到尾梳理相关内容：首先讲解基础数据结构的原理，然后通过六道典型的 LeetCode 题目逐步演示解法，最后附上一张复杂度对比表和一个针对常见错误的 Q&A 环节。

一、栈与队列基础#

栈：后进先出#

栈是一种线性数据结构，特点是“后进先出”（LIFO）。可以把它想象成一摞盘子：新盘子总是放在最上面，拿的时候也从顶上开始。接口非常简洁：

• push(x)：把元素 x 压入栈顶
• pop()：弹出栈顶元素并返回
• peek() 或 top()：查看栈顶元素，但不移除
• empty() 和 size()：检查是否为空或获取当前大小

这些操作的时间复杂度都是 O(1)。栈的核心优势在于它的访问模式——它天然适合解决“最近一次遇到的 X 是什么”这类问题。

在 Python 中，通常直接用 list 实现栈，因为它的 append 和末尾 pop 都是均摊 O(1) 的操作：

1
2
3
4
5
6

stack = []
stack.append(1)        # push
stack.append(2)
top = stack[-1]        # peek -> 2
val = stack.pop()      # pop  -> 2
empty = not stack

Java 中推荐使用 ArrayDeque，它比老旧的 Stack 类更高效，行为也更规范：

1
2
3
4

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
int top = stack.peek();
int val = stack.pop();

C++ 则可以直接使用标准库中的 stack：

1
2
3
4
5

#include <stack>
std::stack<int> st;
st.push(1);
int top = st.top();
st.pop();

队列：先进先出#

队列（Queue）的特点是“先进先出”：最早进的元素最先出来。就像排队买咖啡，先到的人先拿到咖啡。它的基本操作很简单：

• enqueue(x) / offer(x)：把元素加到队尾
• dequeue() / poll()：从队首取出元素
• peek() / front()：查看队首元素但不移除
• empty()、size()：判断是否为空或获取当前大小

如果用 Python 的 list 模拟队列，表面上没问题，但性能会拖后腿——pop(0) 是 O(n)，因为每次操作都会让后续所有元素往前挪。稍微复杂一点的场景，比如 BFS，很容易超时。更好的选择是 collections.deque，它在两端的操作都是 O(1)：

1
2
3
4
5
6

from collections import deque
q = deque()
q.append(1)            # 入队
q.append(2)
front = q[0]           # 查看队首 -> 1
val = q.popleft()      # 出队 -> 1

Java 中推荐用 ArrayDeque（通过 offer 和 poll 方法当作队列）， C++ 则直接有 std::queue<int>。

一个简单的记忆方法：栈是函数调用历史，队列是待办任务列表。 BFS、 DFS、撤销/重做、任务调度、括号匹配——这些场景该用哪个数据结构，按这句话基本就能对号入座。

二、栈的经典题#

LeetCode 20 —— 有效的括号#

给定一个只包含 ()[]{} 的字符串 s，判断它是否合法。

核心规则是嵌套匹配：每当遇到右括号时，它必须和最近的一个未闭合左括号配对。这里的“最近”正好对应栈的特性。

算法思路：从头到尾扫描字符串。遇到左括号就压入栈；遇到右括号时，检查栈是否为空以及栈顶是否是对应的左括号——如果不符合，直接判定为非法。最后扫完字符串后，栈必须为空，否则说明有未闭合的左括号。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def isValid(s: str) -> bool:
    stack = []
    pairs = {")": "(", "}": "{", "]": "["}
    for ch in s:
        if ch in pairs:                       # 右括号
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:                                  # 左括号
            stack.append(ch)
    return not stack

下图展示了字符串 ({[]}) 的执行过程，每列代表一步操作：上方是当前读取的字符，下方是这步操作后的栈状态。可以看到栈先增长到深度 3，然后对称地逐步清空。

复杂度分析：每个字符最多进栈一次、出栈一次，时间复杂度是 O(n)，空间复杂度在最坏情况下（全是左括号）也是 O(n)。

常见错误：

• 忘了在 pop 前检查栈是否为空，空栈调用 pop 会抛异常。
• 别因为某次匹配成功就提前返回结果，必须完整扫描整个字符串。
• 扫描结束后别忘了检查栈是否为空，像 ((( 这种情况不检查就会误判为合法。

LeetCode 155 —— 最小栈#

设计一个栈，支持 push、pop、top，并且能在 O(1) 时间内获取当前栈中的最小值。

如果每次调用 getMin 都去遍历栈找最小值，时间复杂度是 O(n)，显然不够高效。要实现 O(1) 的 getMin，关键在于记录每个状态下的最小值。最直接的做法是把每个元素和它入栈时的最小值绑定在一起，存成一个二元组。

代码实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class MinStack:
    def __init__(self) -> None:
        self.stack: list[tuple[int, int]] = []

    def push(self, val: int) -> None:
        # 当前最小值是新值和栈顶最小值的较小者
        cur_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, cur_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

四个操作的时间复杂度都是 O(1)，额外的空间开销也很小——每个元素只多存了一个整数。

还有一种“双栈写法”也能解决问题：一个栈存数据，另一个栈存最小值。不过这种写法容易踩坑，尤其是当栈中出现重复最小值时。比如，push 时需要判断 <= 而不是 <，否则重复的最小值会被忽略；pop 时也要小心，只有弹出的值等于当前最小值时才更新辅助栈，否则数据会不一致。相比之下，二元组的写法更简洁，逻辑也更清晰。

LeetCode 150 —— 逆波兰表达式求值#

后缀表达式把运算符放在操作数后面，省掉了括号。比如 ((2 + 1) * 3) 写成 2 1 + 3 *。核心思想很简单：栈里存的是等待处理的操作数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def evalRPN(tokens: list[str]) -> int:
    stack: list[int] = []
    ops = {"+", "-", "*", "/"}
    for tok in tokens:
        if tok in ops:
            b = stack.pop()                # 先弹出的是右操作数
            a = stack.pop()
            if   tok == "+": stack.append(a + b)
            elif tok == "-": stack.append(a - b)
            elif tok == "*": stack.append(a * b)
            else:            stack.append(int(a / b))   # 向零取整
        else:
            stack.append(int(tok))
    return stack[0]

这里有两个常见的坑：

• 操作数顺序：栈是后进先出的，第一个 pop 出来的是右操作数。搞反了，a - b 就会变成 b - a，结果肯定不对。
• 除法处理：题目要求结果向零截断， C 风格的 -7 / 2 是 -3，但 Python 的 // 是向下取整（-7 // 2 是 -4）。所以用 int(a / b)，让浮点除法结果转成整数时自动向零截断。

三、单调栈#

单调栈其实就是加了个限制条件的普通栈：栈内元素必须保持单调性，要么递增，要么递减。每当新元素加入时，如果会破坏这个单调性，就先把那些“碍事”的元素弹出去。就这么一条简单的规则，却能把很多看似需要 O(n²) 暴力解法的问题优化到摊还 O(n) 的复杂度——因为每个元素最多只会进栈和出栈一次。

这种数据结构特别适合解决以下四类问题：

• 找右侧第一个比自己大的元素 → 用递减栈
• 找右侧第一个比自己小的元素 → 用递增栈
• 找左侧第一个更大或更小的元素 → 逻辑类似，只需从右往左扫描即可

简单来说，单调栈的核心就是通过维护一个有序的栈，快速找到某个方向上的“最近满足条件”的元素。

LeetCode 739 —— 每日温度#

给一个温度数组 temperatures，对每一天 i，返回“还要等几天才能遇到更暖的一天”。如果之后再也不会更暖，就返回 0。

暴力解法是经典的 O(n²) 双重循环。换成单调栈后，栈里存的是下标，对应的温度从栈底到栈顶递减。每读到一天的温度，如果它比栈顶对应的温度高，说明栈顶等的就是这一天——弹出栈顶，填入答案 answer[idx] = i - idx，重复直到栈为空或当前温度不再更高。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack: list[int] = []                     # 存下标，对应温度递减
    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

下图展示了这个过程。每条绿色弧线表示“某天终于等到更暖的一天”，底部一行显示了每一步之后的栈状态，可以看到栈里的温度始终是递减的。

复杂度：每个下标最多进栈一次、出栈一次，虽然有内外两层循环，但总操作数是 O(n)，空间复杂度也是 O(n)。

注意点：栈里存的是下标而不是温度值，因为计算答案时既需要温度（用来比较），也需要位置（用来求差）。

四、队列与 BFS#

提到队列，最经典的应用就是广度优先搜索（BFS）：先探索离起点距离为 1 的节点，再扩展到距离为 2 的节点，依此类推。核心代码非常简洁，八行就能搞定：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from collections import deque

def bfs(start, neighbours_of):
    seen = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        # ... 处理 node ...
        for nb in neighbours_of(node):
            if nb not in seen:
                seen.add(nb)
                q.append(nb)

写 BFS 时有两条黄金法则，几乎适用于所有题目：

• 入队时标记访问状态，不要等到出队才标记。 否则同一个节点可能被重复加入队列，导致时间和空间复杂度飙升。
• 用 deque 实现队列，别用 list。 list.pop(0) 的时间复杂度是 O(n)，直接把原本 O(V+E) 的 BFS 拖成 O(V·(V+E))。

层序遍历（比如 LeetCode 102）其实就是 BFS 加一个小技巧：每轮开始前记录下当前队列的长度 len(q)，这样就能知道这一层有多少个节点，处理完一层就生成一个子列表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def levelOrder(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):                # 关键：提前固定当前层的节点数
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

五、优先队列与堆#

优先队列（Priority Queue）故意不按 FIFO 规则出队，而是每次取出优先级最高（或最低）的元素。它的标准实现是二叉堆——一棵完全二叉树，用数组存储，最小堆要求每个父节点都不大于自己的子节点。

因为用数组存，父子节点的关系完全靠下标计算，不需要指针：

• 下标 i 的父节点是 (i - 1) // 2
• 它的两个子节点分别是 2*i + 1 和 2*i + 2

这种设计让 heappush 和 heappop 的复杂度都是 O(log n)，取堆顶（peek）是 O(1)，而从一个现成数组建堆更是高效到 O(n)。

Python 的 heapq 模块默认是最小堆。如果需要最大堆，可以将 key 取反后插入堆中。

LeetCode 347 —— 前 K 个高频元素#

找出数组 nums 中出现频率最高的前 k 个元素。

这题有三种解法，按巧妙程度从低到高排列：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import heapq
from collections import Counter

# (1) 用大小为 k 的最小堆。时间复杂度 O(n log k)，空间复杂度 O(n + k)
def topKFrequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    heap: list[tuple[int, int]] = []          # 堆里存 (频次, 值)
    for val, f in freq.items():
        heapq.heappush(heap, (f, val))
        if len(heap) > k:
            heapq.heappop(heap)               # 踢掉当前堆里频次最低的
    return [v for _, v in heap]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# (2) 桶排序。时间复杂度 O(n)，空间复杂度 O(n)
def topKFrequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
    for v, f in freq.items():
        buckets[f].append(v)
    out: list[int] = []
    for f in range(len(buckets) - 1, 0, -1):
        out.extend(buckets[f])
        if len(out) >= k:
            return out[:k]
    return out

最小堆的思路非常通用，不只是用来找前 K 高频元素。比如 合并 K 个升序链表（每条链表的头节点进堆）、数据流中的第 K 大元素、 Dijkstra 最短路径算法，这些场景都用的是同一个套路。

六、双端队列：滑动窗口最大值#

双端队列（Deque）允许在两端做 O(1) 的插入和删除。当一道滑动窗口题问“当前窗口的极值是多少”时，它就是最优解。

LeetCode 239 —— 滑动窗口最大值#

给定一个数组 nums，以及一个长度为 k 的滑动窗口，从左到右在数组上滑动这个窗口，返回每个窗口内的最大值。

核心思想是用一个单调递减的双端队列来存储数组下标。这样可以保证队首始终是当前窗口的最大值所在位置：

• 如果队首下标已经不在窗口范围内（dq[0] <= i - k），直接从队列前面移除；
• 在将当前下标 i 加入队列之前，从队列尾部移除所有对应值小于 nums[i] 的下标——这些值在当前窗口中永远不可能成为最大值；
• 当前窗口的最大值就是 nums[dq[0]]。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()
    out: list[int] = []
    for i, x in enumerate(nums):
        # 1. 移除已经不在窗口范围内的下标
        if dq and dq[0] <= i - k:
            dq.popleft()
        # 2. 保持队列单调递减
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        # 3. 窗口形成后开始记录结果
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

每个下标最多进队一次、出队一次，因此总时间复杂度是 O(n)。如果用暴力解法，每次重新扫描窗口内的元素，复杂度会达到 O(n·k)。为什么不选堆？因为堆无法高效地删除刚刚滑出窗口的元素——只能通过延迟删除实现，复杂度会退化为 O(n log n)。而单调队列两端操作都是 O(1)，这才实现了真正的线性复杂度。

七、互相实现：栈与队列的桥#

下面这两道题在系统设计面试里经常作为热身出现，因为它们考的是你对访问模式到底有没有真正想清楚。

LeetCode 232 —— 用栈实现队列#

队列是先进先出（FIFO），而栈是后进先出（LIFO）。要让栈模拟队列，关键在于反转两次顺序：第一次从输入栈倒到输出栈时，顺序就恢复成了 FIFO。我们用两个栈分工合作：输入栈负责接收新元素，输出栈负责提供弹出操作。当需要执行 pop 或 peek 时，如果输出栈为空，就把输入栈的内容全部倒过去；否则直接操作输出栈。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class MyQueue:
    def __init__(self) -> None:
        self.in_stk: list[int] = []
        self.out_stk: list[int] = []

    def push(self, x: int) -> None:
        self.in_stk.append(x)

    def pop(self) -> int:
        self._shift()
        return self.out_stk.pop()

    def peek(self) -> int:
        self._shift()
        return self.out_stk[-1]

    def empty(self) -> bool:
        return not self.in_stk and not self.out_stk

    def _shift(self) -> None:
        if not self.out_stk:
            while self.in_stk:
                self.out_stk.append(self.in_stk.pop())

push 操作的时间复杂度是 O(1)，因为只是简单地往输入栈里加元素。pop 和 peek 的时间复杂度是摊还 O(1)：虽然某次倒灌可能涉及多个元素的搬运，但每个元素从进入输入栈到被移出输出栈，最多只会经历一次倒灌。因此， n 次操作的总成本是 O(n)，分摊下来每次操作平均为 O(1)。

LeetCode 225 —— 用队列实现栈#

反过来用队列模拟栈就没那么优雅了，主要问题出在旋转操作的开销上。最简单的实现是只用一个队列：每次插入新元素后，把前面 n - 1 个元素依次弹出并重新放回队尾。这样一来，新插入的元素就被挪到了队首。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from collections import deque

class MyStack:
    def __init__(self) -> None:
        self.q: deque[int] = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return not self.q

这里 push 的时间复杂度是 O(n)，而 pop 和 top 都是 O(1)。这种不对称性其实揭示了一个本质：队列和栈的访问模式完全不同， LIFO 的特性需要专门的机制来支持，强行用队列模拟栈效率注定不高。

八、复杂度速查表#

按算法分类的总结：

• 括号匹配 / 逆波兰表达式求值：时间 O(n)，空间 O(n)
• 单调栈（找下一个更大/更小元素）：时间 O(n)，空间 O(n)
• BFS （V 个顶点， E 条边）：时间 O(V + E)，空间 O(V)
• 单调队列解决滑动窗口最值问题：时间 O(n)，空间 O(k)
• 用大小为 K 的最小堆求 Top-K：时间 O(n log k)，空间 O(n)

九、常见问题#

Q1： Python 实现队列时为什么推荐用 deque 而不是 list？

list.pop(0) 的时间复杂度是 O(n)，因为删除头部元素后，后续所有元素都要向前移动。而 deque.popleft() 是 O(1)。对于像 BFS 这种频繁操作队列的场景，这不是简单的常数优化，而是直接关系到算法的渐进复杂度。

Q2：什么时候该用单调栈？

如果题目要求“对每个下标 i，找到它左边/右边第一个比它大/小的元素”，这种问题暴力解法通常是 O(n²)。用单调栈可以将复杂度降到 O(n)，因为它通过维护栈内元素的有序性避免了重复比较。

Q3：如何用 Python 的 heapq 实现最大堆？

heapq 默认是最小堆，实现最大堆可以通过插入时取负号，取出时再还原。比如插入 -x，取出时取反。如果是带优先级的元组，可以用 (-priority, value)，这样最大优先级会变成最小负数，符合最小堆的排序规则。

Q4：滑动窗口最大值为什么用单调队列而不是堆？

堆虽然能以 O(log n) 获取当前最大值，但它无法高效地删除“刚刚滑出窗口”的元素——只能延迟删除，导致复杂度退化为 O(n log n)。而单调队列在窗口滑动时，前面过期的下标可以直接 O(1) 弹出，后面不符合条件的元素也能 O(1) 移除，整体复杂度保持在 O(n)。

Q5：求 Top K 大的元素用最小堆还是最大堆？

用 大小为 K 的最小堆。当堆中元素达到 K 个后，每来一个新元素，如果比堆顶大就替换堆顶；堆顶始终是当前 K 个元素中最小的那个，新来的元素只要“比这个垫底的还小”就可以直接丢弃。反过来，求 Top K 小的元素则用最大堆。

Q6：“用两个栈实现队列”的摊还复杂度为什么是 O(1)？

每个元素从输入栈到输出栈最多只会被搬移一次。 n 次操作下来，总搬运次数是 O(n)，因此平均每次操作的复杂度是 O(1)。虽然单次 pop 可能触发大量搬运，但从整体来看，均摊成本仍然是常数级别。

Q7：树或图的遍历应该用栈还是队列？

栈（或者递归）对应深度优先搜索（DFS），特点是沿着一条路径走到尽头，再回溯换另一条路。队列对应广度优先搜索（BFS），按距离起点的层数一层一层访问。两者探索的是同一张图，但顺序不同，适用场景也不同：如果只需要“任意一条路径”， DFS 更方便；如果需要“最短路径”，那就必须用 BFS。

十、总结#

总结一下核心要点：

• 栈：处理“最近一个还没搞定的东西”。
• 队列：按到来顺序依次处理。
• 单调栈：在“最近”的基础上加个比较条件，把 O(n²) 优化到 O(n)。
• 双端队列：两头都要操作；适合滑动窗口最值、带限制的历史记录管理。
• 优先队列：不管顺序，只看优先级；解决 Top-K、任务调度、 Dijkstra 等问题。

只要题目能对上这五句话中的某一句，代码实现基本就是套模板。面试时的难点其实在于识别该用哪个结构，剩下的工作交给数据结构本身就能搞定。