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

Topic:

Design the front, middle and rear queues

Design a queue that supports push and POP operations in the front, middle, and back positions.

Please complete the FrontMiddleBack class:

  • FrontMiddleBack()Initialize the queue.
  • void pushFront(int val) 将 valAdded to the queueThe front of 。
  • void pushMiddle(int val) 将 valAdded to the queueRight in the middle 。
  • void pushBack(int val) 将 valAdded to the teamThe back 。
  • int popFront() 将 The front ofIs removed from the queue and returns the value, or if the queue was empty before deletion- 1 。
  • int popMiddle() 将 Right in the middleIs removed from the queue and returns the value, or if the queue was empty before deletion- 1 。
  • int popBack() 将 The backIs removed from the queue and returns the value, or if the queue was empty before deletion- 1 。

Note that when there are two middle positions, select the front position for operation. For example:

  • will6Added to the[1, 2, 3, 4, 5]The result array is[1, 2, 6, 3, 4, 5] 。
  • from[1, 2, 3, 4, 5, 6]Pops the element in the middle of the3, the array becomes[1, 2, 4, 5, 6] 。

 

Example 1:

Input:  ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "" popFront popBack", "] [[], [1], [2], [3], [4], [], [], [], [], []] output: [NULL, null, NULL, null, 1, 3, 4, 2, -1] FrontMiddleBackQueue q = new FrontMiddleBackQueue(); q.pushFront(1); // [1] q.pushBack(2); // [1, 2] q.pushMiddle(3); // [1, 3, 2] q.pushMiddle(4); // [1, 4, 3, 2] q.popFront(); // Return 1 -> [4, 3, 2] q.popmiddle (); // Return 3 -> [4, 2] q.popmiddle (); // Return 4 -> [2] q.popback (); // Return 2 -> [] q.popfront (); // Return -1 -> [] (queue empty)Copy the code

 

Tip:

  • 1 <= val <= 109
  • Most call1000 次 pushFront.pushMiddle.pushBack.popFront.popMiddle 和 popBack 。

Train of thought

This topic is the same series as my last article. I suggest that you read it from the front to the back, or you can read it directly. # [Luffy]_ Brush leetCode 641 together.

There’s a lot less bells and whistles in this one. There are 6 simple steps that we can break down into steps:

  1. Head of the line and back of the line, as usualArray.unshift 和 Array.pushImplementation, but now there is no maximum width limit can be inserted directly;
  2. The insertion in the queue, if you look at the conditions you can see that the position you want to insert is either exactly equal to the median, if there are two places in the middle choose the first one, then we can useMath.floor(Array.length / 2)To get the current position.[1, 2, 3]There are several places we can insert in, we can use variablesxTo represent vacancies, then there are four positions of vacancies, respectively:x, 1, x, 2, x, 3, xSo we’re going to insert position 2x, and since the index is calculated from 0, so bit 2xThat means the index is at position 1. while[1, 2, 3, 4]The vacancies in are:x, 1, x, 2, x, 3, x, 4, xAt this point, there are fivexThe position we inserted is the third position in the centerx, so the index formula of the middle position can be deducedmid = Math.floor(Array.length / 2).
  3. The head and tail of the team are deleted, as usualArray.shift 和 Array.popImplementation, in advance to determine whether the array is empty;
  4. Insert (); delete (); delete (); delete ();[1, 2, 3]There are only three elements that can be deleted, so let’s just take the middle one. The index is 1 and the array length is 3. And when the[1, 2, 3，4]When, there are four elements that can be deleted, and there are two numbers in the middle. We delete the first one, index 1, array length 4. Combining these two conditions we can deduce the index formula for the middle positionmid = Math.floor(Array.length / 2) - 1. This step minus one is the essence of the problem, think about this step this problem is solved.

implementation

var FrontMiddleBackQueue = function() {
    this.list = [];
};

/ * * *@param {number} val
 * @return {void}* /
FrontMiddleBackQueue.prototype.pushFront = function(val) {
    this.list.unshift(val);
};

/ * * *@param {number} val
 * @return {void}* /
FrontMiddleBackQueue.prototype.pushMiddle = function(val) {
    let mid = Math.floor(this.list.length / 2);
    this.list.splice(mid, 0, val);
};

/ * * *@param {number} val
 * @return {void}* /
FrontMiddleBackQueue.prototype.pushBack = function(val) {
    this.list.push(val);
};

/ * * *@return {number}* /
FrontMiddleBackQueue.prototype.popFront = function() {
    if (this.list.length) {
        return this.list.shift();
    } else {
        return -1; }};/ * * *@return {number}* /
FrontMiddleBackQueue.prototype.popMiddle = function() {
    if (this.list.length) {
        let mid = Math.ceil(this.list.length / 2) - 1;
        return this.list.splice(mid, 1);
    } else {
        return -1; }};/ * * *@return {number}* /
FrontMiddleBackQueue.prototype.popBack = function() {
    if (this.list.length) {
        return this.list.pop();
    } else {
        return -1; }};/** * Your FrontMiddleBackQueue object will be instantiated and called as such: * var obj = new FrontMiddleBackQueue() * obj.pushFront(val) * obj.pushMiddle(val) * obj.pushBack(val) * var param_4 = obj.popFront() * var param_5 = obj.popMiddle() * var param_6 = obj.popBack() */
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.