队列：先进先出（FIFO）

---

元数据卡

属性	值
章节编号	Vol 2 · 第3章 · 队列
难度等级	（入门加固）
前置知识	数组、链表（第2章）
核心技能	FIFO 操作、循环队列、BFS 层序遍历
关键字	Queue FIFO enqueue dequeue 循环队列 BFS

---

你的进度

逃出死胡同，你跳上一艘独木舟。前面是一条单行河，先上船的人先下船——这就是队列。

但如果直接用 Python 的 list 做队列，pop(0) 每次都要把后面所有元素往前挪——O(n)。队伍有 1000 人，第一个人走时后面 999 人全要挪。

真的队列长这样：

---

循环队列 —— 固定数组，头尾指针转圈走

Python

class CircularQueue:
    """头尾指针在环形空间里追着跑"""

    def __init__(self, capacity=8):
        self._data = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, item):
        if self.is_full():
            self._resize(self._capacity * 2)
        self._data[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        value = self._data[self._head]
        self._data[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return value

    def is_empty(self):
        return self._size == 0

    def is_full(self):
        return self._size == self._capacity

    def _resize(self, new_cap):
        old = self._data
        self._data = [None] * new_cap
        for i in range(self._size):
            self._data[i] = old[(self._head + i) % self._capacity]
        self._head = 0
        self._tail = self._size
        self._capacity = new_cap

cq = CircularQueue(4)
for i in range(1, 5):
    cq.enqueue(i)
print("出队:", cq.dequeue()); print("出队:", cq.dequeue())
cq.enqueue(5); cq.enqueue(6)
while not cq.is_empty():
    print(cq.dequeue(), end=" ")
print()

Java 差异： ArrayDeque 是循环数组实现，用 offer/poll 做队列。

---

常见陷阱

BFS 层序遍历 —— 队列的天命

你要在森林里一层一层地搜——BFS 天生就是队列。

Python

from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def bfs_level_order(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level_size = len(q)
        level = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)
    return result

#       1
#      / \
#     2   3
#    / \   \
#   4   5   6
root = TreeNode(1)
root.left = TreeNode(2); root.right = TreeNode(3)
root.left.left = TreeNode(4); root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print(bfs_level_order(root))

队列在这里干了什么？ 每轮把孩子按顺序排到队尾——"先来先出"，天然按层展开。

如果用 list 做队列： pop(0) 每出队 O(n)，BFS 变成 O(n²)。数据结构选错，复杂度翻倍。

---

验收标准

• [ ] 解释为什么 list.pop(0) 不是队列
• [ ] 循环队列的 (head + 1) % cap 在干什么
• [ ] BFS 为什么用队列不用栈
• [ ] 判空和判满的常用方案

---

常见卡点

卡点	破法
判空判满	浪费一格：head == tail 为空，(tail+1)%cap == head 为满
扩容后顺序乱	按 head→tail 顺序排好再拷贝，让 head 回到 0
BFS 分不清层	while 开头记 len(q)，每轮 for 跑完就是一层

---

旅人笔记

1. 队列 = 先进先出。核心操作：enqueue / dequeue。
2. 别用 list.pop(0)——O(n) 灾难。
3. 循环队列用固定数组+头尾指针转圈。
4. BFS 层序遍历天然是队列——先来先出。

---

→ 下一站预告

去看看 第3章：双端队列——左右通吃，看河马大爷怎么两边张嘴。

代码仓库位置： vol-02-dsa/examples/ch03/ 下有此章完整示例代码