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); // 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();  				/ / return 2
circularDeque.isFull();				        / / return true
circularDeque.deleteLast();			        / / return true
circularDeque.insertFront(4);			        / / return true
circularDeque.getFront();				/ / return 4
Copy the code

Tip:

All values in the range of [1, 1000] Number of operations in the range of [1, 1000] Please do not use the built-in dual-endian queue library.

Ideas:

Define an empty array arR that is equal to the length of the linked list to hold the array. Define a head node at the top and a tail node head,tail, if the head node is added, subtract one. If the tail node is added, add one If CNT is equal to the length of arr, the array is full. If CNT is equal to 0, the array is empty.

 let arr = []; // Use an empty array to hold the list
 let head,tail,cnt;// define a header (head), a tail (tail), and a counter (CNT)
var MyCircularDeque = function(k) {
    arr.length = k;// Define an empty array length equal to the list length
    // initialize the header, tail, and counter
    head = 0;
    tail = 0;
    cnt = 0;
};

/ * * *@param {number} value
 * @return {boolean}* /
MyCircularDeque.prototype.insertFront = function(value) {
    // Check whether the array is full
    if(MyCircularDeque.prototype.isFull()) return false;
    // If the list head is added, it is added one bit before the head, so the head is subtracted by one
    head = (head - 1 + arr.length) % arr.length;
    // Add a new header successfully
    arr[head] = value;
    // The counter increases by one
    cnt ++;
    return true;
};

/ * * *@param {number} value
 * @return {boolean}* /
MyCircularDeque.prototype.insertLast = function(value) {
    // Check if the list is full
    if(MyCircularDeque.prototype.isFull()) return false;
    // Since tail is always empty, we assign a value to tail directly
    arr[tail] = value;
    // Keep tail as an empty node,% to prevent loops
    tail = (tail + 1) % arr.length;
    // Add one to the calculator
    cnt ++;
    return true;
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.deleteFront = function() {
    // If the list is empty, return false.
    if(MyCircularDeque.prototype.isEmpty()) return false;
    // Delete the head node head one bit later,% to prevent loops
    head = (head + 1) % arr.length;
    cnt --;
    return true;
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.deleteLast = function() {
    // If the list is empty, return false.
    if(MyCircularDeque.prototype.isEmpty()) return false;
    // When we remove the tail, we move the tail forward by one bit
    tail = (tail - 1 + arr.length) % arr.length;
    cnt --;
    return true;
};

/ * * *@return {number}* /
MyCircularDeque.prototype.getFront = function() {
    if(MyCircularDeque.prototype.isEmpty()) return -1;
    //head is the head node
    return arr[head]
};

/ * * *@return {number}* /
MyCircularDeque.prototype.getRear = function() {
    if(MyCircularDeque.prototype.isEmpty()) return -1;
    // We need to subtract one bit from the tail to prevent the length of a negative addend
    return arr[(tail - 1 + arr.length) % arr.length]
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.isEmpty = function() {
    // CNT equals 0 is an empty array
    return cnt == 0
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.isFull = function() {
    // CNT equals the length of the array and the array is full
    return cnt == arr.length;
};
Copy the code