Design Front Middle Back Queue Solution in Python

Problem Description

Welcome to the world of queues, where the only thing more complicated than your love life is managing the order of elements! The problem at hand is to design a data structure that supports the following operations efficiently:

1. Push Front: Add an element to the front of the queue.
2. Push Middle: Add an element to the middle of the queue.
3. Push Back: Add an element to the back of the queue.
4. Pop Front: Remove and return the front element of the queue.
5. Pop Middle: Remove and return the middle element of the queue.
6. Pop Back: Remove and return the back element of the queue.

Imagine you’re at a concert, and you want to let your friend in from the front, but you also want to make sure your other friend in the middle doesn’t feel left out. This is the essence of the Front Middle Back Queue!

Code Solution

Copy Code

class FrontMiddleBackQueue:
    def __init__(self):
        self.frontQueue = collections.deque()
        self.backQueue = collections.deque()

    def pushFront(self, val: int) -> None:
        self.frontQueue.appendleft(val)
        self._moveFrontToBackIfNeeded()

    def pushMiddle(self, val: int) -> None:
        if len(self.frontQueue) == len(self.backQueue):
            self.backQueue.appendleft(val)
        else:
            self.frontQueue.append(val)

    def pushBack(self, val: int) -> None:
        self.backQueue.append(val)
        self._moveBackToFrontIfNeeded()

    def popFront(self) -> int:
        if self.frontQueue:
            x = self.frontQueue.popleft()
            self._moveBackToFrontIfNeeded()
            return x
        if self.backQueue:
            return self.backQueue.popleft()
        return -1

    def popMiddle(self) -> int:
        if not self.frontQueue and not self.backQueue:
            return -1
        if len(self.frontQueue) + 1 == len(self.backQueue):
            return self.backQueue.popleft()
        return self.frontQueue.pop()

    def popBack(self) -> int:
        if self.backQueue:
            x = self.backQueue.pop()
            self._moveFrontToBackIfNeeded()
            return x
        return -1

    def _moveFrontToBackIfNeeded(self) -> None:
        if len(self.frontQueue) - 1 == len(self.backQueue):
            self.backQueue.appendleft(self.frontQueue.pop())

    def _moveBackToFrontIfNeeded(self) -> None:
        if len(self.frontQueue) + 2 == len(self.backQueue):
            self.frontQueue.append(self.backQueue.popleft())

Approach Explanation

The approach taken in this solution involves using two deques (double-ended queues) to manage the elements efficiently. The frontQueue holds the front elements, while the backQueue holds the back elements. The key is to maintain balance between the two queues, ensuring that the middle element can be accessed and modified efficiently.

• Push Operations: Depending on the current sizes of the queues, elements are added to the appropriate queue. The _moveFrontToBackIfNeeded and _moveBackToFrontIfNeeded methods ensure that the queues remain balanced after each operation.
• Pop Operations: The pop methods check the queues in order of priority (front, middle, back) and return the appropriate element while maintaining the balance.

Time and Space Complexity

Time Complexity: Each operation (push or pop) runs in O(1) time on average, thanks to the efficient deque operations.

Space Complexity: The space complexity is O(n), where n is the number of elements in the queue, as we are storing all elements in the two deques.

Real-World Example

Think of a queue at a coffee shop. You have customers at the front, some waiting in the middle, and others at the back. If a new customer arrives and wants to cut in line (push front), or if someone wants to order a special drink (push middle), the barista needs to manage the queue efficiently. This is exactly what our Front Middle Back Queue does!

Similar Problems

• 2-Sum Solution in Python