Java Deque: front queue and back queue.
Makes sure 0<= back queue size - front queue size <=1.\nRebalance the queues after operation.\n\nclass FrontMiddleBackQueue {\n    Deque<Integer> front;\n    De
Makes sure 0<= back queue size - front queue size <=1.\nRebalance the queues after operation.\n```\nclass FrontMiddleBackQueue {\n    Deque<Integer> front;\n    Deque<Integer> back;\n    \n    public FrontMiddleBackQueue() {\n        front=new LinkedList<>();\n        back=new LinkedList<>();\n    }\n    \n    public void pushFront(int val) {\n        front.addFirst(val);\n        if(front.size()>back.size()) {\n            back.addFirst(front.pollLast());\n        }\n    }\n    \n    public void pushMiddle(int val) {\n        if(front.size()<back.size()) {\n            front.addLast(val);\n        } else {\n            back.addFirst(val);\n        }\n    }\n    \n    public void pushBack(int val) {\n        back.addLast(val);\n        if(back.size()-front.size()>1) {\n            front.addLast(back.pollFirst());\n        }\n    }\n    \n    public int popFront() {\n        if(front.isEmpty()) {\n            return back.isEmpty()?-1:back.pollFirst();\n        } else {\n            var val=front.pollFirst();\n            if(back.size()-front.size()>1) {\n                front.addLast(back.pollFirst());\n            }\n            return val;\n        }\n    }\n    \n    public int popMiddle() {\n        if(front.size()<back.size()) return back.pollFirst();\n        return front.isEmpty()?-1:front.pollLast();\n    }\n    \n    public int popBack() {\n        if(back.isEmpty()) {\n            return -1;\n        } else {\n            var val=back.pollLast();\n            if(front.size()>back.size()) {\n                back.addFirst(front.pollLast());\n            }\n            return val;\n        }\n    }\n}\n```
[]