The title

Design your loop queue implementation. A circular queue is a linear data structure that operates on a FIFO (first-in, first-out) basis and the tail of the queue is connected behind the head of the queue to form a loop. It is also known as a “ring buffer”.

One of the nice things about a circular queue is that we can use the space that the queue has previously used. In a normal queue, once a queue is full, we cannot insert the next element, even though there is still space in front of the queue. But with circular queues, we can use that space to store new values.

Your implementation should support the following:

MyCircularQueue(k): constructor that sets the queue length to K. Front: Retrieves elements from the team leader. If the queue is empty, -1 is returned. Rear: Gets the last element of the team. If the queue is empty, -1 is returned. EnQueue (value): Inserts an element into the loop queue. Return true on successful insertion. DeQueue (): Removes an element from the loop queue. Return true if deleted successfully. IsEmpty (): checks if the loop queue isEmpty. IsFull (): checks if the loop queue isFull.

Source: force buckle

implementation

The constructor

var MyCircularQueue = function(k) {
    this.arr = new Array(k); // Store data
    this.cnt = 0; // The number of records
    this.tail = 0; // Record the tail pointer
    this.head = 0; // Record the header pointer
};
Copy the code

The enQueue () team

MyCircularQueue.prototype.enQueue = function(value) {
    if (this.isFull()) return false
    this.arr[this.tail] = value // Always add elements to tail
    this.cnt++
    this.tail = (this.tail + 1) % this.arr.length // tail moves back to the first position after the length is exceeded
    return true
};
Copy the code

DeQueue () out of the team

MyCircularQueue.prototype.deQueue = function() {
    if (this.isEmpty()) return false
    this.cnt--
    this.head = (this.head + 1) % this.arr.length // head moves back to the first place after the length exceeds
    return true
};
Copy the code

The Front (the) first

MyCircularQueue.prototype.Front = function() {
    if (this.isEmpty()) return -1
    return this.arr[this.head]
};
Copy the code

The Rear () a party

MyCircularQueue.prototype.Rear = function() {
    if (this.isEmpty()) return -1
    const idx = (this.tail + this.arr.length - 1) % this.arr.length // The tail of the queue is a bit to the left of the tail
    return this.arr[idx]
};
Copy the code

IsEmpty () isEmpty

MyCircularQueue.prototype.isEmpty = function() {
    return this.cnt === 0
};
Copy the code

IsFull () isFull

MyCircularQueue.prototype.isFull = function() {
    return this.cnt === this.arr.length
};
Copy the code