1. Title Description

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 is empty) copy codeCopy the code

Tip:

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

Second, the analysis

We can break this down into several 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.ceil(Array.length / 2) - 1. This step minus one is the essence of the problem, think about this step this problem is solved.

Three, code 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