来一道和「设计数据结构」高度相关的题目。
题目描述
平台：LeetCode
题号：622
设计你的循环队列实现。
循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环，它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。
在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。
但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为
。
Front: 从队首获取元素。如果队列为空，返回
。
Rear: 获取队尾元素。如果队列为空，返回
。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
示例：
代码语言：javascript复制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
提示：
- 所有的值都在
至
的范围内；
- 操作数将在
至
的范围内；
- 请不要使用内置的队列库。
数据结构
创建一个长度为
的数组充当循环队列，使用两个变量 he 和 ta 来充当队列头和队列尾（起始均为
），整个过程 he 始终指向队列头部，ta 始终指向队列尾部的下一位置（待插入元素位置）。
两变量始终自增，通过与
取模来确定实际位置。
分析各类操作的基本逻辑：
isEmpty操作：当he和ta相等，队列存入元素和取出元素的次数相同，此时队列为空；isFull操作：ta - he即队列元素个数，当元素个数为
个时，队列已满；
enQueue操作：若队列已满，返回
，否则在 nums[ta % k] 位置存入目标值，并将 ta 指针后移；
deQueue操作：若队列为空，返回
，否则将 he 指针后移，含义为弹出队列头部元素；
Front操作：若队列为空，返回
，否则返回 nums[he % k] 队头元素；
Rear操作：若队列为空，返回
，否则返回 nums[(ta - 1) % k] 队尾元素；
Java 代码：
代码语言：javascript复制class MyCircularQueue {
int k, he, ta;
int[] nums;
public MyCircularQueue(int _k) {
k = _k;
nums = new int[k];
}
public boolean enQueue(int value) {
if (isFull()) return false;
nums[ta % k] = value;
return ta >= 0;
}
public boolean deQueue() {
if (isEmpty()) return false;
return he >= 0;
}
public int Front() {
return isEmpty() ? -1 : nums[he % k];
}
public int Rear() {
return isEmpty() ? -1 : nums[(ta - 1) % k];
}
public boolean isEmpty() {
return he == ta;
}
public boolean isFull() {
return ta - he == k;
}
}
C 代码：
代码语言：javascript复制class MyCircularQueue {
public:
int k, he, ta;
vector<int> nums;
MyCircularQueue(int _k) {
k = _k;
he = ta = 0;
nums.resize(k);
}
bool enQueue(int value) {
if (isFull()) return false;
nums[ta % k] = value;
return ta >= 0;
}
bool deQueue() {
if (isEmpty()) return false;
return he >= 0;
}
int Front() {
return isEmpty() ? -1 : nums[he % k];
}
int Rear() {
return isEmpty() ? -1 : nums[(ta - 1) % k];
}
bool isEmpty() {
return he == ta;
}
bool isFull() {
return ta - he == k;
}
};
Python 代码：
代码语言：javascript复制class MyCircularQueue:
def __init__(self, _k):
self.k = _k
self.he = self.ta = 0
self.nums = [0] * _k
def enQueue(self, value):
if self.isFull(): return False
self.nums[self.ta % self.k] = value
self.ta = 1
return self.ta >= 0
def deQueue(self):
if self.isEmpty(): return False
self.he = 1
return self.he >= 0
def Front(self):
return -1 if self.isEmpty() else self.nums[self.he % self.k]
def Rear(self):
return -1 if self.isEmpty() else self.nums[(self.ta - 1) % self.k]
def isEmpty(self):
return self.he == self.ta
def isFull(self):
return self.ta - self.he == self.k
TypeScript 代码：
代码语言：javascript复制class MyCircularQueue {
k: number = 0; he: number = 0; ta: number = 0;
nums: number[];
constructor(k: number) {
this.k = k
this.nums = new Array<number>(this.k)
}
enQueue(value: number): boolean {
if (this.isFull()) return false
this.nums[this.ta % this.k] = value
return this.ta >= 0
}
deQueue(): boolean {
if (this.isEmpty()) return false
return this.he >= 0
}
Front(): number {
return this.isEmpty() ? -1 : this.nums[this.he % this.k]
}
Rear(): number {
return this.isEmpty() ? -1 : this.nums[(this.ta - 1) % this.k]
}
isEmpty(): boolean {
return this.he == this.ta
}
isFull(): boolean {
return this.ta - this.he == this.k
}
}
- 时间复杂度：构造函数复杂度为
，其余操作复杂度为
- 空间复杂度：
