01先读懂这个概念
与栈只改一个规则
任务 A、B、C 依次到来。如果用栈，先处理 C；如果用队列，先处理 A。队列在队尾加入元素，在队首取出元素，称为 FIFO（先进先出）。数据结构选错，即使每个元素最后都被处理，处理顺序也可能完全不符合问题要求。
处理 A 时又来了 D，D 应排在 C 后面，剩余队列为 B、C、D。到了图的按层搜索，处理一个旧节点会发现新邻居；让新邻居排在队尾，就不会抢在更早发现的同层节点之前被展开。
接口看起来简单，底层成本仍要数
Python list.pop(0) 能正确取出队首，但需要把后续引用前移；对 n 个元素反复这样做，总搬移量可能是 (n−1)+…+1。正确的顺序不代表正确的复杂度。
Python 的 collections.deque 支持高效的两端操作。本课用 append 入队、popleft 出队。JavaScript 也可保留一个 head 下标，只让 head 向右走而不反复 shift；但旧槽位可能仍占内存，长期服务还需考虑压缩或环形队列。
02从具体数据开始手算
拿一个小输入，逐步手算
A、B、C 依次入队，处理 A 时又到来 D。左端是队首。
| 操作 | 返回 | 剩余队列 |
|---|---|---|
| 入队 A | — | [A] |
| 入队 B、C | — | [A,B,C] |
| 出队 | A | [B,C] |
| 入队 D | — | [B,C,D] |
| 继续出队三次 | B、C、D | [] |
同一批任务的相对先后顺序保持不变。栈是处理最近的任务，队列是处理最早的任务，堆则会按优先级选择。
03把正确性的理由说清楚
为什么不会让后来者插队
- 队列始终按到达顺序保存所有尚未处理的元素。初始时这一规则成立。
- 入队仅添加到末尾，因此不会越过任何已有元素；出队只删除最前面的元素。
- 不断出队得到的顺序与入队顺序一致。实际业务如果允许优先级插队，就需要更换规则或结构。
04把刚才的思路写成代码
基础课用 Python 表达，先对照变量含义与执行顺序。后续算法课提供 Python、C++ 与 JavaScript 三种实现。
from collections import deque
def process_tasks(tasks):
queue = deque(tasks)
processed = []
while queue:
task = queue.popleft()
processed.append(task)
return processed代码里的每个关键决定
queue = deque(tasks)- 将已有任务按原顺序放入队列；构造本身也要遍历输入，计 O(n)。
while queue:- 空队列时停止，避免 popleft 抛出空队列异常。若处理过程中发现新任务，可用 queue.append 添加到末尾。
task = queue.popleft()- 删除并返回队首。append 和 popleft 配对使用，表达先进先出；若改成 pop，则成了从队尾取出。
05这些操作要付出多少代价
把工作量具体数出来
构造队列 O(n)，每个任务出队一次，总时间 O(n)。deque 的端点追加和弹出具有近似常数时间性能。
此函数队列最多 n 项，输出 processed 也最多 n 项，总额外存储 O(n)。如果分析不含输出的辅助空间，队列本身仍为 O(n)。
用数组加 head 的实现，每次 head++ 也是常数动作；但不能只看剩余逻辑长度就认为之前的存储已经释放。
06用一个反例检查理解
顺序正确，性能却变成平方级
把本课的队列换成 list，并反复 pop(0)，每次都搬移剩余元素。n=4 时搬移 3+2+1=6 项，n 变大后累计为 O(n²)。
怎样修正：选用 deque，或设计维护 head 的队列。把『取出第一个元素』的语义与实现成本分开检查。
07自己推一次，再做自测
比较同一串操作
依次加入 1、2，取出一次，再加入 3，最后取完。用队列与栈分别得到什么取出顺序？
需要一点提示
画出每一步的容器，不要只看最终装过哪些数。
查看完整推导与答案
- 队列先取 1，随后容器为 [2,3]，最终取出顺序是 1、2、3。
- 栈先取 2，随后容器为 [1,3]，最终取出顺序是 2、3、1。
- 两者都处理了同样的数，但保留的顺序规则不同。