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

The title

Design the front, middle and back queues

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

Please complete the FrontMiddleBack class:

TMiddleBack () initializes the queue. Void pushFront(int val) adds val to the front of the queue. Void pushMiddle(int val) adds val to the middle of the queue. Void pushBack(int val) adds val to the end of the queue. V int popFront() removes the most recent element from the queue and returns the value, or -1 if the queue was empty before the deletion. Int popMiddle() removes the middle element from the queue and returns the value, or >-1 if the queue was empty before deletion. Int popBack() removes the last element from the queue and returns the value, or -1 if the queue was empty before deletion. Note that when there are two middle positions, select the front position for operation. For example:

Add to the middle of [1, 2, 3, 4, 5], resulting in an array of [1, 2, 6, 3, 4, 5].

Pop the element from the middle of [1, 2, 3, 4, 5, 6], return 3, and the array becomes [1, 2, 4, 5, 6].

Example 1:

Input: [“FrontMiddleBackQueue”, “pushFront”, “pushBack”, “pushMiddle”, “pushMiddle”, “popFront”, “popMiddle”, “popMiddle”, “popBack”, “popFront”]

[], [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)

 

Tip:

1 <= val <= 109 Calls up to 1000 times pushFront, pushMiddle, pushBack, popFront, popMiddle and popBack.

Analysis of the

  • Name two queues and add the middle value to the right queue

  • Add 6 to the front of the queue, unshift the left queue, and add element 6 to the front of the queue

  • The length of the left queue is longer than that of the right queue

  • Remove the last bit from left queue pop and the last bit from right queue unshift

  • Add 6 to the middle of the queue

  • The length of the left queue is equal to that of the queue, and the last pop of the left queue is deleted

  • Deleted unshift right queue

  • Push 6 to the left queue

  • Add 6 to the end of the queue

  • The middle number is in the right queue, and the left queue is smaller than the right queue

  • Otherwise, delete the first item in the right queue and add it to the end of the left queue

  • Delete the first one

  • Checks whether the left queue is empty. If it is empty, return -1, otherwise shift the left queue

  • If the left queue length is greater than the queue, pop the left queue and remove the unshift right queue

  • Delete intermediate elements

  • Check whether the left queue is empty, if empty returns -1, otherwise pop the left queue

  • Continue to judge the left queue length is smaller than the right queue, if not, pop the left queue, will delete the unshift right queue

  • Delete the last element

  • Check whether the right queue is empty. If empty, -1 is returned. Otherwise, pop the right queue

  • If the left queue length is greater than the right queue, pop the left queue and remove the unshift right queue

Code implementation

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

/ * * *@param {number} val
 * @return {void}* /
FrontMiddleBackQueue.prototype.pushFront = function(val) {
    this.leftArray.unshift(val)
    if(this.leftArray.length > this.rightArray.length)  this.rightArray.unshift(this.leftArray.pop())
};

/ * * *@param {number} val
 * @return {void}* /
FrontMiddleBackQueue.prototype.pushMiddle = function(val) {
    if(this.leftArray.length == this.rightArray.length) this.rightArray.unshift(val)
    else this.leftArray.push(val)
};

/ * * *@param {number} val
 * @return {void}* /
FrontMiddleBackQueue.prototype.pushBack = function(val) {
    this.rightArray.push(val)
    if(this.leftArray.length + 1 < this.rightArray.length) this.leftArray.push(this.rightArray.shift())
    
};

/ * * *@return {number}* /
FrontMiddleBackQueue.prototype.popFront = function() {
    if(!this.rightArray.length) return -1
    if(!this.leftArray.length) return this.rightArray.shift()
    let front = this.leftArray.shift()
    if(this.leftArray.length + 1 < this.rightArray.length) this.leftArray.push(this.rightArray.shift())
    return front
};

/ * * *@return {number}* /
FrontMiddleBackQueue.prototype.popMiddle = function() {
    if(!this.rightArray.length){
        return -1
    }
    if(this.leftArray.length == this.rightArray.length){
        return this.leftArray.pop()
    }
    return this.rightArray.shift()
};

/ * * *@return {number}* /
FrontMiddleBackQueue.prototype.popBack = function() {
    if(!this.rightArray.length) return -1
    let back = this.rightArray.pop()
    if(this.leftArray.length > this.rightArray.length) this.rightArray.unshift(this.leftArray.pop())
    return back
};
Copy the code