栈和队列在数据结构里看起来很不起眼，可一旦真做起算法题，会发现它们出现的频率高得惊人。原因其实只有一句：大部分题目本质上都是在问访问顺序——栈是后进先出（LIFO），队列是先进先出（FIFO），再加上单调栈、双端队列、优先队列这几个变体，括号匹配、下一个更大元素、滑动窗口最值、前 K 大、BFS、还有一票"用 X 实现 Y"的题，几乎全在它们的射程之内。

这一篇会把这几样东西一次讲完。先把基础数据结构本身讲清楚，再用六道有代表性的 LeetCode 题完整跑一遍流程，最后给一张复杂度对照表，外加一个集中回答常见疑问的 Q&A 部分。

系列导航

LeetCode 算法刷题手册（共 10 篇）：

哈希表 —— Two Sum、最长连续序列、字母异位词
双指针 —— 对撞指针、快慢指针、滑动窗口
链表操作 —— 反转、判环、合并
二叉树遍历与递归 —— 前/中/后序、最近公共祖先
动态规划入门 —— 一维/二维 DP，状态转移
回溯算法 —— 排列、组合、剪枝
二分查找进阶 —— 整数/实数/答案二分
滑动窗口 —— 定长与变长窗口
栈与队列 —— 单调栈、优先队列、双端队列 ← 本篇
贪心与位运算 —— 贪心策略、位运算技巧

一、栈与队列基础

1.1 栈：后进先出

栈（Stack）是一种线性容器，最后进去的元素最先出来。直观的类比就是叠盘子：只能从顶上放，也只能从顶上拿。接口很小：

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();

1.2 队列：先进先出

队列（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)            # enqueue
q.append(2)
front = q[0]           # peek -> 1
val = q.popleft()      # dequeue -> 1

Java 一般也用 ArrayDeque（通过 offer / poll 当队列用），C++ 用 std::queue<int>。

一句话的记忆模型：栈是函数调用历史，队列是待办任务列表。BFS、DFS、撤销/重做、任务调度、括号匹配——它们各自该用哪个，凭这一句就能判断个八九不离十。

二、栈的经典题

2.1 LeetCode 20：有效的括号

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

合法的核心规则是嵌套：遇到一个右括号，它必须匹配最近一次没被关闭的那个左括号。“最近"两个字就是栈的语义。

算法：扫一遍字符串。遇到左括号就 push；遇到右括号则要求栈非空、且栈顶恰好是匹配的左括号——否则直接判错。扫完之后还要再验一次：栈必须为空，否则说明有左括号没关掉。

 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 之前必须先判 not stack，否则空栈 pop 会报错。
不要因为某一步匹配成功就提前返回，要把整串都扫完。
循环结束后必须再判一次栈是否为空，否则像 ((( 这种就会被误判为合法。

2.2 LeetCode 155：最小栈

设计一个栈，除了常规的 push、pop、top，还要能用 O(1) 时间拿到当前最小值。

如果每次都遍历找最小，那是 O(n)；要做到 O(1)，就必须把"每个深度对应的最小值"都记下来。最简洁的写法是把每个元素和"截至此时的最小值"打包成一个二元组：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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 时也只在弹出值等于当前最小值时才 pop 辅助栈，否则数据会对不上。

2.3 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()                # 先 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)，让浮点除法+int 做截断。

三、单调栈

单调栈就是在普通栈上加了一条规矩：栈里的元素必须保持单调（要么严格递增，要么严格递减）。一旦新元素会破坏这条不变量，就先把破坏者们都 pop 掉。这一条小小的纪律就能把"对每个 i，向后/向前找第一个满足某条件的 j"这类题，从看起来 O(n²) 的暴力降到摊还 O(n)——因为每个下标最多入栈、出栈各一次。

它能套住的题型主要有四类：

右侧第一个比自己大的元素 → 维护递减栈
右侧第一个比自己小的元素 → 维护递增栈
左侧第一个更大/更小的元素 → 同样的逻辑，反向扫一遍即可

3.1 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

队列最有名的工作就是广度优先搜索：先访问所有距离为 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 有两条铁律，几乎所有题都通用：

入队就标记 visited，不要等到出队才标。 否则同一个节点可能被多次入队，时间和内存都会爆。
用 deque，不要用 list。 list.pop(0) 是 O(n)，一不小心就把 O(V+E) 的 BFS 拖成 O(V·(V+E))。

层序遍历（LeetCode 102）只是 BFS 多了一个小技巧：每一轮开始前先把 len(q) 记下来，这样就知道这一层有多少个节点，一层处理完就 append 一组结果。

 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 取反塞进去。

5.1 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 大、Dijkstra 最短路，全是同一招。

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

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

6.1 LeetCode 239：滑动窗口最大值

长度为 k 的窗口在 nums 上从左滑到右，输出每个窗口的最大值。

诀窍是维护一个单调递减的双端队列，存的是下标：

当队首下标已经离开窗口（dq[0] <= i - k），从前面 pop 掉；
在 push 当前下标 i 之前，先从后面 pop 掉所有值小于 nums[i] 的下标——它们在 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) 弹，才能把它压回真正的 O(n)。

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

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

7.1 LeetCode 232：用栈实现队列

队列要 FIFO，栈是 LIFO。把数据反转两次就回到了原始顺序，于是用两个栈：一个输入栈专门接收 push，一个输出栈专门服务 pop。当 pop 发现输出栈是空的，就把输入栈整体倒灌进来；否则直接 pop 输出栈顶。

 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)。某一次 pop 可能很贵，但平均仍然便宜。

7.2 LeetCode 225：用队列实现栈

反方向就丑得多，因为旋转的代价摆在那。最简单的写法是只用一个队列：每次 push 之后，把队列里前 n - 1 个元素都从前面 pop 出来再 append 到后面，这样新元素就被旋转到了队首。

 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 的纪律本质上要靠不一样的机器才能高效维持。

八、复杂度速查表

容器	push / enqueue	pop / dequeue	peek	search
栈	O(1)	O(1)	O(1)	O(n)
队列（基于 deque）	O(1)	O(1)	O(1)	O(n)
双端队列	两端 O(1)	两端 O(1)	O(1)	O(n)
最小/最大堆	O(log n)	O(log n)	O(1)	O(n)
由数组 `heapify` 建堆	O(n) 一次性	—	—	—

按算法分类的总结：

括号匹配 / 逆波兰求值：时间 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)

九、Q&A

Q1：Python 写队列为什么必须用 deque 而不是 list？

list.pop(0) 是 O(n)，因为后面所有元素都要往前挪一格。deque.popleft() 是 O(1)。BFS 这类队列重度操作的场景，这不是常数差距，是渐进复杂度的差距。

Q2：什么时候要换成单调栈？

题面长得像"对每个下标 i，向左/向右找第一个比它大/小的下标"。把这种暴力 O(n²) 的扫法用单调栈写一遍就能压到 O(n)。

Q3：Python 的 heapq 怎么做最大堆？

push 时取负号，pop 完再取一次负号还原。如果是带优先级的元组，写 (-priority, value)，最大优先级就变成最小负数。

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

堆能 O(log n) 给你当前最大值，但它没法便宜地删除"刚刚滑出窗口"的那个元素——只能延迟删除，复杂度被拖到 O(n log n)。单调队列前面 O(1) 弹掉过期下标，后面 O(1) 弹掉无用下标，整体真正 O(n)。

Q5：Top K 大用最小堆还是最大堆？

大小为 K 的最小堆。堆里凑够 K 个之后，每来一个比堆顶大的就替换堆顶；堆顶始终是当前 K 个最佳里最小的那个，新来的只要"比这个垫底的还小"就直接淘汰。反过来，“Top K 小"用大小为 K 的最大堆。

Q6：为什么"用两个栈实现队列"是摊还 O(1)？

每个元素从入到出最多被从输入栈搬到输出栈一次。n 次操作的总搬运量是 O(n)，所以平均每次 O(1)。虽然单次 pop 可能突然搬一大堆，但平均下来仍然便宜。

Q7：树/图遍历该用栈还是队列？

栈（或者递归）对应 DFS——一条路走到黑，再回溯。队列对应 BFS——按和起点的距离一层一层访问。两种顺序探索的是同一张图，但回答的问题不一样：要"任意一条路径"通常 DFS 顺手；要"最短路径"必须 BFS。

十、小结

把上面这些东西压成几句话就是：

栈：你需要"最近一次还没解决的那个东西”。
队列：你需要按到达顺序处理。
单调栈：“最近"还要满足某种比较不变量，把 O(n²) 压成 O(n)。
双端队列：两端都要操作；滑动窗口最值、限长撤销/重做。
优先队列：顺序无关，优先级才重要；Top-K、调度、Dijkstra。

题目一旦能映射到上面五句话之一，写代码基本就是机械的事。面试时大部分功夫都花在"识别该用哪个"上，数据结构本身只是把活干掉而已。

LeetCode（十）—— 栈与队列