C++ solution || Using doubly linked list
Approach
The queue is implemented as a doubly linked list, where each node stores a value and pointers to the previous and next nodes.
pushFront adds a new node
# Approach
1. The queue is implemented as a doubly linked list, where each node stores a value and pointers to the previous and next nodes.
2. `pushFront` adds a new node at the head in `O(1)`.
3. `pushBack` adds a new node at the tail in `O(1)`
4. `pushMiddle` calculates the middle index, traverses to it, and inserts a new node in `O(n)`
5. `popFront` removes the head node in `O(1)`.
6. `popBack` removes the tail node in `O(1)`
7. `popMiddle` calculates the middle index, traverses to it, removes the node, and adjusts pointers in `O(n)`


# Code
```cpp []
struct dq
{
    int val;
    dq* next;
    dq* prev;

    dq()
    {
        next = nullptr;
        prev = nullptr;
    }

    dq(int n) : val(n),
                next(nullptr),
                prev(nullptr)
    {
    }
};

class FrontMiddleBackQueue
{
private:
    dq* _head;
    dq* _tail;
    int len;
    dq* createNode(int v)
    {
        dq* t = new dq(v);
        return t;
    }

    dq* getNodeAt(int index)
    {
        dq* t = _head;
        for (int i = 0; i < index; i++)
            t = t->next;
        return t;
    }

public:
    FrontMiddleBackQueue() : _head(nullptr),_tail(nullptr),len(0)
    {
    }
    
    void pushFront(int val)
    {
        dq* node = createNode(val);
        if(!_head)
        {
            _head = node;
            _tail = _head;
        }
        else
        {
            node->next = _head;
            _head->prev = node;
            _head = node;
        }
        len += 1;
    }
    
    void pushMiddle(int val)
    {
        if (len == 0)
        {
            pushFront(val);
            return;
        }

        int mid = len / 2;
        if (mid == 0)
        {
            pushFront(val);
            return;
        }

        dq* prevNode = getNodeAt(mid - 1);
        dq* node = createNode(val);
        node->next = prevNode->next;
        if (prevNode->next)
            prevNode->next->prev = node;
        prevNode->next = node;
        node->prev = prevNode;

        if (!node->next)
            _tail = node;

        len++;
    }
    
    void pushBack(int val)
    {
        dq* t = createNode(val);
        if( !_tail)
        {
            _tail = _head = t;
        }
        else
        {
            _tail->next = t;
            t->prev = _tail;
            _tail = t;
        }
        len += 1;
    }
    
    int popFront()
    {
        if (!_head)
            return -1;

        int val = _head->val;
        dq* temp = _head;
        _head = _head->next;
        if (_head)
            _head->prev = nullptr;
        else
            _tail = nullptr;

        delete temp;
        len--;
        return val;
    }
    
    int popMiddle()
    {
        if (!len)
            return -1;

        int mid = (len - 1) / 2;
        dq* nodeToDelete = getNodeAt(mid);
        int val = nodeToDelete->val;

        if (nodeToDelete->prev)
            nodeToDelete->prev->next = nodeToDelete->next;
        if (nodeToDelete->next)
            nodeToDelete->next->prev = nodeToDelete->prev;

        if (nodeToDelete == _head)
            _head = nodeToDelete->next;
        if (nodeToDelete == _tail)
            _tail = nodeToDelete->prev;

        delete nodeToDelete;
        len--;
        return val;
    }
    
    int popBack()
    {
        if (!_tail)
            return -1;

        int val = _tail->val;
        dq* temp = _tail;
        _tail = _tail->prev;
        if (_tail)
            _tail->next = nullptr;
        else
            _head = nullptr;

        delete temp;
        len--;
        return val;
    }
};

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();
 * obj->pushFront(val);
 * obj->pushMiddle(val);
 * obj->pushBack(val);
 * int param_4 = obj->popFront();
 * int param_5 = obj->popMiddle();
 * int param_6 = obj->popBack();
 */
```
['C++']