Design Front Middle Back Queue: Two Deques

Design Front Middle Back Queue is LeetCode 1670. You need to build a queue that supports pushing and popping from three positions: front, middle, and back. The catch is that every operation should be efficient. A naive list-based approach gives you O(n) for middle operations because inserting or removing from the center of a list requires shifting elements. The clean solution uses two deques to keep the middle always accessible at the boundary.

The problem

Implement the FrontMiddleBackQueue class with six operations:

• pushFront(val) adds val to the front of the queue
• pushMiddle(val) adds val to the middle of the queue
• pushBack(val) adds val to the back of the queue
• popFront() removes and returns the front element (or -1 if empty)
• popMiddle() removes and returns the middle element (or -1 if empty)
• popBack() removes and returns the back element (or -1 if empty)

When the queue has an even number of elements, the "middle" for push is the position at index n / 2, and for pop it is the element at index (n - 1) / 2. In other words, for even-length queues, push-middle inserts at the later of the two center positions, and pop-middle removes from the earlier one.

The two-deque approach

The key insight: split the queue into a front half and a back half using two deques. If you keep these halves balanced, the middle element is always right at the boundary between them. That means every push and pop, including middle operations, just touches the ends of one or both deques.

The balancing rule is simple: after every operation, make sure the sizes satisfy one of two conditions:

• front.size == back.size (even total length)
• front.size == back.size - 1 (odd total length, extra element in back)

This means the back half is allowed to have at most one more element than the front half. When the queue has odd total length, the true middle element sits at back[0].

After each operation, you run a quick rebalance:

• If front.size > back.size, move the last element of front to the start of back.
• If back.size > front.size + 1, move the first element of back to the end of front.

Both moves are O(1) because deques support efficient operations at both ends.

The solution

from collections import deque

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

    def _balance(self):
        if len(self.front) > len(self.back):
            self.back.appendleft(self.front.pop())
        elif len(self.back) > len(self.front) + 1:
            self.front.append(self.back.popleft())

    def pushFront(self, val):
        self.front.appendleft(val)
        self._balance()

    def pushMiddle(self, val):
        self.front.append(val)
        self._balance()

    def pushBack(self, val):
        self.back.append(val)
        self._balance()

    def popFront(self):
        if not self.front and not self.back:
            return -1
        if self.front:
            val = self.front.popleft()
        else:
            val = self.back.popleft()
        self._balance()
        return val

    def popMiddle(self):
        if not self.front and not self.back:
            return -1
        if len(self.front) == len(self.back):
            val = self.front.pop()
        else:
            val = self.back.popleft()
        self._balance()
        return val

    def popBack(self):
        if not self.front and not self.back:
            return -1
        val = self.back.pop()
        self._balance()
        return val

Let's break down the logic behind each method:

pushFront: Prepend to the front deque, then rebalance. If front gets too large, the rebalance pushes its last element to the start of back.

pushMiddle: Append to the end of front. This places the new value right before the boundary. Rebalance handles the rest.

pushBack: Append to the back deque, then rebalance. If back grows more than one element larger than front, the rebalance shifts back's first element into front.

popFront: If front is not empty, popleft from front. If front is empty (all elements are in back), popleft from back instead. Then rebalance.

popMiddle: When sizes are equal (even total), the middle is the last element of front, so pop from the right end of front. When back is larger (odd total), the middle is the first element of back, so popleft from back. Then rebalance.

popBack: Always pop from the right end of back. Rebalance if needed.

Visual walkthrough

Let's trace through a sequence of operations. Watch how the two deques stay balanced after each step, and how the middle is always right at the boundary.

The rebalancing step is the heart of this design. Every operation touches at most two deque ends, and the rebalance moves at most one element. That keeps everything O(1).

Complexity analysis

Every operation performs a constant number of deque operations (appendleft, append, popleft, pop), each of which is O(1) for Python's collections.deque. The rebalance step moves at most one element.

Space: O(n) where n is the number of elements in the queue. Each element lives in exactly one of the two deques.

Building blocks

This problem is built from one core building block:

Deque-based design. The idea of splitting a data structure into two halves and keeping them balanced is a powerful technique. You see the same pattern in problems like finding the median from a data stream (two heaps), or implementing a deque itself from two stacks. The key mechanic is always the same: maintain a size invariant between the two halves so that the boundary gives you instant access to the element you care about.

The rebalancing logic is also a pattern worth internalizing. Whenever you have two containers that need to stay roughly the same size, the fix is always the same: if one gets too big, move one element to the other. The direction of the move depends on the invariant you are maintaining.

Edge cases

Before submitting, make sure your solution handles these:

• Empty queue pops. Calling popFront, popMiddle, or popBack on an empty queue should return -1. Both deques will be empty, so check for that first.
• Single element. With one element, it lives in the back deque. popFront should still find it there (since front is empty, fall through to back). popMiddle and popBack both pull from back.
• Even vs odd length for middle. When the total length is even, the middle for pop is (n-1)/2, which maps to the last element of front. When odd, it is n/2, which maps to the first element of back. Getting these cases mixed up is the most common bug.
• Alternating push and pop. Interleaving pushFront and popBack (or any mix) should keep the invariant intact. The rebalance runs after every single operation, so no matter what sequence of calls you make, the sizes stay within the allowed range.

From understanding to recall

The two-deque split is easy to understand but tricky to reproduce from memory. Which deque gets the extra element, front or back? When you popMiddle on an even-length queue, do you pop from the end of front or the start of back? Does pushMiddle go to front or back?

These details are small, but getting any of them wrong breaks specific test cases. The _balance method is only four lines, but those four lines encode the entire invariant. If you flip the comparison or move the wrong element, the middle is off by one.

Spaced repetition turns "I understand the two-deque trick" into "I can write the six methods and the balance function from scratch in two minutes." You type it out, verify it passes, and then the system brings it back right before you would forget. After a few reps, the balance direction and the popMiddle case split become automatic.

Related posts

• Implement Queue Using Stacks - Another data structure design problem
• Min Stack - Design problem with O(1) operations
• LRU Cache - Classic design with efficient operations