622. 设计循环队列
题目描述
设计一个容量固定的循环队列类 MyCircularQueue。它遵循先进先出，存储空间首尾相接，出队后空出的位置可以被后续入队的元素再次使用。不允许使用语言自带的队列库。
MyCircularQueue(k)：创建一个最多容纳 k 个元素的空队列。enQueue(value)：把 value 放到队尾，成功返回 true，队列已满时返回 false。deQueue()：移除队首元素，成功返回 true，队列为空时返回 false。
Front()：返回队首元素，队列为空时返回 -1。Rear()：返回队尾元素，队列为空时返回 -1。isEmpty()：队列为空时返回 true。isFull()：队列已满时返回 true。
测试数据以两个数组给出：第一个是依次调用的方法名，第二个是对应的参数；输出数组给出每次调用的返回值，构造函数对应 null。
示例 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]
解释：容量为 3，第 4 次入队因队满返回 false；出队一次后再放入 4 成功，此时队尾为 4。
数据范围
- 所有元素值在
0到1000之间。 - 操作次数在
1到1000之间。 - 不要使用内置的队列实现。
解题思路：定长数组 + 取模
用长度为 k 的数组加两个变量：head 是队首下标，size 是元素个数。队尾的下一个空位是 (head + size) % k，队尾元素是 (head + size - 1) % k。入队写入空位并 size+1；出队只需 head 后移一位（取模）并 size-1，旧值不必清理。
为什么正确
队列中的元素依次位于下标 head, head+1, …, head+size-1（均对 k 取模），且 0 ≤ size ≤ k。
复杂度分析
所有操作 O(1)；空间 O(k)。
易错点
只用 head 和 tail 两个指针时，head == tail 既可能是空也可能是满，需要多开一格或记录 size；这里用 size 来区分。Rear 的下标要减 1 后再取模，不要忘记绕回。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class MyCircularQueue:
def __init__(self, k: int = 3):
self.q = [0] * k
self.head = 0
self.size = 0
self.cap = k
def enQueue(self, value: int) -> bool:
if self.size == self.cap:
return False
self.q[(self.head + self.size) % self.cap] = value
self.size += 1
return True
def deQueue(self) -> bool:
if self.size == 0:
return False
self.head = (self.head + 1) % self.cap
self.size -= 1
return True
def Front(self) -> int:
if self.size == 0:
return -1
return self.q[self.head]
def Rear(self) -> int:
if self.size == 0:
return -1
return self.q[(self.head + self.size - 1) % self.cap]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capclass MyCircularQueue {
private int[] q;
private int head, size, cap;
public MyCircularQueue(int k) {
q = new int[k];
head = 0;
size = 0;
cap = k;
}
public boolean enQueue(int value) {
if (size == cap) {
return false;
}
q[(head + size) % cap] = value;
size++;
return true;
}
public boolean deQueue() {
if (size == 0) {
return false;
}
head = (head + 1) % cap;
size--;
return true;
}
public int Front() {
if (size == 0) {
return -1;
}
return q[head];
}
public int Rear() {
if (size == 0) {
return -1;
}
return q[(head + size - 1) % cap];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == cap;
}
}class MyCircularQueue {
public:
vector<int> q;
int head, size, cap;
MyCircularQueue(int k) {
q.assign(k, 0);
head = 0;
size = 0;
cap = k;
}
bool enQueue(int value) {
if (size == cap) {
return false;
}
q[(head + size) % cap] = value;
size++;
return true;
}
bool deQueue() {
if (size == 0) {
return false;
}
head = (head + 1) % cap;
size--;
return true;
}
int Front() {
if (size == 0) {
return -1;
}
return q[head];
}
int Rear() {
if (size == 0) {
return -1;
}
return q[(head + size - 1) % cap];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == cap;
}
};type MyCircularQueue struct {
q []int
head int
size int
cap int
}
func Constructor(k int) MyCircularQueue {
q := make([]int, k)
head := 0
size := 0
return MyCircularQueue{q: q, head: head, size: size, cap: k}
}
func (this *MyCircularQueue) EnQueue(value int) bool {
if this.size == this.cap {
return false
}
this.q[(this.head+this.size)%this.cap] = value
this.size++
return true
}
func (this *MyCircularQueue) DeQueue() bool {
if this.size == 0 {
return false
}
this.head = (this.head + 1) % this.cap
this.size--
return true
}
func (this *MyCircularQueue) Front() int {
if this.size == 0 {
return -1
}
return this.q[this.head]
}
func (this *MyCircularQueue) Rear() int {
if this.size == 0 {
return -1
}
return this.q[(this.head+this.size-1)%this.cap]
}
func (this *MyCircularQueue) IsEmpty() bool {
return this.size == 0
}
func (this *MyCircularQueue) IsFull() bool {
return this.size == this.cap
}var MyCircularQueue = function(k) {
this.q = new Array(k).fill(0);
this.head = 0;
this.size = 0;
this.cap = k;
};
MyCircularQueue.prototype.enQueue = function(value) {
if (this.size === this.cap) {
return false;
}
this.q[(this.head + this.size) % this.cap] = value;
this.size++;
return true;
};
MyCircularQueue.prototype.deQueue = function() {
if (this.size === 0) {
return false;
}
this.head = (this.head + 1) % this.cap;
this.size--;
return true;
};
MyCircularQueue.prototype.Front = function() {
if (this.size === 0) {
return -1;
}
return this.q[this.head];
};
MyCircularQueue.prototype.Rear = function() {
if (this.size === 0) {
return -1;
}
return this.q[(this.head + this.size - 1) % this.cap];
};
MyCircularQueue.prototype.isEmpty = function() {
return this.size === 0;
};
MyCircularQueue.prototype.isFull = function() {
return this.size === this.cap;
};class MyCircularQueue {
q: number[];
head: number;
size: number;
cap: number;
constructor(k: number) {
this.q = new Array(k).fill(0);
this.head = 0;
this.size = 0;
this.cap = k;
}
enQueue(value: number): boolean {
if (this.size === this.cap) {
return false;
}
this.q[(this.head + this.size) % this.cap] = value;
this.size++;
return true;
}
deQueue(): boolean {
if (this.size === 0) {
return false;
}
this.head = (this.head + 1) % this.cap;
this.size--;
return true;
}
Front(): number {
if (this.size === 0) {
return -1;
}
return this.q[this.head];
}
Rear(): number {
if (this.size === 0) {
return -1;
}
return this.q[(this.head + this.size - 1) % this.cap];
}
isEmpty(): boolean {
return this.size === 0;
}
isFull(): boolean {
return this.size === this.cap;
}
}其他解法
数组实现靠取模让下标在固定空间里循环，内存连续；链表实现按需创建节点，只靠 size 控制容量。各操作都是 O(1)。
解法 2：单链表 时间 O(1)，空间 O(k)
用单链表保存队列元素，维护头指针 head、尾指针 tail 和当前元素个数 size。入队时先检查 size 是否已达容量，再在 tail 后接上新节点。出队时把 head 后移一位。队首和队尾分别读 head 和 tail。
不需要取模，也不用预先分配整块数组。代价是每次入队都要新建节点，并且每个元素多一个指针的开销。
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
class MyCircularQueue:
def __init__(self, k: int = 3):
self.cap = k
self.size = 0
self.head = None
self.tail = None
def enQueue(self, value: int) -> bool:
if self.size == self.cap:
return False
node = ListNode(value)
if self.size == 0:
self.head = self.tail = node
else:
self.tail.next = node
self.tail = node
self.size += 1
return True
def deQueue(self) -> bool:
if self.size == 0:
return False
self.head = self.head.next
self.size -= 1
return True
def Front(self) -> int:
return -1 if self.size == 0 else self.head.val
def Rear(self) -> int:
return -1 if self.size == 0 else self.tail.val
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capclass MyCircularQueue {
private static class Node {
int val;
Node next;
Node(int v) { val = v; }
}
private Node head, tail;
private int size, cap;
public MyCircularQueue(int k) {
cap = k;
}
public boolean enQueue(int value) {
if (size == cap) return false;
Node node = new Node(value);
if (size == 0) head = tail = node;
else {
tail.next = node;
tail = node;
}
size++;
return true;
}
public boolean deQueue() {
if (size == 0) return false;
head = head.next;
size--;
return true;
}
public int Front() { return size == 0 ? -1 : head.val; }
public int Rear() { return size == 0 ? -1 : tail.val; }
public boolean isEmpty() { return size == 0; }
public boolean isFull() { return size == cap; }
}class MyCircularQueue {
struct Node {
int val;
Node* next;
Node(int v) : val(v), next(nullptr) {}
};
Node* head = nullptr;
Node* tail = nullptr;
int size = 0, cap;
public:
MyCircularQueue(int k) : cap(k) {}
bool enQueue(int value) {
if (size == cap) return false;
Node* node = new Node(value);
if (size == 0) head = tail = node;
else {
tail->next = node;
tail = node;
}
size++;
return true;
}
bool deQueue() {
if (size == 0) return false;
Node* old = head;
head = head->next;
delete old;
size--;
return true;
}
int Front() { return size == 0 ? -1 : head->val; }
int Rear() { return size == 0 ? -1 : tail->val; }
bool isEmpty() { return size == 0; }
bool isFull() { return size == cap; }
};type qNode struct {
val int
next *qNode
}
type MyCircularQueue struct {
head, tail *qNode
size, cap int
}
func Constructor(k int) MyCircularQueue {
return MyCircularQueue{cap: k}
}
func (this *MyCircularQueue) EnQueue(value int) bool {
if this.size == this.cap {
return false
}
node := &qNode{val: value}
if this.size == 0 {
this.head, this.tail = node, node
} else {
this.tail.next = node
this.tail = node
}
this.size++
return true
}
func (this *MyCircularQueue) DeQueue() bool {
if this.size == 0 {
return false
}
this.head = this.head.next
this.size--
return true
}
func (this *MyCircularQueue) Front() int {
if this.size == 0 {
return -1
}
return this.head.val
}
func (this *MyCircularQueue) Rear() int {
if this.size == 0 {
return -1
}
return this.tail.val
}
func (this *MyCircularQueue) IsEmpty() bool {
return this.size == 0
}
func (this *MyCircularQueue) IsFull() bool {
return this.size == this.cap
}var MyCircularQueue = function(k) {
this.cap = k;
this.size = 0;
this.head = null;
this.tail = null;
};
MyCircularQueue.prototype.enQueue = function(value) {
if (this.size === this.cap) return false;
const node = { val: value, next: null };
if (this.size === 0) {
this.head = this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
return true;
};
MyCircularQueue.prototype.deQueue = function() {
if (this.size === 0) return false;
this.head = this.head.next;
this.size--;
return true;
};
MyCircularQueue.prototype.Front = function() {
return this.size === 0 ? -1 : this.head.val;
};
MyCircularQueue.prototype.Rear = function() {
return this.size === 0 ? -1 : this.tail.val;
};
MyCircularQueue.prototype.isEmpty = function() {
return this.size === 0;
};
MyCircularQueue.prototype.isFull = function() {
return this.size === this.cap;
};type QNode = { val: number; next: QNode | null };
class MyCircularQueue {
private head: QNode | null = null;
private tail: QNode | null = null;
private size = 0;
private cap: number;
constructor(k: number) {
this.cap = k;
}
enQueue(value: number): boolean {
if (this.size === this.cap) return false;
const node: QNode = { val: value, next: null };
if (this.size === 0) {
this.head = this.tail = node;
} else {
this.tail!.next = node;
this.tail = node;
}
this.size++;
return true;
}
deQueue(): boolean {
if (this.size === 0) return false;
this.head = this.head!.next;
this.size--;
return true;
}
Front(): number {
return this.size === 0 ? -1 : this.head!.val;
}
Rear(): number {
return this.size === 0 ? -1 : this.tail!.val;
}
isEmpty(): boolean {
return this.size === 0;
}
isFull(): boolean {
return this.size === this.cap;
}
}