LeetCode Solutions Blog

Design Front Middle Back Queue

Difficulty: Medium

Problem Description

Design a queue that supports push and pop operations in the front, middle, and back. Implement the FrontMiddleBack class with methods to add and remove elements from these positions.

Key Insights

The queue needs to maintain order while allowing operations from three distinct positions: front, middle, and back.
When adding to the middle, if the size is even, the new element goes in the frontmost middle position.
Efficiently managing these operations requires careful consideration of the underlying data structure to avoid performance bottlenecks.

Space and Time Complexity

Time Complexity: O(n) for pushMiddle, O(1) for pushFront, pushBack, popFront, and popBack; O(n) for popMiddle. Space Complexity: O(n) for storing the elements in the queue.

Solution

To implement the FrontMiddleBack class, we can use two deques to efficiently manage the elements in the queue. One deque will represent the front and middle elements, while the second deque will represent the back elements. This allows us to push and pop elements from both ends efficiently and to maintain access to the middle element.

Use a deque for the front/middle section.
Use another deque for the back section.
Balance the two sections after each insertion and deletion to maintain the correct middle element.

Code Solutions

from collections import deque

class FrontMiddleBackQueue:
    def __init__(self):
        self.front = deque()  # Deque for the front/middle
        self.back = deque()   # Deque for the back

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

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

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

    def popFront(self) -> int:
        if not self.front and not self.back:
            return -1
        if self.front:
            return self.front.popleft()
        return -1

    def popMiddle(self) -> int:
        if not self.front and not self.back:
            return -1
        if len(self.front) > len(self.back):
            return self.front.pop()
        return self.back.popleft()

    def popBack(self) -> int:
        if not self.back and not self.front:
            return -1
        if self.back:
            return self.back.pop()
        return -1

    def balance(self):
        # Ensure the sizes of the two deques are balanced
        if len(self.front) > len(self.back) + 1:
            self.back.appendleft(self.front.pop())
        elif len(self.back) > len(self.front):
            self.front.append(self.back.popleft())