LeetCode 622. Design Circular Queue 题解

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从而实现循环。这种方法不仅适用于设计循环队列问题还可以应用于许多其他需要循环缓冲区的问题。掌握循环队列的使用对于解决这类问题非常重要。