[Java] Using two Deque O(1) for each operation
\nclass FrontMiddleBackQueue {\n    Deque<Integer> left;\n    Deque<Integer> right;\n    \n    public FrontMiddleBackQueue() {\n        left = new ArrayDeque<>(
```\nclass FrontMiddleBackQueue {\n    Deque<Integer> left;\n    Deque<Integer> right;\n    \n    public FrontMiddleBackQueue() {\n        left = new ArrayDeque<>();\n        right = new ArrayDeque<>();\n    }\n    \n    public void pushFront(int val) {\n        left.offerFirst(val);\n        rebalance();\n    }\n    \n    public void pushMiddle(int val) {\n        left.offerLast(val);\n        rebalance();\n    }\n    \n    public void pushBack(int val) {\n        right.offerLast(val);\n        rebalance();\n    }\n    \n    public int popFront() {\n        int res = -1;\n        if(!left.isEmpty()){\n            res = left.pollFirst();\n        }\n        else if(!right.isEmpty()){\n            res = right.pollFirst();\n        }\n        rebalance();\n        return res;\n    }\n    \n    public int popMiddle() {\n        int res = -1;\n        boolean isRight = (left.size()+right.size())%2==1;\n        if(isRight && !right.isEmpty()){\n            res = right.pollFirst();\n        }\n        else if(!left.isEmpty()){\n            res = left.pollLast();\n        }\n        rebalance();\n        return res;\n    }\n    \n    public int popBack() {\n        int res = -1;\n        if(!right.isEmpty()){\n            res = right.pollLast();\n        }\n        else if(!left.isEmpty()){\n            res = left.pollLast();\n        }\n        rebalance();\n        return res;\n    }\n    \n    private void rebalance(){\n        while(left.size()<right.size()-1){\n            left.offerLast(right.pollFirst());\n        }\n        while(left.size()>right.size()){\n            right.offerFirst(left.pollLast());\n        }\n    }\n}\n```
[]