“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Topic:

641. Design a circular double-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

 

Tip:

  • The range of all values is [1, 1000]
  • The range of operation times is [1, 1000]
  • Do not use the built-in double-endian queue library.

Train of thought

First of all, this question is very similar to the title of my last article. I suggest that you read the last article and then read this one and make a series. # [Luffy]_ Brush leetCode 622 together. Design loop queue

  1. For this problem, we only need to add a method of queue head insertion and queue tail deletion on the basis of the original ordinary circular queue.
  2. There are eight ways to solve this problem, so let’s break it down;
  3. isertThe head and the tail of the queue, we can useArray.unshiftandArray.pushTo implement, but need to determine whether the queue is full before inserting;
  4. deleteThe head and the tail of the queue, we can useArray.shiftandArray.popTo implement, but before deleting need to determine whether the queue is empty;
  5. Return the first element and the last element by the index of the array, but need to check whether the array is empty;
  6. We can check whether the queue is full or empty by looking at the length of the array.

implementation

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

/ * * *@param {number} value
 * @return {boolean}* /
MyCircularDeque.prototype.insertFront = function(value) {
    if (this.list.length < this.maxCount) {
        this.list.unshift(value);
        return true;
    }

    return false;
};

/ * * *@param {number} value
 * @return {boolean}* /
MyCircularDeque.prototype.insertLast = function(value) {
    if (this.list.length < this.maxCount) {
        this.list.push(value);
        return true;
    }

    return false;
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.deleteFront = function() {
    if (this.list.length > 0) {
        this.list.shift();
        return true;
    }

    return false;
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.deleteLast = function() {
    if (this.list.length > 0) {
        this.list.pop();
        return true;
    }

    return false;
};

/ * * *@return {number}* /
MyCircularDeque.prototype.getFront = function() {
    return this.list.length ? this.list[0] : -1;
};

/ * * *@return {number}* /
MyCircularDeque.prototype.getRear = function() {
    return this.list.length ? this.list[this.list.length - 1] : -1;
};

/ * * *@return {boolean}* /
MyCircularDeque.prototype.isEmpty = function() {
     return this.list.length === 0;
};

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

/** * 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 understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.