Javascript two Deque Solution | 96%
Straightforward solution using two deques.  \n\nThe idea is to balance the two deques around where the middle element will always be.\nThis solution ensures tha
Straightforward solution using two deques.  \n\nThe idea is to balance the two deques around where the middle element will always be.\nThis solution ensures that the **middle** element is always at the top of the front deque.\nThe best way to come up with an answer is to write out the rules you need to follow when balancing\nin each of the functions.\n\nSolution is **O(n)** due to the nature of Javascript\'s implementation of arrays.   The functions **shift()** and **unshift()** are the cuplrits.  \nWhen calling an unshift(), to avoid placing the element at the start of the array and having to go over all elements to reassign as such: \n\n**N -> N + 1, N1 -> N + 2, N2 -> N + 3** etc.  \n\nJavascript instead will build a new array with the new beginning element and copy the old into the new.  This would\'ve been an issue if the problem asked us to do alot more than the 1000 calls.  If that was the case, a custom deque implementation using a Doubly Linked List would allow for **O(1)**. \n\n```\nvar FrontMiddleBackQueue = function() {\n    this.frontDeque = [];\n    this.backDeque = [];\n};\n\nFrontMiddleBackQueue.prototype.pushFront = function(val) {\n    if(this.frontDeque.length > this.backDeque.length)\n        this.backDeque.unshift(this.frontDeque.pop());\n    \n    this.frontDeque.unshift(val);\n};\n\nFrontMiddleBackQueue.prototype.pushMiddle = function(val) {\n    if(this.frontDeque.length !== this.backDeque.length)\n        this.backDeque.unshift(this.frontDeque.pop());\n    \n    this.frontDeque.push(val);\n};\n\nFrontMiddleBackQueue.prototype.pushBack = function(val) {\n    this.backDeque.push(val);\n    \n    if(this.backDeque.length > this.frontDeque.length)\n        this.frontDeque.push(this.backDeque.shift());\n};\n\nFrontMiddleBackQueue.prototype.popFront = function() {\n    if(this.frontDeque.length == 0 && this.backDeque.length == 0) return -1;\n    \n    let res = this.frontDeque.shift();\n    \n    if(this.backDeque.length > this.frontDeque.length)\n        this.frontDeque.push(this.backDeque.shift());\n    \n    return res;\n};\n\nFrontMiddleBackQueue.prototype.popMiddle = function() {\n    if(this.frontDeque.length == 0 && this.backDeque.length == 0) return -1;\n    \n    let res = this.frontDeque.pop();\n    \n    if(this.frontDeque.length < this.backDeque.length)\n        this.frontDeque.push(this.backDeque.shift());\n    \n    return res;\n};\n\nFrontMiddleBackQueue.prototype.popBack = function() {\n    if(this.frontDeque.length == 0 && this.backDeque.length == 0) return -1;\n    \n    let res;\n    \n    if(this.backDeque.length == 0)\n        res = this.frontDeque.pop();\n    else\n        res = this.backDeque.pop();\n\n    if(this.frontDeque.length - this.backDeque.length == 2)\n        this.backDeque.unshift(this.frontDeque.pop());\n\n    \n    return res;    \n};\n\n/*\n\tPUSH FRONT\n    If the front deque is larger than the back deque before adding new element.  \n\tThen move the top of the front deque into the back deque\n    \n    Front   Back\n    [1,2]   [3]\n    [1]     [2,3] *POP BACK DEQUE BEFORE ADDING\n    [4,1]   [2,3]\n    \n    --------------------\n    \n    Front   Back\n    [1,2]   [3,4]\n    [5,1,2] [3,4]\n*/\n\n/*\n    PUSH MIDDLE\n    If front is larger, shift the current middle element into the back deque before adding new element.\n\tThis ensures the middle element stays in the front deque\n     \n    Front       Back\n    [1, 2, (3)] [4, 5]      ***POP CURRENT MIDDLE ELEMENT\n    [1, 2, (6)] [3, 4, 5]\n    \n    --------------------\n    \n    Otherwise simply push the new middle element to the top of the front deque\n    \n    Front       Back\n    [1,2]       [3,4]\n    [1,2,(5)]   [3, 4]\n*/\n\n/*\n\tPUSH BACK\n    When back becomes larger, move it\'s first element to the top of front deque \n\tafter adding the element\n    \n    Front   Back\n    [1,2]   [3,4]\n    [1,2]   [3,4,5] **SHIFT\n    [1,2,3] [4,5]\n    \n    -----------------\n    \n    Otherwise simply add to back\n    \n    Front   Back\n    [1,2,3] [4,5]\n    [1,2,3] [4,5,6]\n    \n*/\n\n/*\n    POP FRONT\n    Remove from front deque.  When it becomes smaller than back, shift the first element of back deque\n    into the top of front deque after removing element\n    \n    Front   Back\n    [1,2,3] [4,5,6]\n    [2,3]   [4,5,6] ***SHIFT\n    [2,3,4] [5,6]\n    \n    ------------\n    \n    Otherwise remove from front\n    \n    Front   Back\n    [1,2,3] [4,5]\n    [2,3]   [4,5]\n*/\n\n/*\n    POP MIDDLE\n    Again if front deque becomes smaller than back, shift element out of back deque.\n    Remember, top of front deque is always middle element\n    \n    Front   Back\n    [1,2,3] [4,5,6]\n    [1,2]   [4,5,6]  ***SHIFT\n    [1,2,4] [5,6]\n    \n    --------------\n    \n    Otherwise simply remove top of the front deque\n    \n    Front   Back\n    [1,2,3] [4,5]\n    [1,2]   [4,5]\n*/\n\n/*\n    POP BACK\n    Take from front when back is empty.  Otherwise take from back, rebalance when\n    front is greater than back by 2.  This preserves middle element\n    \n    Front Back\n    [1]   []\n    []    []\n    \n    ---------\n    Otherwise\n    \n    Front   Back\n    [1,2,3] [4,5]\n    [1,2,3] [4]   ***Rebalance\n    [1,2]   [3,4]\n    [1,2]   [3]\n    [1,2]   []    ***Rebalance\n    [1]     [2]\n    \n*/\n```\n
['Queue', 'JavaScript']