Python队列（collections.deque）

用 deque 实现队列：像排队打饭一样简单

生活中排队无处不在：食堂打饭要排队，超市结账要排队，连玩游乐园的过山车也要排队。队列这种数据结构就是模仿“先来先服务”的规则——先进先出（FIFO，First In First Out）。第一个排队的人最先离开，最后来的人只能排在末尾。

Python 里怎么实现队列？最方便的方式是用 collections 模块里的 deque（读作“deck”，意思是双端队列）。它既可以像普通队列一样从右边进、左边出，还能快速从两端添加或删除元素。我们只用一个方向进、另一个方向出，就得到了一个标准队列。

什么是 deque？

deque 是“double-ended queue”的缩写，也就是“双端队列”。如果你把 deque 想象成一条队伍，那么：

• 你可以在队伍末尾加入新人（append）
• 你可以在队伍最前面让第一个人离开（popleft）
• 你还可以快速在队伍最前面插队（appendleft）或者从末尾直接抽人（pop），但普通队列一般不用这些操作。

生活小剧场：你正在排队买冰淇淋，突然你的好朋友来了，想插到你前面。如果你允许他插队，那就相当于用了 appendleft，但这会破坏公平，所以队列一般只用右进左出。

创建队列

先导入 deque，再创建空队列：

from collections import deque

# 创建一个空队列，就像一条空空的队伍
line = deque()

也可以直接创建带初始元素的队列：

# 一开始就有三个人在排队
line = deque(["小红", "小明", "小刚"])
print(line)  # deque(['小红', '小明', '小刚'])

入队：把元素加到队尾

用 append() 方法，就像有人站到了队伍最后面。

from collections import deque

# 创建空队列
queue = deque()

# 三个人依次来排队
queue.append("小红")   # 小红先来，站到第一位（也是最后一位）
queue.append("小明")   # 小明后来，站到小红后面
queue.append("小刚")   # 小刚最后来，站到最后
print("当前队列:", queue)  # deque(['小红', '小明', '小刚'])

注意：每次 append 都是加到 右端（队尾），队首在左边。

出队：从队首移除元素

用 popleft() 方法，队伍最前面的人离开。这个方法会返回离开的那个人，并且队列里就没有他了。

# 第一个人离开
first = queue.popleft()     # first 得到 '小红'
print(first, "走了")        # 打印 "小红 走了"
print("现在队列:", queue)   # deque(['小明', '小刚'])

重要：如果用 pop() 代替 popleft()，会从队尾移除！那就变成了“后进先出”，像栈一样，不再是队列了。这是新手最容易犯的错误。

查看队首但不移除

用 queue[0] 可以偷看队首是谁，队伍不动。

print("当前队首是:", queue[0])  # 小明

也可以用 queue[-1] 查看队尾（最后一个人），但队列一般只关心队首。

为什么用 deque 而不用列表？

你可能想：直接用列表，list.append() 加到最后，list.pop(0) 移除第一个，不也能实现队列吗？
可以，但非常慢！
因为列表在内存中是连续存储的，删除第一个元素后，后面所有元素都得往前移动一位，就像队伍最前面的人走了，后面的人全都得往前挪一步。如果有1000个人，就要移动999次。而 deque 是双向链表实现的，从两端添加或删除都很快，无论队列多长，速度都几乎不变。

生活例子：想象你在一张纸上写着一列名字，删除第一个名字后，你必须把后面所有名字都重新抄一遍到更靠前的位置，多累啊！而 deque 就像一块磁力白板，每个人可以独立地站在自己的位置上，拿掉一个，其他人不用动。

常见错误

1. 用了 pop() 而不是 popleft()
pop() 默认从右边（队尾）删除，队列变栈，违背了“先进先出”的原则。

2. 用了 appendleft() 入队
   appendleft() 会从左端（队首）加元素，相当于允许插队，破坏了队列的公平性。如果想实现插队功能（比如紧急任务），那就要用双端队列的完整功能了，不再算普通队列。

3. 忘记导入 deque
   直接写 queue = deque() 会报错，因为没导入。记住最前面写 from collections import deque。

4. 用 queue[0] 时队列为空
   如果队列是空的，访问 queue[0] 会抛出 IndexError。出队和查看队首之前最好先判断队列是否为空。

完整示例：模拟银行排队叫号

假设银行有一个叫号机，顾客取号后按顺序办理业务。我们用一个队列来模拟。

from collections import deque

# 创建空队列，模拟正在等待的人
waiting_line = deque()  # 等待队伍为空

# 顾客取号，依次入队
waiting_line.append("顾客001")  # 第一位顾客
waiting_line.append("顾客002")  # 第二位
waiting_line.append("顾客003")  # 第三位
print("当前等待人数:", len(waiting_line))  # 3人
print("等待队列:", waiting_line)           # deque(['顾客001', '顾客002', '顾客003'])

# 叫号：第一位顾客去窗口办理业务
served = waiting_line.popleft()  # 最先来的顾客离开队伍
print(served, "正在办理业务")     # 顾客001 正在办理业务
print("剩余等待人数:", len(waiting_line))  # 2人

# 又来了一位新顾客
waiting_line.append("顾客004")
print("新等待队列:", waiting_line)  # deque(['顾客002', '顾客003', '顾客004'])

# 查看当前第一位是谁
print("下一位是:", waiting_line[0])  # 顾客002

运行结果：

当前等待人数: 3
等待队列: deque(['顾客001', '顾客002', '顾客003'])
顾客001 正在办理业务
剩余等待人数: 2
新等待队列: deque(['顾客002', '顾客003', '顾客004'])
下一位是: 顾客002

实际应用场景

• 打印任务：多个文档排队打印，先提交的先打印。
• 游戏中的动作序列：比如角色出招，先输入的先执行。
• 广度优先搜索（BFS）：在迷宫寻路、社交网络找最短路径时，会用队列保存待探索的节点。
• 消息队列：不同程序之间发消息，用队列保证顺序。

相关指引

如果你学会了队列，不妨继续看看：

• 栈（Stack）：deque 也能当栈用（只用 append 和 pop）。栈是“后进先出”（LIFO），就像一摞盘子，最后放的先拿走。
• 双端队列的其他用法：deque 还支持 appendleft、pop、rotate（旋转）等方法，可以灵活实现更复杂的数据结构。
• queue 模块：Python 还有专门的 queue.Queue（线程安全），适合多线程程序。不过单线程下用 deque 更简单高效。

记住：队列的核心就是公平——谁先来谁先走！ 用 deque 的 append 和 popleft，你就掌握了队列的灵魂。