队列
解题思路
定义循环变量 front 和 rear：
- front 指向队列头部第 1 个有效数据的位置；
- rear 指向队列尾部（即最后 1 个有效数据）的下一个位置，即下一个从队尾入队元素的位置；
为了避免「队列为空」和「队列为满」的判别条件冲突，有意浪费了一个位置：
- 判别队列为空的条件是：
front == rear；- 判别队列为满的条件是：
(rear + 1) % capacity == front；可以这样理解，当 rear 循环到数组的前面，要从后面追上 front，还差一格的时候，判定队列为满；因为有循环的出现，要特别注意处理数组下标可能越界的情况；指针后移的时候 下标 +1 ，并且为了防止数组下标越界要取模；
图解
复杂度
-
时间复杂度：初始化和每项操作的时间复杂度均为
O(1)； -
空间复杂度：
O(k)，其中 k 为给定的队列元素数目；
代码实现
var MyCircularDeque = function (k) {
this.front = 0;
this.rear = 0;
this.capacity = k + 1;
this.arr = new Array(this.capacity);
};
MyCircularDeque.prototype.insertFront = function (value) {
if (this.isFull()) {
return false;
}
this.front = (this.front - 1 + this.capacity) % this.capacity;
this.arr[this.front] = value;
return true;
};
MyCircularDeque.prototype.insertLast = function (value) {
if (this.isFull()) {
return false;
}
this.arr[this.rear] = value;
this.rear = (this.rear + 1) % this.capacity;
return true;
};
MyCircularDeque.prototype.deleteFront = function () {
if (this.isEmpty()) {
return false;
}
// front 被设计在数组的开头，所以是 +1
this.front = (this.front + 1) % this.capacity;
return true;
};
MyCircularDeque.prototype.deleteLast = function () {
if (this.isEmpty()) {
return false;
}
// rear 被设计在数组的末尾，所以是 -1
this.rear = (this.rear - 1 + this.capacity) % this.capacity;
return true;
};
MyCircularDeque.prototype.getFront = function () {
if (this.isEmpty()) {
return -1;
}
return this.arr[this.front];
};
MyCircularDeque.prototype.getRear = function () {
if (this.isEmpty()) {
return -1;
}
// 当 rear 为 0 时防止数组越界
return this.arr[(this.rear - 1 + this.capacity) % this.capacity];
};
MyCircularDeque.prototype.isEmpty = function () {
return this.front === this.rear;
};
MyCircularDeque.prototype.isFull = function () {
// 注意：这是这个经典设计的原因
return (this.rear + 1) % this.capacity === this.front;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 622. 设计循环队列
上一篇
评论
