栈、队列与双端队列
本节目标
区分后进先出与先进先出，使用 list 实现栈、使用 collections.deque 实现队列，并为任务消费者设计空队列和容量边界。
栈：后进先出
栈（stack）像一摞盘子，最后放上的先取走，称为 LIFO（Last In, First Out）。
steps = []
steps.append("open_file")
steps.append("parse_json")
current = steps.pop()
print(current) # parse_json栈用于解析嵌套结构、撤销记录和深度优先遍历。调用栈也是函数执行的重要模型，但不要把业务补偿简单等同于 pop()：已发送邮件或已付款等外部副作用需要明确补偿流程。
队列：先进先出
队列（queue）像排队，最早进入的先处理，称为 FIFO（First In, First Out）。Python 列表从头部弹出需要移动元素；双端队列 deque 适合两端追加和弹出：
from collections import deque
jobs = deque(["run-1", "run-2"])
jobs.append("run-3")
while jobs:
run_id = jobs.popleft()
print(run_id)循环前先判断队列是否为空，否则 popleft() 会抛出 IndexError。
操作与空结构契约
| 抽象 | Python 结构 | 加入 | 取出 | 空时行为 |
|---|---|---|---|---|
| 栈 | list | append(x) | pop() | IndexError |
| FIFO 队列 | deque | append(x) | popleft() | IndexError |
| 双端队列 | deque | append/appendleft | pop/popleft | IndexError |
API 应选择“先判断为空”“捕获具体异常”或“返回显式空结果”，并保持一致。不要用 None 同时表示“队列为空”和“队列中合法存了 None”。单线程教学代码可以 if jobs:；并发环境中的“先判断再取”可能发生竞态，应使用队列原语提供的原子操作。
有界缓冲区
监控系统常只保留最近 N 条记录：
from collections import deque
recent_errors = deque(maxlen=3)
for code in [500, 502, 429, 503]:
recent_errors.append(code)
print(list(recent_errors)) # [502, 429, 503]本例始终用 append 按时间追加，因此满容量时左端最早加入的元素被丢弃。它适合滑动窗口，不适合需要永久审计的事件日志。
一般规则是：有界 deque 满时，从新增操作的相反端丢弃元素；只有约定始终从一端按时间追加时，才可把被丢弃项称为“最旧”。maxlen 创建后不可修改。静默丢弃是容器语义，不会自动写审计或告警。如果不能丢数据，应在加入前显式检查容量，或把背压交给更合适的队列系统。
rotate(k) 可以移动两端位置，但它不是业务重试/公平调度策略；旋转顺序必须由清楚的业务规则驱动。
deque 与并发队列不是一回事
collections.deque 是内存容器。线程间生产/消费可考虑 queue.Queue，异步协程使用 asyncio.Queue；它们还提供阻塞/等待和容量语义。即便如此，也仍没有跨进程持久化、崩溃恢复或分布式确认。
选择前先问：只需要容器操作，还是需要协调多个执行者？不要因为名字都叫 queue 就假定契约相同。
生产任务队列还缺什么
内存 deque 能讲清 FIFO，却不能提供跨进程持久化。真实 Agent 工作者通常还需要：
- 任务 ID 和幂等键；
- 确认、重试、退避与死信队列；
- 超时、租约和消费者崩溃恢复；
- 优先级、并发上限与背压；
- 持久化、监控与权限。
这些是系统语义，不会因为换一个容器自动出现。
练习
- 用列表实现浏览器“后退”栈：依次访问 A、B、C，再后退两次。
- 用
deque模拟三个任务先进先出处理。 - 创建
deque(maxlen=5)保存最近延迟，并在每次追加后计算平均值。 - 若任务处理失败，应该立刻放回队首、放到队尾还是进入单独重试队列？分别说明风险。
- 为栈和队列分别写“空时抛异常”与“返回可空值”两种接口，说明哪一种不会与合法
None混淆。 - 测试
deque(maxlen=3)的append与appendleft分别淘汰哪一端，并写成契约。
自测
- 栈和队列的取出顺序分别是什么？
- 为什么不用
list.pop(0)处理大队列？ maxlen队列适合审计日志吗？- 内存队列为何不能直接用于可靠的多机任务系统？
- 为什么并发消费者不应依赖“先
if queue再取”的两步检查？ deque、queue.Queue与asyncio.Queue解决的是完全相同的问题吗？
下一步与相关概念
下一节：哈希表、字典、集合与计数。
参考资料
获取日期：2026-07-14。