核心 · 算法第 4 课 / 共 8 课免费阅读

栈与队列 · 数据结构与算法

什么时候需要栈，什么时候需要队列？

课程目录

为什么需要它

撤销按钮、浏览器的后退键、代码里括号的配对、程序里的函数调用，用的都是栈。打印任务、消息队列、广度优先搜索用的是队列。选对了，很多题目会变得很短。

直觉理解

栈：后进先出（LIFO），像一摞盘子。Python 里：用列表的 append() 和 pop()。
队列：先进先出（FIFO），像商店门口排队。Python 里：用 collections.deque 的 append() 和 popleft()。

不要用 list.pop(0) 做队列：它要把其他元素全挪一位，每次 O(n)。deque.popleft() 是 O(1)。

定义

栈 Stack

A collection where you add and remove at the same end (the top). Last in, first out.
只在同一端（栈顶）添加和删除的集合。后进先出。

队列 Queue

A collection where you add at the back and remove from the front. First in, first out.
从队尾添加、从队头删除的集合。先进先出。

示例

括号是否配对

动手试试

遇到开括号就压栈；每个闭括号必须和栈顶配对。

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(balanced("f(a[1]) {x}"))
print(balanced("f(a[1)]"))

逐步执行

L6开括号在栈里等着。
L8最近的那个开括号必须配得上。
L10栈里还剩开括号，说明有没关上的。
L13) 遇到栈顶的 [：配不上。False

任务队列

动手试试

按到达顺序处理任务。需要再来一轮的任务排到队尾。

from collections import deque

jobs = deque([("print", 2), ("email", 1), ("backup", 3)])
while jobs:
    name, rounds = jobs.popleft()
    print("run", name)
    if rounds > 1:
        jobs.append((name, rounds - 1))

逐步执行

L5从队头取。
L8没做完的任务重新排到队尾。
L6顺序：print、email、backup、print、backup、backup。

常见错误

对空栈 pop()

[].pop() 会报 IndexError。先检查 if stack，就像 balanced() 里那样。

用 list.pop(0) 做队列

能用，但每次都是 O(n)。有 10 万个元素时，用 deque。

小测验

1. 这段代码会输出什么？

stack = []
for x in [1, 2, 3]:
    stack.append(x)
stack.pop()
stack.append(4)
print(stack.pop(), stack)

A
```
4 [1, 2]
```
B
```
3 [1, 2, 4]
```
C
```
1 [2, 4]
```

查看答案

答案：A

压入 1、2、3；弹出 3；压入 4；弹出 4，剩下 [1, 2]。

2. 浏览器后退键会回到你最近访问的那一页。哪种结构合适？

A栈
B队列
C集合

查看答案

答案：A

最近的页面最先回来：后进先出。

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

预测输出撤销
准确写出这段程序的输出。
改需求用真正的队列
serve(n) 让顾客 1…n 排队，按顺序服务，返回服务顺序的列表。pop(0) 让它变成 O(n²)。改用 collections.deque 和 popleft()。
从零写计算后缀表达式
后缀表达式里运算符写在数字后面："3 4 + 2 *" 表示 (3 + 4) × 2。写函数 postfix(expr)：按空格切开；数字压栈；遇到 + - * 时弹出两个数（第二次弹出的是左边的数），把结果压回去。最后返回整数结果。

在互动课里练这一课

打开互动课，这些例子都能直接改、直接运行，练习题提交马上判题。免费开始，不用注册。

打开互动课课程地图

互动课按顺序解锁：前面的课还没学，会先带你到课程地图。

本课术语

术语	中文	英文定义
Stack	栈	Last in, first out.
Queue	队列	First in, first out.
Deque	双端队列	A double-ended queue with O(1) adds and removes at both ends.