波仔
⌨️ 第三章 数值和数据的处理方法
📄 一句话概括

两座【只开一个口】或【一进一出】的数据楼：堆栈像摞盘子——后进先出（LIFO），从顶上放、从顶上拿；队列像排队——先进先出（FIFO），从尾进、从头出。它们规定的不只是存法，更是【谁先被处理】的秩序。

📝 本节和前面几节的关系

3-8／3-15 解决【怎么存】，这一篇解决【按什么顺序取】。回收两处旧地：C++ 课 12 章（函数调用）里每个函数就是一层栈帧；树莓派课第八章 Arduino 的 loop() 就是永不空转的队列循环思想。

一、堆栈：后进先出（LIFO）

三个动作：push 入栈（放盘子上顶）、pop 出栈（取顶上盘子）、peek 看顶（不拿只看）。只有栈顶一个口子：

stack = []
stack.append(1)    # push 1
stack.append(2)
stack.append(3)
print(stack.pop()) # 3 —— 最后进去的最先出来
print(stack.pop()) # 2
print(stack)       # [1]

真实世界的栈：

  1. 函数调用栈——每调一个函数压一层【栈帧】（参数、局部变量、返回地址），函数 return 弹出一层回到调用者。函数套函数有多深，栈就叠多高；压到爆就是【栈溢出 Stack Overflow】（那个著名网站的得名出处）；
  2. 编辑器撤销（Ctrl+Z）——最后一次操作最先撤销；
  3. 浏览器回退——最后访问的页面最先退回。

二、队列：先进先出（FIFO）

两个口子：enqueue 入队（从尾接上）、dequeue 出队（从头叫号）。绝对的【先来先服务】：

from collections import deque

queue = deque(["任务A", "任务B"])
queue.append("任务C")       # 入队：接到尾部
print(queue.popleft())      # 任务A —— 最先来的最先出
print(list(queue))          # [任务B, 任务C]

真实世界的队列：打印机任务排队、客服叫号、消息队列（服务器课程里 Kafkia／RabbitMQ 的思想原点）、操作系统的任务调度。用 deque 不用 list——list 从头部出元素（pop(0)）要让后面全体搬家（O(n)），deque 两头进出都是 O(1)（3-15 双向链表思想的落地）。

三、合流一景：用两个栈拼一个队列

经典思考题：栈只有一个口，怎么模拟队列的【先来先走】？——两个栈倒手：入栈 A、要取时把 A 全部倒进 B（顺序刚好翻回来）、从 B 弹出。这一幕是理解【结构决定行为】的最佳习题。

四、动手 Demo：两种秩序同台

# 栈：一摞盘子
stack = []
for plate in ["红", "黄", "蓝"]:
    stack.append(plate)
print(stack.pop(), stack.pop())      # 蓝 黄

# 队列：一条队伍
from collections import deque
queue = deque(["红", "黄", "蓝"])
print(queue.popleft(), queue.popleft())   # 红 黄

看到什么算成功：蓝 黄 和 红 黄。

读结果：同样按【红黄蓝】顺序放进去——栈吐出【蓝黄】（反序）、队列吐出【红黄】（正序）。两种结构、同一批数据、两种秩序——这就是【后进先出】与【先进先出】的全部区别。

五、30 秒实验

跑 stack.append(stack.pop() * 2 + 1) 前先放 3、5 进栈——输出 11。最顶上的 5 被弹出、翻倍加一、放回顶上——计算器求值、表达式解析的底层玩法就是这样的栈上操作。

六、常见误区

  1. 【堆栈和栈是两个东西】——是一回事。中文里【堆栈】这个词历史悠久（教材沿用），现代严格说法叫栈（stack）；注意它与堆（heap，动态分配内存的另一区域）毫无关系——【堆栈】两个字别拆开各自理解。
  2. 【栈溢出是内存不够用】——不准确。它是【调用栈叠得太高】（无限递归最典型）——哪怕总内存还剩很多，栈那一块区域先爆。
  3. 【队列必须用链表、栈必须用数组】——错。两种结构是【行为约定】，底层用数组还是链表随便（Python 栈用 list、队列用 deque 都是最顺手解）——接口与实现分离才是要学的。
自测三问（点开对答案） 1. **栈和队列的出入秩序各是什么？** 答：栈后进先出（LIFO，只有一个口）；队列先进先出（FIFO，一进一出两个口）。 2. **函数调用为什么天然用栈？** 答：调用嵌套的层次＝返回的逆序（最后调用的最先返回）——与 LIFO 完全同构；每层调用压一个栈帧，return 弹出。 3. **为什么 Python 队列推荐 deque 不推荐 list？** 答：list 从头部出元素要后面全体搬家（O(n)）；deque 两头进出都是 O(1)——双向链表思想的实现。

相关笔记