Python数据结构——循环队列

一句话：循环队列是用固定长度数组模拟环形、靠取模绕回解决「假溢出」的队列。物理上还是一段连续数组，逻辑上首尾相接成了环。

一、为什么需要循环队列

普通队列用数组实现时，出队只动 front 指针，元素不断从队头离开，前面就空出一堆位置。但 rear 指针一路向右，等到它撞到数组末尾时，哪怕前面空着，也插不进新元素了——这就是假溢出（false overflow）。

循环队列的解法：把数组首尾相接想成环，rear/front 走到末尾时取模绕回开头。这样「前面空出来的位置」能被重新利用，假溢出消失。

二、核心思路：两个指针 + 取模

只靠 front、rear 两个下标不够——当 front == rear 时，你分不清是「空」还是「满」。两种解法：

指针前进都靠取模，这是「循环」二字的核心：

rear = (rear + 1) % capacity # 入队后前进，到末尾自动绕回开头
front = (front + 1) % capacity # 出队同理

三、完整实现（带 size 计数器，推荐版）

# D:\\博客\\circular_queue.py（节选：CircularQueue 类）

# D:\\博客\\circular_queue.py
class CircularQueue:
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("容量必须大于 0")
self.capacity = capacity
self.queue = [None] * capacity
self.front = 0 # 队头下标（出队位置）
self.rear = 0 # 队尾下标（下一个入队位置）
self.size = 0 # 当前元素个数

def is_empty(self) –> bool:
return self.size == 0

def is_full(self) –> bool:
return self.size == self.capacity

def enqueue(self, item) –> None:
if self.is_full():
raise OverflowError("队列已满，无法入队")
self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.capacity
self.size += 1

def dequeue(self):
if self.is_empty():
raise IndexError("队列为空，无法出队")
item = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item

def peek(self):
if self.is_empty():
return None
return self.queue[self.front]

def __len__(self):
return self.size

def __repr__(self):
items = []
i = self.front
for _ in range(self.size):
items.append(self.queue[i])
i = (i + 1) % self.capacity
return f"CircularQueue({items})"

__repr__ 里用 i = (i + 1) % capacity 按逻辑顺序遍历，保证打印结果和「入队顺序」一致，调试时一眼能看懂。

小结：enqueue 放 rear、动 rear；dequeue 取 front、动 front；两者都取模绕回。判空判满交给 size，干净无歧义。

四、另一种写法：牺牲一个空位判满

不想维护 size 时，用「永远留一个空槽」来区分空和满：

class CircularQueueWasteOne:
def __init__(self, capacity: int):
self.capacity = capacity
self.queue = [None] * capacity
self.front = 0
self.rear = 0

def is_empty(self) –> bool:
return self.front == self.rear

def is_full(self) –> bool:
return (self.rear + 1) % self.capacity == self.front

def enqueue(self, item) –> None:
if self.is_full():
raise OverflowError("队列已满，无法入队")
self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.capacity

def dequeue(self):
if self.is_empty():
raise IndexError("队列为空，无法出队")
item = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front + 1) % self.capacity
return item

代价：N 容量的数组只能装 N-1 个元素。新手直接用第三节的 size 版，少踩坑。

五、和 collections.deque 的关系

Python 标准库的 deque（双端队列）底层就是类似环形缓冲，两端增删都是 O(1)。deque(maxlen=N) 更是开箱即用的有界循环队列——满了再 append 自动丢掉最老的那头，正好对应我们手写的「循环覆盖」语义。

# D:\\博客\\circular_queue.py
from collections import deque
dq = deque(maxlen=3) # maxlen 满了自动丢最老的，自带「循环」语义
for x in range(5):
dq.append(x)
print(dq) # deque([2, 3, 4], maxlen=3)

deque 常用 API：

六、什么时候用

• 手写循环队列：面试手写、理解底层、或特定嵌入式/缓冲场景需要完全掌控。
• 直接 deque：工程里 99% 的情况。滑动窗口、最近 N 条记录、BFS、栈/队列通吃。
• 一句话：凡是频繁从一头或两头增删，别用 list（头部操作 O(n)），用 deque；要练手或面试才手写循环队列。

总结：循环队列 = 数组 + front/rear 取模绕回 + size 判空满，专治普通队列的假溢出。真实项目里 collections.deque(maxlen=N) 一句话顶替它的全部功能。手写一遍是为了把「为什么这么设计」刻进脑子，不是让你上线造轮子。