LeetCode 题解工作台
设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们可以使用一个长度为 的数组 来模拟循环队列，用一个指针 记录队首元素的位置，初始时队列为空，而 为 。另外，我们用一个变量 记录队列中元素的个数，初始时 为 。 调用 `enQueue` 方法时，我们首先检查队列是否已满，即 $\textit{size} = k$，如果满了则直接返回 。否则，我们将元素插入到 $(\textit{front} + \textit{size}) \b…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
示例：
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
提示：
- 所有的值都在 0 至 1000 的范围内；
- 操作数将在 1 至 1000 的范围内；
- 请不要使用内置的队列库。
解题思路
方法一：数组模拟
我们可以使用一个长度为 的数组 来模拟循环队列，用一个指针 记录队首元素的位置，初始时队列为空，而 为 。另外，我们用一个变量 记录队列中元素的个数，初始时 为 。
调用 enQueue 方法时，我们首先检查队列是否已满，即 ，如果满了则直接返回 。否则，我们将元素插入到 的位置，然后 ，表示队列中元素的个数增加了 。最后返回 。
调用 deQueue 方法时，我们首先检查队列是否为空，即 ，如果为空则直接返回 。否则，我们将 ，表示队首元素出队，然后 ，
调用 Front 方法时，我们首先检查队列是否为空，即 ，如果为空则返回 。否则，返回 。
调用 Rear 方法时，我们首先检查队列是否为空，即 ，如果为空则返回 。否则，返回 。
调用 isEmpty 方法时，我们只需判断 即可。
调用 isFull 方法时，我们只需判断 即可。
时间复杂度方面，以上操作的时间复杂度均为 。空间复杂度为 。
class MyCircularQueue:
def __init__(self, k: int):
self.q = [0] * k
self.size = 0
self.capacity = k
self.front = 0
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self.q[(self.front + self.size) % self.capacity] = value
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:
return -1 if self.isEmpty() else self.q[self.front]
def Rear(self) -> int:
if self.isEmpty():
return -1
return self.q[(self.front + self.size - 1) % self.capacity]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacity
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to optimize space usage in a FIFO data structure.
- question_mark
Proficiency with circular data structure concepts.
- question_mark
Understanding of linked-list manipulation and pointer handling.
常见陷阱
外企场景- error
Failing to properly handle the circular nature of the queue, leading to overflow or underflow.
- error
Not managing the front and rear pointers correctly, causing incorrect operations.
- error
Using excessive space when a linked-list or array-based approach could optimize memory usage.
进阶变体
外企场景- arrow_right_alt
Implement the circular queue using a doubly linked list for bi-directional traversal.
- arrow_right_alt
Modify the queue to support multiple types of data (generic queue).
- arrow_right_alt
Add extra methods like peek or getSize to extend the basic operations.