实现环形队列

环形队列是一种特殊的线性数据结构，它遵循先进先出（FIFO）原则，并且其存储空间是固定大小的，通过循环利用数组空间来避免数据搬移。环形队列的核心在于如何判断队列为空或已满，以及如何高效地进行入队和出队操作。

1. 环形队列的基本概念

• 固定大小：环形队列使用一个固定长度的数组来存储元素。
• 两个指针：
  • front：指向队列的第一个元素。
  • rear：指向队列最后一个元素的下一个位置（即新元素要插入的位置）。
• 循环利用：当指针到达数组末尾时，通过取模运算（%）使其回到数组开头，形成循环。

2. 关键问题：如何判断队列空或满？

由于 rear 指向下一个插入位置，如果直接使用 front == rear 判断空队列，那么当队列满时 front 和 rear 也可能相等（因为循环后位置重叠）。为了解决这个问题，有两种常见方法：

• 方法1：浪费一个数组空间
  规定当 (rear + 1) % capacity == front 时表示队列已满（即 rear 的下一个位置是 front）。此时队列中最多存储 capacity - 1 个元素。
• 方法2：维护一个计数器
  通过变量 size 记录当前队列中的元素数量，直接通过 size == 0 判断空，size == capacity 判断满。

下面以方法1（浪费一个空间）为例详细讲解实现。

3. 设计数据结构

class CircularQueue:
    def __init__(self, capacity: int):
        self.capacity = capacity + 1  # 多分配一个空间用于区分空和满
        self.data = [None] * self.capacity
        self.front = 0  # 指向队首元素
        self.rear = 0   # 指向下一个插入位置

4. 操作步骤详解

（1）判断队列是否为空

如果 front == rear，说明没有元素。

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

（2）判断队列是否已满

如果 (rear + 1) % capacity == front，说明队列已满（rear 的下一个位置是 front）。

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

（3）入队操作（enqueue）

• 检查队列是否已满，若满则拒绝操作。
• 将元素放入 rear 位置。
• 更新 rear = (rear + 1) % capacity。

def enqueue(self, value: int) -> bool:
    if self.is_full():
        return False  # 入队失败
    self.data[self.rear] = value
    self.rear = (self.rear + 1) % self.capacity
    return True

（4）出队操作（dequeue）

• 检查队列是否为空，若空则拒绝操作。
• 取出 front 位置的元素。
• 更新 front = (front + 1) % capacity。

def dequeue(self) -> Optional[int]:
    if self.is_empty():
        return None  # 出队失败
    value = self.data[self.front]
    self.front = (self.front + 1) % self.capacity
    return value

（5）获取队首元素

def peek(self) -> Optional[int]:
    if self.is_empty():
        return None
    return self.data[self.front]

5. 完整代码示例

class CircularQueue:
    def __init__(self, k: int):
        self.capacity = k + 1
        self.data = [None] * self.capacity
        self.front = 0
        self.rear = 0

    def enqueue(self, value: int) -> bool:
        if self.is_full():
            return False
        self.data[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        return True

    def dequeue(self) -> bool:
        if self.is_empty():
            return False
        self.front = (self.front + 1) % self.capacity
        return True

    def get_front(self) -> int:
        if self.is_empty():
            return -1
        return self.data[self.front]

    def get_rear(self) -> int:
        if self.is_empty():
            return -1
        return self.data[(self.rear - 1 + self.capacity) % self.capacity]

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

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

6. 复杂度分析

• 时间复杂度：所有操作（入队、出队、检查空/满）均为 O(1)。
• 空间复杂度：O(n)，其中 n 是队列的容量。

7. 环形队列的应用场景

• 操作系统中的进程调度队列。
• 网络数据包缓冲区。
• 生产者-消费者模型中的有限容量队列。

通过以上步骤，你可以清晰地理解环形队列的实现原理和关键技巧。重点掌握空/满判断条件和循环指针的移动，这是环形队列的核心。