Implement circular queue ring buffer in JavaScript

Circular queue

Circular queue is a linear data structure. Its operation is based on the FIFO (first in, first out) principle, and the last The positions are connected back to the first position, forming a loop. It is also called a "ring buffer".

One benefit of circular queues is that we can utilize the space in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is space in front of the queue. But using a circular queue, we can use space to store new values.

Question

We need to design the implementation of circular queue in JavaScript to support the following operations:

• MyCircularQueue(k) - constructor, the queue The size of is set to k.

• Front() - Gets the front item from the queue. If the queue is empty, -1 is returned.

• Rear() - Retrieve the last item from the queue. If the queue is empty, -1 is returned.

• enQueue(value) - Inserts an element into a circular queue. Returns true if the operation is successful.

• deQueue() - Removes an element from a circular queue. Returns true if the operation is successful.

• isEmpty() - Checks if the circular queue is empty.

• isFull() - Checks if the circular queue is full.

Example

The following is the code -

Demo

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());

Output

true
true
false
2
true
true
true
3

The above is the detailed content of Implement circular queue ring buffer in JavaScript. For more information, please follow other related articles on the PHP Chinese website!