C++ using doubly linked list O(1) approach, no cheats
\nstruct Node {\n    int data;\n    Node* next;\n    Node* prev;\n};\n\n\nclass FrontMiddleBackQueue {\nprivate:\n    Node* head;\n    Node* mid;\n    Node* tai
```\nstruct Node {\n    int data;\n    Node* next;\n    Node* prev;\n};\n\n\nclass FrontMiddleBackQueue {\nprivate:\n    Node* head;\n    Node* mid;\n    Node* tail;\n    int size;\npublic:\n    FrontMiddleBackQueue() {\n        head = nullptr;\n        mid = nullptr;\n        tail = nullptr;\n        size = 0;\n    }\n    \n    Node* getNode(int val) {\n        Node* n = new Node();\n        n->data = val;\n        n->next = nullptr;\n        n->prev = nullptr;\n        return n;\n    }\n    \n    void pushFront(int val) {\n        Node* n = getNode(val);\n        \n        if(head == nullptr) {\n            head = n;\n            mid = n;\n            tail = n;\n            size++;\n            return;\n        }\n        \n        n->next = head;\n        head->prev = n;\n        head = n;\n        size++;\n        \n        if(size % 2 == 0) {\n            mid = mid->prev;\n        }\n        \n        return;\n    }\n    \n    void pushMiddle(int val) {\n        Node* n = getNode(val);\n\n        if(head == nullptr) {\n            head = n;\n            mid = n;\n            tail = n;\n            size++;\n            return;\n        }\n        \n        if(size % 2 != 0) {\n            Node* p = mid->prev;\n            if(p != nullptr)\n                p->next = n;\n            else\n                head = n;\n            n->prev = p;\n            n->next = mid;\n            mid->prev = n;\n            mid = n;\n            size++;\n        } else {\n            Node* p = mid->next;\n            mid->next = n;\n            n->prev = mid;\n            n->next = p;\n            p->prev = n;\n            mid = n;\n            size++;\n        }\n\n        return;\n    }\n    \n    void pushBack(int val) {\n        Node* n = getNode(val);\n        \n        if(head == nullptr) {\n            head = n;\n            mid = n;\n            tail = n;\n            size++;\n            return;\n        }\n        \n        n->prev = tail;\n        tail->next = n;\n        tail = n;\n        size++;\n        \n        if(size % 2 != 0) {\n            mid = mid->next;\n        }\n        \n        return;\n    }\n    \n    int popFront() {\n        if(head == nullptr) {\n            return -1;\n        }\n        \n        int val = head->data;\n        Node* p = head;\n        head = head->next;\n        size--;\n        \n        if(size == 0) {\n            tail = nullptr;\n            mid = nullptr;\n            head = nullptr;\n        } else if(size % 2 != 0) {\n            mid = mid->next;\n        }\n        \n        if(head != nullptr)\n            head->prev = nullptr;\n\n        delete p;\n        return val;\n        \n    }\n    \n    int popMiddle() {\n        if(head == nullptr) {\n            return -1;\n        }\n\n        size--;\n        Node* p = mid;\n        int val = p->data;\n        \n        if(size == 0) {\n            tail = nullptr;\n            mid = nullptr;\n            head = nullptr;\n        } else if(size % 2 == 0) {\n            mid->prev->next = p->next;\n            mid = p->prev;\n            if(p->next != nullptr) {\n                p->next->prev = mid;\n            }\n        } else {\n            mid = mid->next;\n            mid->prev = p->prev;\n            if(p->prev != nullptr) {\n                p->prev->next = mid;\n            } else {\n                head = mid;\n                tail = mid;\n            }\n        }\n\n        delete p;\n        return val;\n    }\n    \n    int popBack() {\n        if(head == nullptr) {\n            return -1;\n        }\n        \n        size--;\n        \n        Node* p = tail;\n        int val = p->data;\n        tail = tail->prev;\n        if(tail != nullptr)\n        tail->next = nullptr;\n\n        if(size == 0) {\n            tail = nullptr;\n            head = nullptr;\n            mid = nullptr;\n        } else if(size % 2 == 0) {\n            mid = mid->prev;\n        }\n        \n        delete p;\n        return val;\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 ```
[]