C++ Two deque, O(1)
\nclass FrontMiddleBackQueue {\npublic:\n    deque<int> F, B;\n    FrontMiddleBackQueue() {\n        \n    }\n    \n    void balance() {\n        if(F.size() > 
```\nclass FrontMiddleBackQueue {\npublic:\n    deque<int> F, B;\n    FrontMiddleBackQueue() {\n        \n    }\n    \n    void balance() {\n        if(F.size() > B.size()) {\n            B.push_front(F.back());\n            F.pop_back();\n        }\n        if(F.size() + 1 < B.size()) {\n            F.push_back(B.front());\n            B.pop_front();\n        }\n    }\n    void pushFront(int val) {\n        F.push_front(val);\n        balance();\n    }\n    \n    void pushMiddle(int val) {\n        F.push_back(val);\n        balance();\n    }\n    \n    void pushBack(int val) {\n        B.push_back(val);\n        balance();\n    }\n    \n    int popFront() {\n        if(F.size() == 0) {\n            if(B.size() == 0) return -1;\n            int ans = B.front(); B.pop_front();\n            return ans;\n        }\n        int ans = F.front(); F.pop_front();\n        balance();\n        return ans;\n    }\n    \n    int popMiddle() {\n        if(B.size() == 0 && F.size() == 0) return -1;\n        if(F.size() < B.size()) {\n            int ans = B.front(); B.pop_front();\n            return ans;\n        }\n        int ans = F.back(); F.pop_back();\n        balance();\n        return ans;\n    }\n    \n    int popBack() {\n        if(B.size() == 0 && F.size() == 0) return -1;\n        if(B.size() == 0) {\n            if(F.size() == 0) return -1;\n            int ans = F.back(); F.pop_back();\n            return ans;\n        }\n        int ans = B.back(); B.pop_back();\n        balance();\n        return ans;\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```
[]