Topic describes

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.

Subject train of thought

First we need to borrow the Array Array from JS to store the values of the queue (you can also implement a linked list to achieve this, in this case using arrays).

Next we create a head and tail to store the head and tail Pointers, respectively

Finally, create two variables count, Max to assist the operation

The subject code

In the constructor, we initialize the variables defined above

var MyCircularDeque = function (k) {
    this.list = [];
    this.count = 0;
    this.head = 0;
    this.tail = 0;
    this.max = k;
};
Copy the code

Next, write void and full operations

/ / found empty
MyCircularDeque.prototype.isEmpty = function () {
    if (this.count === 0) return true;
    return false;
};
Copy the code
/ / to full
MyCircularDeque.prototype.isFull = function () {
    if (this.max === this.count) return true;
    return false;
};
Copy the code

Core point, insert top, insert tail, delete top, delete tail

Implement insert top

Boundary condition: Full non-insertable returns false

If the head pointer can be inserted, then the head node is inserted minus one position. Here is a trick: to keep the head pointer within Max, add Max after head-1.

Assign to the element in the list at position head-1, and print

MyCircularDeque.prototype.insertFront = function (value) {
    if (this.isFull()) return false;
    this.head = (this.head - 1 + this.max) % this.max;
    this.list[this.head] = value;
    this.count += 1;
    return true;
};
Copy the code

Insert the tail

The boundary conditions are the same, return false when full

When inserting, you can insert directly on the tail node, so the tail node is calculated as tail % Max

Remember to adjust the count and Max values after processing

MyCircularDeque.prototype.insertLast = function (value) {
    if (this.isFull()) return false;
    this.list[this.tail % this.max] = value;
    this.tail += 1;
    if (this.tail === this.max) this.tail = 0;
    this.count += 1;
    return true;
};
Copy the code

Remove the top

The head value is updated and the count value is updated

MyCircularDeque.prototype.deleteFront = function () {
    if (this.isEmpty()) return false;
    // this.list.splice(this.head, 1);
    this.head = (this.head + 1) % this.max;
    this.count -= 1;
    return true;
};
Copy the code

Remove the tail

The head value is updated and the count value is updated

MyCircularDeque.prototype.deleteLast = function () {
    if (this.isEmpty()) return false;
    // this.list.splice(this.tail - 1, 1);
    this.tail = (this.tail - 1 + this.max) % this.max;
    this.count -= 1;
    return true;
};
Copy the code

Get the top element

Return the head element

MyCircularDeque.prototype.getFront = function () {
    if (this.isEmpty()) return -1;
    return this.list[this.head];
};
Copy the code

Get the tail element

Return the tail element

MyCircularDeque.prototype.getRear = function () {
    if (this.isEmpty()) return -1;
    return this.list[(this.tail - 1 + this.max) % this.max];
};
Copy the code

complete

Above for the design of a double – end loop queue all code implementation, you can try oh ~ ~ ~