设计循环队列 题目描述 设计一个循环队列（Circular Queue），也称为环形缓冲区。循环队列是一种线性数据结构，其操作基于FIFO（先进先出）原则，并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 你需要实现以下操作： MyCircularQueue(k) : 构造器，设置队列长度为 k。 Front : 从队首获取元素。如果队列为空，返回 -1。 Rear : 获取队尾元素。如果队列为空，返回 -1。 enQueue(value) : 向循环队列插入一个元素。如果成功插入则返回真。 deQueue() : 从循环队列中删除一个元素。如果成功删除则返回真。 isEmpty() : 检查循环队列是否为空。 isFull() : 检查循环队列是否已满。 解题过程 第一步：理解循环队列的核心思想与挑战 想象一个普通的、长度固定的数组实现的队列。当我们从队头（front）删除元素，并向队尾（rear）添加元素时， front 和 rear 指针都会不断向后移动。即使数组前面部分出现了空位，当 rear 指针到达数组末尾时，我们也会认为队列“已满”，无法再添加新元素。这造成了空间浪费。 循环队列通过将数组视为一个“环”来解决这个问题。当 rear 指针到达数组末尾时，如果数组开头还有空位，下一个元素就会被放置在数组开头。这样，只要队列没有真正被元素填满，我们就可以持续地添加元素。 核心挑战在于如何判断队列是“空”还是“满”。 队列空的条件 ：当队列中没有元素时，我们定义 front 和 rear 指针相等。 队列满的条件 ：如果我们也用 front 和 rear 指针相等来表示队列满，这就和“队列空”的条件冲突了。 第二步：选择解决方案——浪费一个空间 为了解决空和满的判断冲突，最常用且清晰的方法是“浪费”数组中的一个元素空间。 我们分配一个大小为 k+1 的数组，但规定最多只能存放 k 个有效元素。 front ：指向队列的第一个元素的位置。 rear ：指向队列最后一个元素的下一个位置（即下一个新元素应该被插入的位置）。 现在，我们可以定义明确的状态判断条件： 队列为空 ： front == rear 队列已满 ： (rear + 1) % capacity == front 解释： rear 的下一个位置（用取模运算实现循环）如果是 front ，就说明队列满了。因为我们总是预留一个空位，所以当 rear 指向这个空位时，我们就认为队列已满，不能再插入，否则就无法区分空和满。 第三步：详细设计每个操作 假设我们声明的数组为 queue ，容量（能存储的最大元素数）为 k ，但实际分配的数组大小为 k+1 。我们定义 capacity = k+1 。 构造器 MyCircularQueue(k) 初始化一个大小为 k+1 的数组（例如 self.queue = [0] * (k+1) ）。 初始化 self.front = 0 。 初始化 self.rear = 0 。 记录队列的最大容量 self.capacity = k+1 。 isEmpty() 直接判断 self.front == self.rear 。如果相等，返回 True ；否则返回 False 。 isFull() 判断 (self.rear + 1) % self.capacity == self.front 。如果相等，返回 True ；否则返回 False 。 enQueue(value) 首先检查队列是否已满（调用 isFull() ）。如果已满，返回 False 。 如果未满，执行以下操作： a. 将 value 放入 rear 指针当前指向的位置： self.queue[self.rear] = value 。 b. 将 rear 指针向后移动一位（并实现循环）： self.rear = (self.rear + 1) % self.capacity 。 返回 True 。 deQueue() 首先检查队列是否为空（调用 isEmpty() ）。如果为空，返回 False 。 如果不为空，执行以下操作： a. 将 front 指针向后移动一位（并实现循环）： self.front = (self.front + 1) % self.capacity 。 （注意：在队列中，从队头删除元素通常不需要显式地删除数组中的数据，只需移动指针即可。） 返回 True 。 Front() 如果队列为空，返回 -1 。 否则，返回 front 指针当前指向的元素： return self.queue[self.front] 。 Rear() 如果队列为空，返回 -1 。 否则，需要返回 rear 指针前一个位置的元素。因为 rear 指向的是下一个插入位置。 计算队尾元素的位置： (self.rear - 1 + self.capacity) % self.capacity 。 解释： self.rear - 1 可能会得到负数（比如当 rear 为 0 时），加上 capacity 再取模，可以确保得到一个合法的、非负的索引。 返回该位置的元素： return self.queue[(self.rear - 1) % self.capacity] 。 第四步：举例说明 让我们设计一个容量为 3 ( k=3 ) 的循环队列。分配的数组大小为 4 ( capacity=4 )。 初始状态： front = 0 , rear = 0 ，队列为空。 [ , , , ] (下划线表示空位) 索引: 0, 1, 2, 3 enQueue(1) : rear=0 未满，在索引0放入1， rear 移动到 (0+1)%4=1 。 队列: [1, _, _, _] , front=0 , rear=1 enQueue(2) : rear=1 未满，在索引1放入2， rear 移动到 (1+1)%4=2 。 队列: [1, 2, _, _] , front=0 , rear=2 enQueue(3) : rear=2 未满，在索引2放入3， rear 移动到 (2+1)%4=3 。 队列: [1, 2, 3, _] , front=0 , rear=3 enQueue(4) : 检查是否满？ (3+1)%4=0 ， 0 == front(0) ？ 是，队列已满，插入失败。 deQueue() : 队列不空， front 移动到 (0+1)%4=1 。 队列: [_, 2, 3, _] , front=1 , rear=3 (索引0的空间被释放，但数据1还在，只是我们不再访问它) enQueue(4) : 现在检查是否满？ (3+1)%4=0 ， 0 == front(1) ？ 否，未满。在索引3放入4， rear 移动到 (3+1)%4=0 。 队列: [_, 2, 3, 4] , front=1 , rear=0 。这就是循环的体现。 Rear() : 返回 rear 的前一个位置。 rear=0 , 前一个位置是 (0-1+4)%4=3 。返回 queue[3] 的值 4。正确。 Front() : 返回 queue[1] 的值 2。正确。 通过这个例子，你可以清晰地看到“浪费一个空间”的策略是如何工作的，以及指针是如何循环的。