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

王林转载: 2023-08-22 17:57:08 367浏览

循环队列

循环队列是一种线性数据结构，它的操作是基于FIFO（先进先出）原则进行的，并且最后一个位置连接回第一个位置，形成一个循环。它也被称为“环形缓冲区”。

循环队列的一个好处是我们可以利用队列前面的空间。在普通队列中，一旦队列变满，即使队列前面有空间，我们也无法插入下一个元素。但是使用循环队列，我们可以使用空间来存储新的值。

问题

我们需要在JavaScript中设计循环队列的实现，支持以下操作：

MyCircularQueue(k) - 构造函数，将队列的大小设置为k。
Front() - 从队列中获取前面的项。如果队列为空，则返回-1。
Rear() - 从队列中获取最后一项。如果队列为空，则返回-1。
enQueue(value) - 将元素插入循环队列。如果操作成功，则返回true。
deQueue() - 从循环队列中删除一个元素。如果操作成功，则返回true。
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());