波仔
🧮 第3章 数据结构
📄 一句话概括

堆栈是后进先出：最后放上去的最先拿走，像桌上摞书。 队列是先进先出：先排队的先办完，像收银台。 两者底层都是「一排格子」，差别只在从哪一头进出。

📝 本章和前面几章的关系

上一篇立了结论：摆放决定快慢。这一篇开始看具体的摆法。 堆栈和队列是最好懂的两个，因为日常生活里天天见——摞书、排队、撤销。 它们也是后面很多算法的零件：括号配对用堆栈，广度优先搜索用队列（3.6 会用到）。

一、堆栈：只能从最上面拿

桌上摞三本书。你要拿最下面那本，只能先把上面两本挪开。能动的永远只有最上面那一本。 这就是堆栈。放叫 push，拿叫 pop，两个动作都在同一头。 演示里 push 了三个盘子，再 pop 三次，拿出来的顺序正好是反的：盘子3、盘子2、盘子1。

英文叫 LIFO——后进先出。最后放进去的，最先出来。 这个规矩听着很受限，但它解决了一类问题：「最近的那个还没处理完」。 撤销、括号配对、浏览器的后退，都是这一类。

二、队列：一头进，另一头出

超市收银台排队。新来的站队尾，办完的从队头走。两头各管一件事。 这就是队列。进叫 enqueue，出叫 dequeue，一个在尾一个在头。 演示里三个顾客依次进来，出去的顺序和进来的顺序一样：A、B、C。

英文叫 FIFO——先进先出。 堆栈和队列的底层可以是同一个列表，差别只在 pop 从哪一头拿。从这个角度看， 它们不是两种数据结构，是同一个结构的两种用法。

三、拿堆栈解一个真问题：括号配不配对

给你一串括号 ([]{}，判断配不配对。人眼一扫就知道，程序怎么写？ 用堆栈，规则三句话：遇到左括号就压进去；遇到右括号就看栈顶；栈顶是配对的左括号就弹出，不是就报错。 为什么栈顶一定是对的？因为栈顶永远是「最近一个还没闭合的左括号」，而右括号要配的正是最近那个。

演示跑了五个例子，三个不配的各有各的原因：少一个左括号、要方括号却拿到圆括号、顺序交叉了。 这题是堆栈最经典的用法，也是面试里出现频率最高的一道。 它不是背出来的，是「最近未闭合」这个词直接推出来的。

四、队列用在哪：看场景选结构

打印任务必须用队列。谁先提交谁先打，大家才服气；要是按堆栈来，最后一个提交的先打，用户会骂人。 消息推送也一样。按到达顺序处理，因果才不会乱。 演示里那张表有一行是反着的：浏览器的后退该用堆栈，最近访问的最先退。退回最早访问的那个毫无意义。

所以选结构的方法是：先想清楚「先处理哪个才合理」，再选结构。不是看哪个高级， 也不是看哪个快——这两个都是 O(1)。

五、动手 Demo：堆栈、队列，和一道括号题

先用一个列表当堆栈，push 三个盘子再 pop 三次，看出来的顺序。 再把它当队列用，三个顾客依次进、依次出，对比两者的差别。 最后拿堆栈解括号配对，五个例子一起跑。

stack = []
for x in ('盘子1', '盘子2', '盘子3'):
    stack.append(x)
print('push 后', stack)
while stack:
    print('pop ->', stack.pop(), '还剩', stack)

from collections import deque
q = deque()
for x in ('顾客A', '顾客B', '顾客C'):
    q.append(x)
while q:
    print('dequeue ->', q.popleft(), '还剩', list(q))

def ok(s):
    pair = {')': '(', ']': '[', '}': '{'}
    st = []
    for c in s:
        if c in '([{':
            st.append(c)
        elif not st or st.pop() != pair[c]:
            return '不配'
    return '配对' if not st else '不配'
print([ok(x) for x in ('([]{})', '([]', '(]', '([)]', '')])

实跑输出：

--------------------------------------------------------------------
堆栈与队列：后进先出，先进先出
--------------------------------------------------------------------


  ① 堆栈：最后放上去的最先拿走
  --------------------------------------------------------------------
  push 盘子1  ->  栈里 ['盘子1']
  push 盘子2  ->  栈里 ['盘子1', '盘子2']
  push 盘子3  ->  栈里 ['盘子1', '盘子2', '盘子3']
  pop      ->  拿走 盘子3，还剩 ['盘子1', '盘子2']
  pop      ->  拿走 盘子2，还剩 ['盘子1']
  pop      ->  拿走 盘子1，还剩 []
  教材的比方是桌上摞书：只能从最上面拿。这就是堆栈，英文 LIFO——后进先出。

  ② 队列：先排队的先办完
  --------------------------------------------------------------------
  enqueue 顾客A  ->  队里 ['顾客A']
  enqueue 顾客B  ->  队里 ['顾客A', '顾客B']
  enqueue 顾客C  ->  队里 ['顾客A', '顾客B', '顾客C']
  dequeue      ->  顾客A 办完，还剩 ['顾客B', '顾客C']
  dequeue      ->  顾客B 办完，还剩 ['顾客C']
  dequeue      ->  顾客C 办完，还剩 []
  队列是 FIFO——先进先出。同一个列表，一头进一头出。

  ③ 拿堆栈解一个真问题：括号配不配对
  --------------------------------------------------------------------

| 字符串 | 结果 | 卡在哪 |
|---|---|---|
| ([]{}) | 配对 | — |
| ([] | 不配 | 还剩 1 个左括号没闭合 |
| (] | 不配 | 要 ] 却拿到 ) |
| ([)] | 不配 | 要 ] 却拿到 ) |
| (空) | 配对 | — |

  真跑一遍：['配对', '不配', '不配', '不配', '配对']
  括号题是堆栈最经典的用法：遇到左括号就压进去，遇到右括号就跟栈顶比。
  栈顶永远是「最近一个还没闭合的」。

  ④ 队列用在哪
  --------------------------------------------------------------------

| 场景 | 为什么是队列 | 为什么不是堆栈 |
|---|---|---|
| 打印任务 | 先提交的先打，才公平 | 后交的先打，用户会骂 |
| 消息推送 | 按到达顺序处理 | 会打乱因果 |
| 浏览器的后退 | 最近访问的最先退 | 退最早访问的没意义 |

  第三行是堆栈。看场景选结构，不是看哪个高级。

①堆栈用 append 进、pop 出，两个动作都在列表末尾——所以「最后进的先出」是自然的。 ②队列用 deque 而不是 list。list 从头部删要挪后面全部元素，deque 两头都是 O(1)。 这个选择不是讲究，是必要。 ③括号那段里 st.pop() 写在条件里，它既有「取出栈顶」也有「弹出」的效果。 not st 要先判，否则空栈上 pop 会报错。 ④最后一行五个结果：配对、不配、不配、不配、配对。空字符串算配对——这是括号题里容易被忽略的边界。

30 秒实验

  1. 把括号题里的 ([{ 改成只认圆括号，看 ([]) 的结果变成什么。
  2. 用堆栈判断一个字符串是不是回文（正着读反着读一样），想想为什么能。
  3. 把队列那段的 deque 换成普通 list 的 pop(0)，测一下快慢差多少。

常见误区

  1. 「堆栈和队列是两种完全不同的结构。」底层可以都是列表，差别只在从哪头取。
  2. 「队列就是先进先出，没有别的讲究。」实现上要用 deque，用 list 从头部删会变慢。
  3. 「括号题要记住规则。」规则是推出来的：栈顶永远是最近一个没闭合的左括号。
自测三问（点开对答案） 1. 堆栈和队列的根本差别是什么？ —— 从哪一头进、从哪一头出。堆栈同一头进出（后进先出），队列一头进一头出（先进先出）。 2. 为什么括号配对必须用堆栈，不能用队列？ —— 右括号要配的是最近一个没闭合的左括号，正是栈顶。队列给出的是最早那个，配不上。 3. 打印任务为什么用队列？ —— 先提交的先打才公平。用堆栈会变成最后一个提交的先打。

堆栈和队列只能在一头或两头动。要是想在中间插一个，前两篇的数组就得挪一大片。 下一节请出专门管插删的结构。

相关笔记