Design a queue that supports push and pop operations in the front, middle, and back.

Implement the FrontMiddleBack class:


	FrontMiddleBack() Initializes the queue.
	void pushFront(int val) Adds val to the front of the queue.
	void pushMiddle(int val) Adds val to the middle of the queue.
	void pushBack(int val) Adds val to the back of the queue.
	int popFront() Removes the front element of the queue and returns it. If the queue is empty, return -1.
	int popMiddle() Removes the middle element of the queue and returns it. If the queue is empty, return -1.
	int popBack() Removes the back element of the queue and returns it. If the queue is empty, return -1.


Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example:


	Pushing 6 into the middle of [1, 2, 3, 4, 5] results in [1, 2, 6, 3, 4, 5].
	Popping the middle from [1, 2, 3, 4, 5, 6] returns 3 and results in [1, 2, 4, 5, 6].


&nbsp;
Example 1:

Input:
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
Output:
[null, null, null, null, null, 1, 3, 4, 2, -1]

Explanation:
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // return 1 -&gt; [4, 3, 2]
q.popMiddle();    // return 3 -&gt; [4, 2]
q.popMiddle();    // return 4 -&gt; [2]
q.popBack();      // return 2 -&gt; []
q.popFront();     // return -1 -&gt; [] (The queue is empty)


&nbsp;
Constraints:


	1 &lt;= val &lt;= 109
	At most&nbsp;1000&nbsp;calls will be made to&nbsp;pushFront,&nbsp;pushMiddle,&nbsp;pushBack, popFront, popMiddle, and popBack.


class FrontMiddleBackQueue:

    def __init__(self):
        self.front = deque()
        self.back = deque()

    def _correct_size(self):
        while len(self.back) > len(self.front):
            self.front.append(self.back.popleft())

        while len(self.front) > len(self.back) + 1:
            self.back.appendleft(self.front.pop())

    def pushFront(self, val: int) -> None:
        self.front.appendleft(val)
        self._correct_size()

    def pushMiddle(self, val: int) -> None:
        if len(self.front) > len(self.back):
            self.back.appendleft(self.front.pop())
        self.front.append(val)
        self._correct_size()

    def pushBack(self, val: int) -> None:
        self.back.append(val)
        self._correct_size()

    def popFront(self) -> int:
        front = self.front if self.front else self.back
        ret = front.popleft() if front else -1
        self._correct_size()
        return ret

    def popMiddle(self) -> int:
        ret = self.front.pop() if self.front else -1
        self._correct_size()
        return ret

    def popBack(self) -> int:
        back = self.back if self.back else self.front
        ret = back.pop() if back else -1
        self._correct_size()
        return ret
class FrontMiddleBackQueue {

    Deque<Integer> dq1, dq2;
    public FrontMiddleBackQueue() {        
        dq1 = new ArrayDeque<Integer>();
        dq2 = new ArrayDeque<Integer>();
    }
    
    public void pushFront(int val) {
        dq1.addFirst(val);
    }    
    
    public void pushBack(int val) {
        dq2.addLast(val);
    }   
    
    public void pushMiddle(int val) {
        while(dq1.size() + 1 < dq2.size())
            dq1.addLast(dq2.removeFirst());       
        while(dq1.size() > dq2.size())
            dq2.addFirst(dq1.removeLast());        
        dq1.addLast(val);        
    }     
    
    public int popFront() {
        if(!dq1.isEmpty())
            return dq1.removeFirst();
        if(!dq2.isEmpty())
            return dq2.removeFirst();
        return -1;    
    }  
    
    public int popMiddle() {
        if(dq1.isEmpty() && dq2.isEmpty())
            return -1;        
        while(dq1.size() < dq2.size())
            dq1.addLast(dq2.removeFirst());     
        while(dq1.size() > dq2.size() + 1)
            dq2.addFirst(dq1.removeLast());
        return !dq1.isEmpty() ? dq1.removeLast() : dq2.removeFirst();
    }    
    
    public int popBack() {
        if(!dq2.isEmpty())
            return dq2.removeLast();
        if(!dq1.isEmpty())
            return dq1.removeLast();
        return -1;            
    }    
}
class FrontMiddleBackQueue {
public:
    deque<int> list1;
    deque<int> list2;
    int size;
    
    FrontMiddleBackQueue() {
        size = 0;        
    }
    
    void pushFront(int val) {
        
        if(list1.size()- list2.size() == 0)
        {
            list1.push_front(val);
        }
        else
        {
            list1.push_front(val);
            list2.push_front(list1.back());
            list1.pop_back();
        }
        
        size++;
    }
    
    void pushMiddle(int val) {
        
        if(list1.size() - list2.size() == 0)
        {
            list1.push_back(val);
        }
        else
        {
            list2.push_front(list1.back());
            list1.pop_back();
            list1.push_back(val);
        }
        
        size++;
    }
    
    void pushBack(int val) {
            
        if(list1.size() - list2.size() == 0)
        {
            list2.push_back(val);
            list1.push_back(list2.front());
            list2.pop_front();
        }
        else
        {
            list2.push_back(val);
        }
        
        size++;
    }
    
    int popFront() {

        if(size ==0) return -1;
        
        int val = list1.front();
        list1.pop_front();
        
        if(list1.size()<list2.size())
        {
            list1.push_back(list2.front());
            list2.pop_front();
        }
        
        size--;
        return val;
    }
    
    int popMiddle() {
        
        if(size ==0) return -1;
        
        int val = list1.back();
        list1.pop_back();

        if(list1.size() < list2.size())
        {
            list1.push_back(list2.front());
            list2.pop_front();
        }
        
        size--;
        return val;
        
    }
    
    int popBack() {
        
        if(size ==0) return -1;
        
        int val;
        if(size==1)
        {
            val = list1.front();
            list1.pop_front();
        }
        else
        {
            val = list2.back();
            list2.pop_back();

            int s1 = list1.size();
            int s2 = list2.size();

            if(list1.size() - list2.size() > 1)
            {
                list2.push_front(list1.back());
                list1.pop_back();
            }                   
        }
        
        size--;
        return val;       
    }
};
// T.C: 
// O(1) for init and methods other than pushMiddle(), popMiddle()
// O(N) for pushMiddle(), popMiddle()
// S.C: O(N) for storage 

// Doubly linked list node
function ListNode(val, prev, next) {
    this.val = val || 0;
    this.prev = prev || null;
    this.next = next || null;
}

var FrontMiddleBackQueue = function() {
    this.head = null;
    this.tail = null;
    this.len = 0;
};

/** 
 * @param {number} val
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushFront = function(val) {
    if (this.len === 0) {
        this.head = new ListNode(val);
        this.tail = this.head;
        this.len += 1;
        return;
    }
    
    let newNode = new ListNode(val);
    newNode.next = this.head;
    this.head.prev = newNode;
    this.head = newNode; // the new node becomes the new head
    this.len += 1;
};

/** 
 * @param {number} val
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushMiddle = function(val) {
    if (this.len <= 1) {
        this.pushFront(val);
        return;
    }
    let cur = this.head;
    for (let i = 1; i < Math.floor(this.len / 2); i++) { // we go to previous node of median
        cur = cur.next;    
    }
    let newNode = new ListNode(val);
    let next = cur.next;
    cur.next = newNode;
    newNode.prev = cur;
    newNode.next = next;
    if (next) next.prev = newNode;
    this.len += 1;
};

/** 
 * @param {number} val
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushBack = function(val) {
    if (this.len === 0) {
        this.pushFront(val);
        return;
    }
    
    let newNode = new ListNode(val);
    this.tail.next = newNode;
    newNode.prev = this.tail;
    this.tail = newNode; // end node becomes the new tail
    this.len += 1;
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popFront = function() {
    if (this.len === 0) {
        return -1;
    }
    let front = this.head;
    let next = front.next;
    if (next) next.prev = null;
    this.head = next;
    this.len -= 1;
    return front.val;
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popMiddle = function() {
    if (this.len <= 2) {
        return this.popFront();
    }
    let cur = this.head;
    for (let i = 1; i < Math.ceil(this.len / 2); i++) { // we go to median node
        cur = cur.next;    
    }

    let prev = cur.prev;
    let next = cur.next;
    cur.prev = null;
    cur.next = null;
    if (prev) prev.next = next;    
    if (next) next.prev = prev;
    this.len -= 1;
    return cur.val;
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popBack = function() {
    if (this.len <= 1) {
        return this.popFront();
    }
    let end = this.tail;
    let prev = end.prev;
    end.prev = null;
    prev.next = null;
    this.tail = prev;
    this.len -= 1;
    return end.val;
};

/** 
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * var obj = new FrontMiddleBackQueue()
 * obj.pushFront(val)
 * obj.pushMiddle(val)
 * obj.pushBack(val)
 * var param_4 = obj.popFront()
 * var param_5 = obj.popMiddle()
 * var param_6 = obj.popBack()
 */
Design Front Middle Back Queue