实现环形队列

题目描述
环形队列（Circular Queue）是一种基于数组实现的队列，通过循环利用数组空间来解决普通队列出队后空间无法重用的问题。要求实现一个固定大小的环形队列，支持入队、出队、获取队首元素、检查队列是否为空/满等操作。

核心知识点

• 数组的循环使用（通过取模运算实现）
• 队首（front）和队尾（rear）指针的维护
• 队列空和满的判定条件

实现步骤详解

1. 数据结构设计

   • 使用数组存储元素，并定义两个指针：
     • front：指向队列第一个元素的位置
     • rear：指向下一个可插入位置（即队尾元素的下一个位置）
   • 可选：添加size变量记录当前元素个数，简化空/满判断（推荐方法）

2. 空队列与满队列的判定

   • 无size变量时（依赖front和rear）：
     • 队列空：front == rear
     • 队列满：(rear + 1) % capacity == front（牺牲一个数组位置区分空和满）
   • 有size变量时（更直观）：
     • 队列空：size == 0
     • 队列满：size == capacity

3. 入队操作（enQueue）

   • 检查队列是否已满，若满则返回失败
   • 将元素放入rear指向的位置
   • 更新rear：rear = (rear + 1) % capacity
   • 更新size（如果使用size变量）

4. 出队操作（deQueue）

   • 检查队列是否为空，若空则返回失败
   • 从front指向位置取出元素
   • 更新front：front = (front + 1) % capacity
   • 更新size（如果使用size变量）

5. 获取队首元素（Front）

   • 若队列不为空，返回data[front]

6. 获取队尾元素（Rear）

   • 若队列不为空，返回data[(rear - 1 + capacity) % capacity]（注意rear指向下一个空位）

代码实现（使用size变量）

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

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

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        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.capacity) % self.capacity]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

关键问题分析

1. 为什么推荐使用size变量？

   • 逻辑清晰，避免判断空/满时的边界问题
   • 无需牺牲数组的一个存储位置

2. 取模运算的作用

   • 当指针到达数组末尾时，通过取模使其回到数组开头，实现循环使用

3. 时间复杂度分析

   • 所有操作（入队、出队、获取首尾元素）均为O(1)时间

环形队列 vs 普通队列

• 普通队列：出队后空间浪费，可能频繁扩容
• 环形队列：空间利用率高，适合固定大小的场景（如操作系统任务调度）