Look a hundred times beauty, beauty is not necessarily yours. But if you run the algorithm a hundred times, the knowledge is yours

Who can have nine floors? No need to get up!

Title address

The title

Design and implement a double – ended queue.

Your implementation needs to support the following:

  • MyCircularDeque(k): constructor, the size of the two-ended queue isk.
  • insertFront(): Adds an element to the head of a two-ended queue. Returns if the operation succeedstrue.
  • insertLast(): Adds an element to the end of a double-ended queue. Returns if the operation succeedstrue.
  • deleteFront(): Removes an element from the head of a two-ended queue. Returns if the operation succeedstrue.
  • deleteLast(): Removes an element from the end of a two-ended queue. Returns if the operation succeedstrue.
  • getFront(): Retrieves an element from the head of a two-ended queue. Returns if the two-end queue is empty- 1.
  • getRear(): Gets the last element of a double-endian queue. Returns if the two-end queue is empty- 1.
  • isEmpty(): Checks whether the two-end queue is empty.
  • isFull(): Checks whether the two-end queue is full.

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

Their thinking

  • We define an array if the length of the array is the same as the required queue lengthisFull
  • If the length of the array is zero0, then meetisEmpty
  • insertLastIt’s just inserting into the first item in the array
  • insertLastIt’s just going into an arraypushThe element
  • deleteFrontIt’s just removing the first element of the array
  • deleteLastIt’s essentially removing the last element of the array
  • getRearGet the last item, which is the first item in the arraylength-1item
  • getFrontGet array number0item

Tip:

  • All values are in the range of[1, 1000]
  • The number of operations ranges from[1, 1000]
  • Do not use the built-in double-endian queue library.

The problem solving code

/ * * *@param {number} k* /
var MyCircularDeque = function(k) {
    this.maxLen = k 
    this.arr = []
};

/ * * *@param {number} value
 * @return {boolean}* /
MyCircularDeque.prototype.insertFront = function(value) {
    if(this.isFull()) return false
    this.arr = [value,...this.arr]
    return true
};

/ * * *@param {number} value
 * @return {boolean}* /
MyCircularDeque.prototype.insertLast = function(value) {
    if(this.isFull()) return false
    this.arr.push(value)
    return true
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.deleteFront = function() {
 if(this.isEmpty()) return false
    let [a,...args] = this.arr
    this.arr = [...args]
    return true
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.deleteLast = function() {
    if(this.isEmpty()) return false
    this.arr = this.arr.slice(0.this.arr.length-1)
    return true
};

/ * * *@return {number}* /
MyCircularDeque.prototype.getFront = function() {
    if(this.isEmpty()) return -1
    return this.arr[0]};/ * * *@return {number}* /
MyCircularDeque.prototype.getRear = function() {
    if(!this.arr.length) return -1
    return this.arr[this.arr.length-1]};/ * * *@return {boolean}* /
MyCircularDeque.prototype.isEmpty = function() {
    return this.arr.length == 0
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.isFull = function() {
    return this.arr.length == this.maxLen
};

/** * 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 have any questions or suggestions, please leave a comment!