C++ All O(1) | Deque
Straight-forward idea:\n Take two double ended queues (deque)\n Keep them balanced always, such that:\n\t* size_of_left_deque <= size_of_right_deque\n\nEach ope
Straight-forward idea:\n* Take two double ended queues (deque)\n* Keep them balanced always, such that:\n\t* size_of_left_deque <= size_of_right_deque\n\nEach operation: O(1) time!\n\n```c++\nclass FrontMiddleBackQueue {\npublic:\n    deque<int>leftD, rightD;\n    FrontMiddleBackQueue() {\n        leftD.clear();\n        rightD.clear();\n    }\n    \n    void shiftLeft()\n    {\n        int item = rightD.front();\n        rightD.pop_front();\n        leftD.push_back(item);\n    }\n    \n    void shiftRight()\n    {\n        int item = leftD.back();\n        leftD.pop_back();\n        rightD.push_front(item);\n    }\n\n    void balance()\n    {\n        if(leftD.size() > rightD.size())\n            shiftRight();\n        if(leftD.size() + 1 < rightD.size())\n            shiftLeft();\n    }\n    \n    void pushFront(int val)\n    {\n        leftD.push_front(val);\n        balance();\n    }\n    \n    void pushMiddle(int val)\n    {\n        leftD.push_back(val);\n        balance();\n    }\n    \n    void pushBack(int val)\n    {\n        rightD.push_back(val);\n        balance();\n    }\n    \n    int popFront()\n    {\n        if(leftD.empty() && rightD.empty()) return -1;\n        if(leftD.empty())\n        {\n            int item = rightD.front();\n            rightD.pop_front();\n            balance();\n            return item;\n        }\n        int item = leftD.front();\n        leftD.pop_front();\n        balance();\n        return item;\n    }\n    \n    int popMiddle()\n    {\n        if(rightD.empty()) return -1;\n        if(leftD.size() < rightD.size())\n        {\n            int item = rightD.front();\n            rightD.pop_front();\n            balance();\n            return item;\n        }\n        int item = leftD.back();\n        leftD.pop_back();\n        balance();\n        return item;\n    }\n    \n    int popBack()\n    {\n        if(rightD.empty()) return -1;\n        int item = rightD.back();\n        rightD.pop_back();\n        balance();\n        return item;\n    }\n};\n\n/**\n * Your FrontMiddleBackQueue object will be instantiated and called as such:\n * FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();\n * obj->pushFront(val);\n * obj->pushMiddle(val);\n * obj->pushBack(val);\n * int param_4 = obj->popFront();\n * int param_5 = obj->popMiddle();\n * int param_6 = obj->popBack();\n */\n```
[]