Problem statement

https://binarysearch.com/problems/Middle-Operable-Deque/

Solution

Equal to Leetcode 1670. Design Front Middle Back Queue.

Complexity

It is O(1) for all operations.

Code

class MiddleOperableDeque:
    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 appendLeft(self, val):
        self.A.appendleft(val)
        self.balance()

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

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

    def popLeft(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 pop(self):
        val = (self.B or self.A or [-1]).pop()
        self.balance()
        return val