C++ implementation using doubly linked list
This solutin can be done with doubly linked list, Time complexity : O(1) except middle functions.\n\n\nstruct Node {\n    int val;\n    Node *prev, *next;\n    
This solutin can be done with **doubly linked list**, Time complexity : O(1) except middle functions.\n\n```\nstruct Node {\n    int val;\n    Node *prev, *next;\n    Node() {\n        val = 0, prev = next = NULL;\n    }\n    \n    Node(int x) {\n        val = x, prev = next = NULL;\n    }\n    \n    Node(int x, Node *p, Node *n) {\n        val = x, prev = p, next = n;\n    }\n};\n\nclass FrontMiddleBackQueue {\n    Node *head;\n    int size;\npublic:\n    FrontMiddleBackQueue() {\n        head = NULL;\n        size = 0;\n    }\n    \n    void pushFront(int val) {\n        head = new Node(val, NULL, head);\n        if(head->next) {\n            head->next->prev = head;\n        }\n        size++;\n    }\n    \n    void pushMiddle(int val) {\n        if(size == 0) {\n            head = new Node(val);\n            size++;\n            return;\n        }\n        \n        if(size == 1) {\n            pushFront(val);\n            return;\n        }\n        \n        Node *ptr = NULL;\n        int n = size/2;\n        while(n--) {\n            if(ptr == NULL)\n                ptr = head;\n            else\n                ptr = ptr->next;\n        }\n        \n        // Even or Odd push to next of ptr\n        Node *next = ptr->next;\n        ptr->next = new Node(val, ptr, next);\n        if(next)\n            next->prev = ptr->next;\n        size++;\n    }\n    \n    void pushBack(int val) {\n        Node *ptr = head;\n        if(ptr == NULL)\n            head = new Node(val);\n        else {\n            while(ptr->next) {\n                ptr = ptr->next;\n            }\n            ptr->next = new Node(val, ptr, NULL);\n        }\n        size++;\n    }\n    \n    int popFront() {\n        if(size == 0)\n            return -1;\n        int val = head->val;\n        head = head->next;\n        if(head)\n            head->prev = NULL;\n        size--;\n        return val;\n    }\n    \n    int popMiddle() {\n        if(size == 0)\n            return -1;\n        \n        if(size == 1) {\n            int val = head->val;\n            head = NULL;\n            size--;\n            return val;\n        }\n        \n        int n = size/2;\n        Node *ptr = NULL;\n        while(n--) {\n            if(ptr == NULL)\n                ptr = head;\n            else\n                ptr = ptr->next;\n        }\n        \n        int val = -1;\n        Node *temp = NULL;\n        \n        if(size & 1) { // Odd size delete ptr->next\n            val = ptr->next->val;\n            temp = ptr->next->next;\n            ptr->next = temp;\n            if(temp)\n                temp->prev = ptr;\n        } else { // Even size delete ptr\n            if(ptr == head) {\n                val = popFront();\n                size++; // since decreased by popFront\n            }\n            else {\n                val = ptr->val;\n                ptr->prev->next = ptr->next;\n                ptr->next->prev = ptr->prev;\n            }\n        }\n        size--;\n        return val;\n    }\n    \n    int popBack() {\n        if(size == 0)\n            return -1;\n        if(size == 1) {\n            int val = head->val;\n            head = NULL;\n            size = 0;\n            return val;\n        }\n        \n        Node *ptr = head;\n        while(ptr->next) {\n            ptr = ptr->next;\n        }\n        \n        if(ptr->prev)\n            ptr->prev->next = NULL;\n        size--;\n        return ptr->val;\n    }\n};\n```\n\nThis approach is obviously complex, But for practicing the linked list it good. Vote up if it is helpfull \uD83D\uDE0A
['Linked List', 'Design', 'C', 'C++']