C++ using 2 deques, all operations O(1), beats 100%
Approach\n Describe your approach to solving the problem. \nDivide the elements of the queue into front and back halves, fq and bq, whose size differs at most b
# Approach\n<!-- Describe your approach to solving the problem. -->\nDivide the elements of the queue into front and back halves, `fq` and `bq`, whose size differs at most by one element. The following invariants shall hold true:\n1. `fq.size() == bq.size()` iff there are an even number of elements\n2. `fq.size() == bq.size() + 1` iff there are an odd number of elements\n3. The middle element is always at `fq.back()`\n4. The front element is always at `fq.front()`\n5. The rear element is at `bq.back()` *unless* there is only 1 element, in which case it is at `fq.back()` (`== fq.front()` in this case)\n\nThe invariants are enforced in the `rebalance()` function, called after each push or pop from either end. Each call to `rebalance()` involves at most 2 operations: A single `pop` from one queue and a single `push` to the other.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nAll write operations (`push_*` ) involve at most 2 pushes and 1 pop, all read operations (`pop_*`) involve at most 2 pops and 1 push. Time complexity for all operations is thus $$O(1)$$.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ for the elements of the queue.\n\n# Code\n```cpp []\nclass FrontMiddleBackQueue {\n    // Invariants:\n    // 1. If number of elements is even, fq.size() == bq.size()\n    // 2. If number of elements is odd, fq.size() == bq.size() + 1\n    // 3. Middle element is always at the back of fq\n    // 4. First element is at front of fq\n    // 5. Last element is at back of bq, unless there is only 1 element then it is in fq\n    deque<int> fq; // front-half\n    deque<int> bq; // back-half\n\n    void rebalance()\n    {\n        if (bq.size() > fq.size()) {\n            fq.push_back(bq.front());\n            bq.pop_front();\n        } else if (fq.size() > bq.size() + 1) {\n            bq.push_front(fq.back());\n            fq.pop_back();\n        }\n    }\n\npublic:    \n    void pushFront(int val) {\n        fq.push_front(val);\n        rebalance();\n    }\n    \n    void pushMiddle(int val) {\n        if (fq.size() == bq.size()) { // total size is even\n            fq.push_back(val);\n        } else { // total size is odd\n            bq.push_front(fq.back());\n            fq.pop_back();\n            fq.push_back(val);\n        }\n    }\n    \n    void pushBack(int val) {\n        bq.push_back(val);\n        rebalance();\n    }\n    \n    int popFront() {\n        if (empty()) return -1;\n        int val = fq.front();\n        fq.pop_front();\n        rebalance();\n        return val;\n    }\n    \n    int popMiddle() {\n        if (empty()) return -1;\n        int val = fq.back();\n        fq.pop_back();\n        rebalance();\n        return val;\n    }\n    \n    int popBack() {\n        if (empty()) return -1;\n        auto& q = !bq.empty() ? bq : fq;\n        int val = q.back();\n        q.pop_back();\n        rebalance();\n        return val;\n    }\n\n    bool empty()\n    {\n      return fq.empty();\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```
['C++']