循环队列是一种线性数据结构，其中的操作基于FIFO（先进先出）原则进行，最后一个位置连接回第一个位置，形成一个循环。它也被称为“环形缓冲区”。
循环队列的好处之一是我们可以利用队列前面的空间。在普通队列中，一旦队列已满，即使队列前面有空间，我们也无法插入下一个元素。但是使用循环队列，我们可以使用空间来存储新值。
我们需要在 JavaScript 中设计循环队列的实现，以支持以下操作 -
MyCircularQueue(k) − 构造函数，设置队列大小为k。
Front()- 从队列中获取最前面的项目。如果队列为空，则返回-1。
Rear()- 从队列中获取最后一项。如果队列为空，则返回-1。
enQueue(value)− 向循环队列中插入一个元素。如果操作成功，则返回 true。
deQueue()− 从循环队列中删除一个元素。如果操作成功则返回真。
isEmpty() − 检查循环队列是否为空。
isFull() − 检查循环队列是否已满。
以下是代码 -
const CircularQueue = function(k) {
this.size = k
this.queue = []
this.start1 = 0
this.end1 = 0
this.start2 = 0
this.end2 = 0
}
CircularQueue.prototype.enQueue = function(value) {
if(this.isFull()) {
return false
}
if(this.end2 <=this.size- 1) {
this.queue[this.end2++] = value
} else {
this.queue[this.end1++] = value
}
return true
}
CircularQueue.prototype.deQueue = function() {
if(this.isEmpty()) {
return false
}
if(this.queue[this.start2] !== undefined) {
this.queue[this.start2++] = undefined
} else {
this.queue[this.start1++] = undefined
}
return true
}
CircularQueue.prototype.Front = function() {
if(this.isEmpty()) {
return -1
}
return this.queue[this.start2] === undefined ? this.queue[this.start1] : this.queue[this.start2]
}
CircularQueue.prototype.Rear = function() {
if(this.isEmpty()) {
return -1
}
return this.queue[this.end1 - 1] === undefined ? this.queue[this.end2 - 1] : this.queue[this.end1 - 1]
}
CircularQueue.prototype.isEmpty = function() {
if(this.end2 - this.start2 + this.end1 - this.start1 <= 0) {
return true
}
return false
}
CircularQueue.prototype.isFull = function() {
if(this.end2 - this.start2 + this.end1 - this.start1 >= this.size) {
return true
}
return false
}
const queue = new CircularQueue(2);
console.log(queue.enQueue(1));
console.log(queue.enQueue(2));
console.log(queue.enQueue(3));
console.log(queue.Rear());
console.log(queue.isFull());
console.log(queue.deQueue());
console.log(queue.enQueue(3));
console.log(queue.Rear());输出结果true true false 2 true true true 3