实现环形队列

题目描述
环形队列（Circular Queue）是一种基于数组实现的队列数据结构，通过循环利用数组空间解决普通队列出队后空间浪费的问题。要求实现以下操作：

• enqueue(value)：向队尾添加元素
• dequeue()：删除队首元素并返回
• front()：获取队首元素（不删除）
• isEmpty()：检查队列是否为空
• isFull()：检查队列是否已满

关键难点：如何区分队列空和队列满的状态。

解题过程

1. 基础结构设计
环形队列使用数组存储数据，需要维护两个指针：

• front：指向队首元素的位置
• rear：指向队尾元素的下一个位置（即新元素插入的位置）
• 预留一个空位用于区分空/满状态（常用技巧）

示例初始化（容量为k的队列）：

class CircularQueue:
    def __init__(self, k: int):
        self.size = k + 1  # 多留一个空位
        self.data = [None] * self.size
        self.front = 0
        self.rear = 0

2. 空/满判断逻辑

• 队列空：front == rear
• 队列满：(rear + 1) % size == front
  （当rear的下一个位置是front时认为已满，此时实际容量为size-1）

3. 入队操作（enqueue）

def enqueue(self, value: int) -> bool:
    if self.isFull():
        return False  # 队列已满
    self.data[self.rear] = value
    self.rear = (self.rear + 1) % self.size  # 循环移动
    return True

关键点：通过取模运算实现指针循环：

• 当rear到达数组末尾时，(rear+1) % size会回到数组开头
• 例如size=5，rear=4时：(4+1)%5=0

4. 出队操作（dequeue）

def dequeue(self) -> bool:
    if self.isEmpty():
        return False
    self.front = (self.front + 1) % self.size  # 移动front指针
    return True

注意：实际应用中可能需要返回出队的值，这里简化为布尔值。

5. 获取队首元素

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

6. 获取队尾元素

def Rear(self) -> int:
    if self.isEmpty():
        return -1
    return self.data[(self.rear - 1 + self.size) % self.size]  # 处理循环

难点解析：rear指向的是下一个空位，队尾元素在rear-1的位置。当rear=0时，需要(0-1+5)%5=4来正确取到末尾元素。

7. 完整代码示例

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

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

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

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

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.rear - 1) % self.size]

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

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

8. 实战测试

# 测试用例
q = CircularQueue(3)
q.enqueue(1)  # 返回 True
q.enqueue(2)  # 返回 True  
q.enqueue(3)  # 返回 True
q.enqueue(4)  # 返回 False（已满）
q.Front()     # 返回 1
q.Rear()      # 返回 3
q.dequeue()   # 返回 True
q.enqueue(4)  # 返回 True（循环利用空间）
q.Rear()      # 返回 4

核心思想：通过取模运算实现指针的循环移动，用(rear+1)%size == front判断队列满，确保至少有一个空位不被使用，从而与队列空状态区分开。