在 JavaScript 中实现循环队列环形缓冲区

Z时代
2024-01-10
分类：综合

循环队列

循环队列是一种线性数据结构，其中的操作基于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());