数据结构与算法 / 系统课时
循环队列的实现
循环队列的实现
固定数组实现普通队列时,队头移走后会留下空槽;若队尾只能向右移动,可能在仍有空间时误判已满。本课用取模运算实现下标回绕,并可靠区分空队列与满队列。
学习目标
- 理解线性数组队列出现假溢出的原因
- 掌握
front、rear、size三个状态的含义 - 实现固定容量循环队列并验证下标回绕
状态与回绕规则
本课约定 front 指向当前队头元素,rear 指向下一次写入位置,size 记录实际元素数量。入队和出队后,下标都通过 (index + 1) % capacity 回到数组开头。

使用 size 判断状态最直接:size == 0 表示空,size == capacity 表示满。另一种实现会预留一个空槽,仅凭 front 和 rear 区分空满,但实际可用容量会减少 1。
主示例
以下 Python 3.9+ 示例使用固定长度列表保存元素。出队后清空槽位,避免容器继续持有已移除对象的引用。
python
from typing import Generic, Optional, TypeVar, cast
T = TypeVar("T")
class CircularQueue(Generic[T]):
def __init__(self, capacity: int) -> None:
if capacity <= 0:
raise ValueError("capacity 必须大于 0")
self._capacity = capacity
self._data: list[Optional[T]] = [None] * capacity
self._front = 0
self._rear = 0
self._size = 0
def enqueue(self, item: T) -> None:
if self.is_full():
raise OverflowError("循环队列已满")
self._data[self._rear] = item
self._rear = (self._rear + 1) % self._capacity
self._size += 1
def dequeue(self) -> T:
if self.is_empty():
raise IndexError("循环队列为空")
item = cast(T, self._data[self._front])
self._data[self._front] = None
self._front = (self._front + 1) % self._capacity
self._size -= 1
return item
def front(self) -> T:
if self.is_empty():
raise IndexError("循环队列为空")
return cast(T, self._data[self._front])
def is_empty(self) -> bool:
return self._size == 0
def is_full(self) -> bool:
return self._size == self._capacity
def main() -> None:
queue = CircularQueue[int](3)
for value in [10, 20, 30]:
queue.enqueue(value)
print("队头:", queue.front())
print("出队:", queue.dequeue())
queue.enqueue(40) # rear 回绕后复用已释放的槽位。
while not queue.is_empty():
print("依次出队:", queue.dequeue())
if __name__ == "__main__":
main()预期输出:
text
队头: 10
出队: 10
依次出队: 20
依次出队: 30
依次出队: 40正确性与边界
入队必须按“写入、推进 rear、增加 size”更新;出队必须按“读取、清空、推进 front、减少 size”更新。任一状态遗漏都会使空满判断失真。
循环队列的入队、出队和读取队头均为 ,底层数组占用 空间。容量必须大于 0;满队列应明确拒绝写入或采用覆盖策略,不能在未定义规则时悄悄丢数据。
按自己的节奏,确认真正理解。