LeetCode 622. 设计循环队列
目录
题目描述
题意分析
需要设计一个容量固定为
k的先进先出容器，对外提供入队、出队、取队首、取队尾、判空、判满六个接口。入队和出队用布尔值表示是否成功，容器已满时入队返回false，容器为空时出队返回false，取队首和取队尾在空容器上返回-1。约束里的信号很直白：容量在构造时就确定且不再变化，说明底层可以一次性申请好一块定长存储，不需要扩容；接口里同时存在判空和判满，说明这两种状态必须能被明确区分，不能含糊。题目还隐含要求每个操作都是常数时间，否则「循环」二字就失去意义。
边界集中在两端相遇的时刻：刚构造出来什么都没有、装到一个不剩、装满后出队再入队让数据绕回存储开头、以及只有一个元素时队首和队尾指向同一处。这四种情形是所有实现出错的高发区。
解法：数组 + 队首下标 + 元素数量
核心思路
用普通数组实现队列时，出队后搬移元素会花费 $O(k)$；只让下标向右走，又无法复用数组前端的空位。循环队列通过对容量取模，让下标越过末尾后回到开头，从而在固定数组中持续复用空间。
本解法只维护数组
data、队首下标head和元素个数size。核心不变量是：从head开始、按环形顺序向后数size个位置，恰好是队列中的全部有效元素，并且 $0 \le size \le k$。因此：
- 下一个写入位置：
(head + size) % k；- 队尾位置：
(head + size - 1) % k；- 队空：
size == 0；队满：size == k。维护
size还解决了head == tail无法区分空与满的问题。另一种常见方案是额外留一个空槽，但数组要开成k + 1；面试中任选一种讲清状态定义即可，不要混用。
解题步骤
- 构造时申请长度为
k的数组，令head = 0、size = 0。- 入队前判满；将值写入
(head + size) % k，再执行size++。- 出队前判空；令
head = (head + 1) % k，再执行size--。旧值无需清除，因为有效性只由head和size决定。- 非空时，队首为
data[head]，队尾为data[(head + size - 1) % k]；空队列按题意返回-1。- 判空、判满分别比较
size与 0、k。例如容量为 3，入队
1, 2, 3后出队1，此时head = 1、size = 2。再次入队4的位置是 $(1+2) \bmod 3=0$，正好复用数组开头，逻辑队列变为[2, 3, 4]。
代码实现
class MyCircularQueue {
private int[] data;
private int head;
private int size;
public MyCircularQueue(int k) {
data = new int[k];
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
int tail = (head + size) % data.length;
data[tail] = value;
size++;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
// 出队只需要移动队首下标，不需要清空数组位置。
head = (head + 1) % data.length;
size--;
return true;
}
public int Front() {
return isEmpty() ? -1 : data[head];
}
public int Rear() {
if (isEmpty()) {
return -1;
}
return data[(head + size - 1) % data.length];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == data.length;
}
}
type MyCircularQueue struct {
data []int
head int
size int
}
func Constructor(k int) MyCircularQueue {
return MyCircularQueue{data: make([]int, k)}
}
func (this *MyCircularQueue) EnQueue(value int) bool {
if this.IsFull() {
return false
}
tail := (this.head + this.size) % len(this.data)
this.data[tail] = value
this.size++
return true
}
func (this *MyCircularQueue) DeQueue() bool {
if this.IsEmpty() {
return false
}
// head 按容量取模前进，实现循环复用数组。
this.head = (this.head + 1) % len(this.data)
this.size--
return true
}
func (this *MyCircularQueue) Front() int {
if this.IsEmpty() {
return -1
}
return this.data[this.head]
}
func (this *MyCircularQueue) Rear() int {
if this.IsEmpty() {
return -1
}
return this.data[(this.head+this.size-1)%len(this.data)]
}
func (this *MyCircularQueue) IsEmpty() bool {
return this.size == 0
}
func (this *MyCircularQueue) IsFull() bool {
return this.size == len(this.data)
}
复杂度分析
- 时间复杂度：每个接口都是 $O(1)$，没有遍历或元素搬移。
- 空间复杂度：$O(k)$，用于保存容量为
k的定长数组。
关键点总结
- 先定义状态不变量，再由它推导入队位置、队尾位置和空满条件，比背公式可靠。
- 取模负责回绕，
size负责区分空与满，两者职责不同。head + size指向下一个写入位置，所以队尾必须再减 1。- 出队只改变逻辑边界，不必清除数组中的旧值。
- 面试时应主动说明「维护
size」与「留一个空槽」两种方案的取舍。
易错点总结
- 只用
head == tail同时判断空和满，两种状态会产生歧义；必须维护size或留一个空槽。- 入队前漏判满会覆盖仍有效的队首元素，并破坏
size <= k。- 队尾公式漏掉
-1，读到的是下一个待写位置；公式漏掉head，绕圈后会读错。- 下标前进忘记取模，走过数组末尾就会越界。
- 空队列调用
Front或Rear必须返回-1，不能直接读取数组默认值。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 225. 用队列实现栈 | 简单 | 用队列倒腾出后进先出语义 |
| 232. 用栈实现队列 | 简单 | 双栈摊还实现先进先出 |
| 707. 设计链表 | 中等 | 指针型容器的增删边界 |
| 933. 最近的请求次数 | 简单 | 按时间窗口自动淘汰队首 |
| 1188. 设计有限阻塞队列 | 中等 | 定长队列加多线程同步 |