队列

#队列

• 什么是队列
• 入队与出队
• FIFO 特性
• 队列与栈的对比
• 应用场景

#什么是队列

队列也是一种数据呈线性排列的数据结构，但与栈不同：队列的添加和删除分别在两端进行——一端只能进，另一端只能出。

就像在公交站排队：先到的人先上车，新来的人只能排在最后。

出队 ← ┌──────┬──────┬──────┐ ← 入队
       │ Blue │Green │ Red  │
       └──────┴──────┴──────┘
         ↑                    ↑
       队首(最先出)          队尾(最后入)

#入队与出队

• 入队（enqueue）：在队尾添加数据
• 出队（dequeue）：从队首取出数据

初始状态: 空

入队 Blue:  Blue

入队 Green:  Blue → Green

入队 Red:   Blue → Green → Red

出队:       Green → Red     (Blue 最先入队，最先出队)

出队:       Red              (Green 第二个出队)

Python 实现：

from collections import deque

queue = deque()

# 入队
queue.append("Blue")
queue.append("Green")
queue.append("Red")
print(queue)  # deque(['Blue', 'Green', 'Red'])

# 出队
first = queue.popleft()
print(first)  # Blue（最先入队的，最先出队）
print(queue)  # deque(['Green', 'Red'])

用 Python 的 list 也可以模拟队列（pop(0)），但每次出队都要移动所有元素，时间复杂度为 O(n)。collections.deque 是双端队列，两端操作都是 O(1)。

#FIFO 特性

队列的核心特性是 FIFO（First In First Out，先进先出）：最先放入的数据，最先被取出来。

入队顺序: Blue → Green → Red
出队顺序: Blue → Green → Red（与入队顺序相同！）

#队列与栈的对比

#应用场景

• 广度优先搜索（BFS）：候补顶点用队列管理，先加入的先检查，保证从近到远搜索

BFS 搜索过程（寻找芒果销售商）:

队列: [朋友A, 朋友B, 朋友C]
  → 检查朋友A（不是），朋友A的朋友入队
队列: [朋友B, 朋友C, A的朋友1, A的朋友2]
  → 检查朋友B（不是），朋友B的朋友入队
...

• 任务调度：操作系统的进程调度，先来的进程先执行
• 消息队列：分布式系统中的异步通信（如 RabbitMQ、Kafka）
• 打印机排队：多个打印任务按提交顺序处理
• 缓冲区：视频缓冲、键盘输入缓冲等

#小结

• 队列在两端操作，先进先出（FIFO）
• 入队和出队的时间复杂度都是 O(1)
• 队列适合「先来先服务」的场景
• 栈和队列是两种最基本的受限线性结构，广度优先搜索用队列，深度优先搜索用栈