C++ 2 Deque Solution O(1) Operation
Runtime: 28 ms, faster than 93.45% of C++ online submissions for Design Front Middle Back Queue.\nMemory Usage: 20.5 MB, less than 41.85% of C++ online submissi
Runtime: 28 ms, faster than 93.45% of C++ online submissions for Design Front Middle Back Queue.\nMemory Usage: 20.5 MB, less than 41.85% of C++ online submissions for Design Front Middle Back Queue.\n\n\n**Maintain 2 dequeue List1 and List2 for storing data such as List1 has the first half and List2 has other half of the data and \nalways keep size of List1 and List2 as 0<=List1-List2<=1. Maintaining this rule always keep our middle data at the back of the List1.**\n\n**Push_front()=>** Push data in front of List1 and then check if 0<=List1-List2<=1; otherwise move data from back of List1 to the front of List2\n\n**Push_back()=>** Push data in back of List2 and then check if 0<=List1-List2<=1; otherwise move data from front of List2 to the back of List1\n\n```\nclass FrontMiddleBackQueue {\npublic:\n    deque<int> list1;\n    deque<int> list2;\n    int size;\n    \n    FrontMiddleBackQueue() {\n        size = 0;        \n    }\n    \n    void pushFront(int val) {\n        \n        if(list1.size()- list2.size() == 0)\n        {\n            list1.push_front(val);\n        }\n        else\n        {\n            list1.push_front(val);\n            list2.push_front(list1.back());\n            list1.pop_back();\n        }\n        \n        size++;\n    }\n    \n    void pushMiddle(int val) {\n        \n        if(list1.size() - list2.size() == 0)\n        {\n            list1.push_back(val);\n        }\n        else\n        {\n            list2.push_front(list1.back());\n            list1.pop_back();\n            list1.push_back(val);\n        }\n        \n        size++;\n    }\n    \n    void pushBack(int val) {\n            \n        if(list1.size() - list2.size() == 0)\n        {\n            list2.push_back(val);\n            list1.push_back(list2.front());\n            list2.pop_front();\n        }\n        else\n        {\n            list2.push_back(val);\n        }\n        \n        size++;\n    }\n    \n    int popFront() {\n\n        if(size ==0) return -1;\n        \n        int val = list1.front();\n        list1.pop_front();\n        \n        if(list1.size()<list2.size())\n        {\n            list1.push_back(list2.front());\n            list2.pop_front();\n        }\n        \n        size--;\n        return val;\n    }\n    \n    int popMiddle() {\n        \n        if(size ==0) return -1;\n        \n        int val = list1.back();\n        list1.pop_back();\n\n        if(list1.size() < list2.size())\n        {\n            list1.push_back(list2.front());\n            list2.pop_front();\n        }\n        \n        size--;\n        return val;\n        \n    }\n    \n    int popBack() {\n        \n        if(size ==0) return -1;\n        \n        int val;\n        if(size==1)\n        {\n            val = list1.front();\n            list1.pop_front();\n        }\n        else\n        {\n            val = list2.back();\n            list2.pop_back();\n\n            int s1 = list1.size();\n            int s2 = list2.size();\n\n            if(list1.size() - list2.size() > 1)\n            {\n                list2.push_front(list1.back());\n                list1.pop_back();\n            }                   \n        }\n        \n        size--;\n        return val;       \n    }\n};\n```
['Linked List', 'Queue', 'C']