题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 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
注:循环队列的实现难点主要在于 full 和 empty 这两种状态的判断,都是头指针和尾指针处于相邻的状态
接下来的两种解决方案都非常有意思,记录一下
算法1 (滑动窗口)
front表示队首元素的下标,rear表示下一个队尾元素的下标,他们在存储的时候都是不取模的
举例,可能队列大小只有3,但是front和rear的值可能最后是-100,-5,1000,2000
也就是说不存取模后的结果,只在操作过程中累加或累减(详情可看代码)
第1次插入,rear是1
第2次插入,rear是2
第3次插入,rear是3
第3次插入,rear是4(注意,不取模,只在读写对应元素的时候取模)
这么做的好处是空间复杂度是O(k),代码简洁一些
缺点是对使用次数有限制,如果超出front和rear使用类型的存储数据范围,可能会出错。
时空复杂度
- 时间复杂度:构造函数复杂度为 O(k),其余操作复杂度为 O(1)
- 空间复杂度:O(k)
Java 代码
class MyCircularDeque {
int[] q;
int front, rear, k;
public MyCircularDeque(int _k) {
k = _k;
q = new int[k];
}
public boolean insertFront(int value) {
if (isFull()) return false;
front--;
q[(front % k + k) % k] = value;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
q[(rear % k + k) % k] = value;
rear++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
front++;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
rear--;
return true;
}
public int getFront() {
return isEmpty() ? -1 : q[(front % k + k) % k];
}
public int getRear() {
return isEmpty() ? -1 : q[((rear - 1) % k + k) % k];
}
public boolean isEmpty() {
return rear == front;
}
public boolean isFull() {
return rear - front == k;
}
}
通过率
算法2 (额外空间)
开辟 k+1 个空间,巧妙地区分 full 和 empty
- 当状态为 full 的时候:rear != front 且 (rear + 1) % k == front
- 而状态为 empty 的时候:rear == front
时空复杂度
- 时间复杂度:构造函数复杂度为 O(k),其余操作复杂度为 O(1)
- 空间复杂度:O(k+1)
java 代码
class MyCircularDeque {
int[] q;
int front, rear, k;
public MyCircularDeque(int _k) {
k = _k + 1;
q = new int[k];
}
public boolean insertFront(int value) {
if (isFull()) return false;
if (--front < 0) front += k;
q[front] = value;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
q[rear] = value;
if (++rear >= k) rear -= k;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
if (++front >= k) front -= k;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
if (--rear < 0) rear += k;
return true;
}
public int getFront() {
return isEmpty() ? -1 : q[front];
}
public int getRear() {
return isEmpty() ? -1 : q[(rear - 1 + k) % k];
}
public boolean isEmpty() {
return rear == front;
}
public boolean isFull() {
return (rear + 1) % k == front;
}
}