To the chase

Design a circular two-ended queue

Design and implement a double – ended queue.

Your implementation needs to support the following:

  • MyCircularDeque(k) : constructor, double-ended queue size k.
  • InsertFront () : Adds an element to the head of a double-ended queue. Returns true on success.
  • InsertLast () : Adds an element to the end of a double-ended queue. Returns true on success.
  • DeleteFront () : Removes an element from the head of a double-ended queue. Returns true on success.
  • DeleteLast () : Removes an element from the end of a two-ended queue. Returns true on success.
  • GetFront () : Gets an element from the head of a two-ended queue. If the two-end queue is empty, -1 is returned.
  • GetRear () : Gets the last element of a two-ended queue. If the two-end queue is empty, -1 is returned.
  • IsEmpty () : checks whether the double-ended queue isEmpty.
  • IsFull () : checks whether the two-end queue isFull.

Example:

MyCircularDeque circularDeque = new MycircularDeque(3); Circulardeque.insertlast (1); // Set the capacity to 3 circulardeque.insertlast (1); // Return true circulardeque.insertlast (2); / / return true circularDeque. InsertFront (3); / / return true circularDeque. InsertFront (4); // Already full, return false circulardeque.getrear (); Circulardeque.isfull (); // Return true circulardeque.deletelast (); / / return true circularDeque. InsertFront (4); // Return true circulardeque.getFront (); / / return 4Copy the code

If you are not familiar with queues and circular queues, please refer to the previous article: Implementing JS circular queues by Hand

In this case, different from the above, it needs to implement double ends, that is, it needs to implement the following methods:

  1. infrontFront add node
  2. deleterearBefore the node

So let’s start with the constructor.

Build the constructor

Just like a normal loop queue, no difference, okay

/**
 * @param {number} k
 */
var MyCircularDeque = function(k) {
    this.capatity = k
    this.queue = new Array(k)
    this.front = 0
    this.rear = 0
};
Copy the code

Implementation infrontFront insertion node

Unlike normal circular queues, new nodes can be inserted at the node before the front, and the front node changes accordingly. So the idea is, move the front node forward, and then assign the front node.

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertFront = function(value) {
    if (this.isFull()) {
        return false
    } else{
        this.front = this.front === 0 ? this.capatity - 1 : this.front - 1
        this.queue[this.front] = value
        return true
    }
};
Copy the code

Implement adding nodes at the end of the queue

Just like a normal circular queue

/** * @param {number} value * @return {boolean} */ MyCircularDeque.prototype.insertLast = function(value) { if (this.isFull()) { return false } else { this.queue[this.rear] = value this.rear = (this.rear + 1) % this.capatity return  true } };Copy the code

Delete the front node

Because a normal circular queue follows a first-in, first-out rule, removing a front node is the same as removing a node in a normal circular queue

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function() {
    if (this.isEmpty()) {
        return false
    } else {
        this.queue[this.front] = null
        this.front = (this.front + 1) % this.capatity
        return true
    }
};
Copy the code

Delete the tail node

Move the left rear pointer and set the node corresponding to the move pointer to empty, so it’s easy to understand, I won’t do the diagram

/** * @return {boolean} */ MyCircularDeque.prototype.deleteLast = function() { if (this.isEmpty()) { return false } else  { this.rear = this.rear === 0 ? this.capatity - 1 : this.rear - 1 this.queue[this.rear] = null return true } };Copy the code

Get the first and last nodes, judge empty, judge full and implement the same as normal circular queue

/** * @return {number} */ MyCircularDeque.prototype.getFront = function() { if (this.isEmpty()) { return -1 } else { return this.queue[this.front] } }; /** * @return {number} */ MyCircularDeque.prototype.getRear = function() { if (this.isEmpty()) { return -1 } else { let index = this.rear === 0 ? this.capatity - 1 : this.rear - 1 return this.queue[index] } }; /** * @return {boolean} */ MyCircularDeque.prototype.isEmpty = function() { return this.rear === this.front && ! this.queue[this.front] && this.queue[this.front] ! = = 0}; /** * @return {boolean} */ MyCircularDeque.prototype.isFull = function() { return this.rear === this.front && this.queue[this.front] ! == null && this.queue[this.front] ! == undefined };Copy the code

So put it all together

Complete code:

/** * @param {number} k */ var MyCircularDeque = function(k) { this.capatity = k this.queue = new Array(k) this.front = 0 this.rear = 0 }; /** * @param {number} value * @return {boolean} */ MyCircularDeque.prototype.insertFront = function(value) { if (this.isFull()) { return false } else{ this.front = this.front === 0 ? this.capatity - 1 : this.front - 1 this.queue[this.front] = value return true } }; /** * @param {number} value * @return {boolean} */ MyCircularDeque.prototype.insertLast = function(value) { if (this.isFull()) { return false } else { this.queue[this.rear] = value this.rear = (this.rear + 1) % this.capatity return  true } }; /** * @return {boolean} */ MyCircularDeque.prototype.deleteFront = function() { if (this.isEmpty()) { return false } else { this.queue[this.front] = null this.front = (this.front + 1) % this.capatity return true } }; /** * @return {boolean} */ MyCircularDeque.prototype.deleteLast = function() { if (this.isEmpty()) { return false } else  { this.rear = this.rear === 0 ? this.capatity - 1 : this.rear - 1 this.queue[this.rear] = null return true } }; /** * @return {number} */ MyCircularDeque.prototype.getFront = function() { if (this.isEmpty()) { return -1 } else { return this.queue[this.front] } }; /** * @return {number} */ MyCircularDeque.prototype.getRear = function() { if (this.isEmpty()) { return -1 } else { let index = this.rear === 0 ? this.capatity - 1 : this.rear - 1 return this.queue[index] } }; /** * @return {boolean} */ MyCircularDeque.prototype.isEmpty = function() { return this.rear === this.front && ! this.queue[this.front] && this.queue[this.front] ! = = 0}; /** * @return {boolean} */ MyCircularDeque.prototype.isFull = function() { return this.rear === this.front && this.queue[this.front] ! == null && this.queue[this.front] ! == undefined }; /** * Your MyCircularDeque object will be instantiated and called as such: * var obj = new MyCircularDeque(k) * var param_1 = obj.insertFront(value) * var param_2 = obj.insertLast(value) * var param_3 = obj.deleteFront() * var param_4 = obj.deleteLast() * var param_5 = obj.getFront() * var param_6 = obj.getRear() * var param_7 = obj.isEmpty() * var param_8 = obj.isFull() */Copy the code

If you fully understand the content of the JS loop queue with you, then this problem is really very simple!