数据结构与算法 / 系统课时

循环队列的实现

循环队列的实现

固定数组实现普通队列时,队头移走后会留下空槽;若队尾只能向右移动,可能在仍有空间时误判已满。本课用取模运算实现下标回绕,并可靠区分空队列与满队列。

学习目标

  • 理解线性数组队列出现假溢出的原因
  • 掌握 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”更新。任一状态遗漏都会使空满判断失真。

循环队列的入队、出队和读取队头均为 O(1)O(1),底层数组占用 O(capacity)O(capacity) 空间。容量必须大于 0;满队列应明确拒绝写入或采用覆盖策略,不能在未定义规则时悄悄丢数据。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

循环队列的实现

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通