LeetCode 622. Design Circular Queue 题解
题目描述
设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回 true 。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回 true 。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
示例 1：
输入： ["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","Rear","isFull","deQueue","enQueue","Rear"] [[3],[1],[2],[3],[4],[],[],[],[4],[]] 输出： [null,true,true,true,false,3,true,true,true,4] 解释： MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4解题思路
方法：数组
思路：
- 使用数组来存储队列元素
- 使用两个指针
front和rear分别指向队首和队尾 - 使用一个变量
count来记录队列中的元素个数 - 当
count == 0时，队列为空 - 当
count == k时，队列已满 - 当
rear到达数组末尾时，将其重置为 0 - 当
front到达数组末尾时，将其重置为 0
复杂度分析：
- 时间复杂度：O(1)，所有操作都是常数时间。
- 空间复杂度：O(k)，需要使用大小为 k 的数组来存储元素。
代码实现
方法：数组
class MyCircularQueue: def __init__(self, k: int): # 初始化数组、队首指针、队尾指针和元素个数 self.k = k self.queue = [0] * k self.front = 0 self.rear = 0 self.count = 0 def enQueue(self, value: int) -> bool: # 如果队列已满，返回 false if self.isFull(): return False # 将元素插入队尾 self.queue[self.rear] = value # 队尾指针后移，如果到达数组末尾，重置为 0 self.rear = (self.rear + 1) % self.k # 元素个数加 1 self.count += 1 return True def deQueue(self) -> bool: # 如果队列为空，返回 false if self.isEmpty(): return False # 队首指针后移，如果到达数组末尾，重置为 0 self.front = (self.front + 1) % self.k # 元素个数减 1 self.count -= 1 return True def Front(self) -> int: # 如果队列为空，返回 -1 if self.isEmpty(): return -1 # 返回队首元素 return self.queue[self.front] def Rear(self) -> int: # 如果队列为空，返回 -1 if self.isEmpty(): return -1 # 返回队尾元素（注意：队尾指针指向的是下一个插入的位置，所以需要减 1） return self.queue[(self.rear - 1) % self.k] def isEmpty(self) -> bool: # 当元素个数为 0 时，队列为空 return self.count == 0 def isFull(self) -> bool: # 当元素个数等于队列长度时，队列已满 return self.count == self.k测试用例
测试用例 1：
输入：
["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","Rear","isFull","deQueue","enQueue","Rear"] [[3],[1],[2],[3],[4],[],[],[],[4],[]]输出：
[null,true,true,true,false,3,true,true,true,4]总结
本题是队列的经典应用问题，主要考察对循环队列数据结构的理解和使用。通过使用数组，我们可以高效地实现循环队列的所有操作。
循环队列的核心思想是：使用数组来存储队列元素，使用两个指针分别指向队首和队尾，当指针到达数组末尾时，将其重置为 0，从而实现循环。
这种方法不仅适用于设计循环队列问题，还可以应用于许多其他需要循环缓冲区的问题。掌握循环队列的使用，对于解决这类问题非常重要。
