Problem statement

https://leetcode.com/problems/design-front-middle-back-queue/

Solution

Problem constraints allow us just to do bruteforce. However there is better solution. Let us keep two deques: A and B and funciton balance, which make sure, that if we have 2n elements, we have n, n in them and if we have 2n + 1 elements, that we have n + 1, n in them.

Complexity

It is O(1) for all operations.

Code

class FrontMiddleBackQueue:
    def __init__(self):
        self.A, self.B = deque(), deque()
        
    def balance(self):
        if len(self.A) > len(self.B) + 1:
            self.B.appendleft(self.A.pop())
        if len(self.A) < len(self.B):
            self.A.append(self.B.popleft())

    def pushFront(self, val):
        self.A.appendleft(val)
        self.balance()

    def pushMiddle(self, val):
        if len(self.A) > len(self.B):
            self.B.appendleft(self.A.pop())
        self.A.append(val)

    def pushBack(self, val):
        self.B.append(val)
        self.balance()

    def popFront(self):
        val = self.A.popleft() if self.A else -1
        self.balance()
        return val

    def popMiddle(self):
        val = (self.A or [-1]).pop()
        self.balance()
        return val

    def popBack(self):
        val = (self.B or self.A or [-1]).pop()
        self.balance()
        return val