Easy to understand, using deque , in c++, int O(1), with well explanation
\n# Approach\n1. we are using two deque dq1 & dq2, dq1 hold element till mid element and dq2 hold elements form mid+1 to till last element.\n2. if in our data s
\n# Approach\n1. we are using two deque dq1 & dq2, dq1 hold element till mid element and dq2 hold elements form mid+1 to till last element.\n2. if in our data structure had odd size, then dq1 has 1 element more than dq2.\n3. we have to maintain mid element by both deques.\n\n\n# Code\n```\nclass FrontMiddleBackQueue {\npublic:\n    deque<int>dq1,dq2; // initialisation\n    FrontMiddleBackQueue() {\n        \n    }\n    \n    void pushFront(int val) \n    {\n        dq1.push_front(val);\n        balance(); // we have to try  equal elements in both deque\n    }\n    \n    void pushMiddle(int val) \n    {\n        if((dq1.size()+dq2.size())%2==0) // if both deque have equal size\n        {\n            dq1.push_back(val);\n        }\n        else  \n        {   // we deleting last element to dq1 and pushing deleting element to dq2.\n            // then push given value to back to dq1\n            int x = dq1.back();\n            dq1.pop_back();\n            dq1.push_back(val);\n            dq2.push_front(x);\n        }\n    }\n    \n    void pushBack(int val) \n    {\n        dq2.push_back(val);\n        balance(); // we have to try  equal elements in both deque\n    }\n    \n    int popFront() \n    {\n        if(dq1.empty()) // if data structure contain no elements\n        return -1;\n        int x = dq1.front(); \n        dq1.pop_front();\n        balance();\n        return x;\n    }\n    \n    int popMiddle() \n    {\n        if(dq1.empty())  // if data structure contain no elements\n        return -1;\n        int x = dq1.back();\n        dq1.pop_back();\n        balance();\n        return x;\n    }\n    \n    int popBack() \n    {\n        if(dq2.empty())  // if q2 is empty then dq1 can be empty or not\n        {\n            if(dq1.empty())\n            return -1;\n            else\n            {\n                int x = dq1.back();\n                dq1.pop_back();\n                return x;\n            }\n        }\n\n        int x = dq2.back();\n        dq2.pop_back();\n        balance();\n        return x;\n    }\n    void balance()\n    {\n        // if size(dq1) - size(dq2)==1 or ==0, we do nothing\n        if(dq1.size()==dq2.size() || dq1.size()-dq2.size()==1)\n            return;   \n        if(dq1.size()>dq2.size()) // if size(dq1) - size(dq2) > 1\n        {\n            int x = dq1.back();\n            dq1.pop_back();\n            dq2.push_front(x);\n        }\n        else\n        {    // if size(dq2) > size(dq1)\n            int x = dq2.front();\n            dq2.pop_front();\n            dq1.push_back(x);\n        }\n    }\n};\n\n```
['Queue', 'C++']