LeetCode · #1670

Design Front Middle Back Queue Solution

Split the structure into two balanced deques so front, middle, and back operations stay efficient and easy to reason about.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #1670

🏗️

Pattern

Design — Two Deques + Rebalancing

Implement a queue that supports pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack. For even length, the middle is the front-middle.

Example

 FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1); // [1]
q.pushBack(2); // [1, 2]
q.pushMiddle(3); // [1, 3, 2]
q.pushMiddle(4); // [1, 4, 3, 2]
q.popFront(); // 1
q.popMiddle(); // 3
q.popMiddle(); // 4
q.popBack(); // 2 

Section Two · Brute Force

Single List — O(n) Middle Operations

A dynamic array or linked list can represent the queue directly, but middle insertions and deletions require finding and moving around the midpoint repeatedly.

Problem: If every middle operation walks or shifts through the structure, performance becomes O(n) per call. The design challenge wants something cleaner and closer to constant time.

Section Three · Optimal

Two Balanced Deques

Store the left half in front and the right half in back. Maintain this invariant:

front.size() == back.size() OR front.size() == back.size() + 1

That means the current middle is always the last element of front.

💡 Mental model: Think of the queue as split into two trays. The left tray is allowed to hold either the same number of items as the right tray, or exactly one more. Then the middle item is always easy to find: it sits at the end of the left tray.

Rebalancing rules

If front gets too big, move its last element to the front of back.
If back gets bigger than front, move its first element to the back of front.
popMiddle() always removes front.pollLast().

Why front-middle for even length?:

For an even number of elements, the middle is defined as the earlier of the two central positions.
That is exactly the last element of front when the halves are balanced.

Section Four · Walkthrough

Visual Walkthrough

front + back halves

Section Five · Code

Code — Java & Python

Java — two deques

 import java.util.ArrayDeque;
import java.util.Deque;
class FrontMiddleBackQueue {
private final Deque<Integer> front = new ArrayDeque<>();
private final Deque<Integer> back = new ArrayDeque<>();
private void balance() {
if (front.size() > back.size() + 1) {
            back.offerFirst(front.pollLast());
        } else if (front.size() < back.size()) {
            front.offerLast(back.pollFirst());
        }
    }
public void pushFront(int val) {
        front.offerFirst(val);
balance();
    }
public void pushMiddle(int val) {
if (front.size() > back.size())
            back.offerFirst(front.pollLast());
        front.offerLast(val);
    }
public void pushBack(int val) {
        back.offerLast(val);
balance();
    }
public int popFront() {
if (front.isEmpty() && back.isEmpty()) return -1;
int val = !front.isEmpty() ? front.pollFirst() : back.pollFirst();
balance();
return val;
    }
public int popMiddle() {
if (front.isEmpty() && back.isEmpty()) return -1;
int val = front.pollLast();
balance();
return val;
    }
public int popBack() {
if (front.isEmpty() && back.isEmpty()) return -1;
int val = !back.isEmpty() ? back.pollLast() : front.pollLast();
balance();
return val;
    }
}

Python — two deques

 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) + 1:
            self.back.appendleft(self.front.pop())
elif len(self.front) < len(self.back):
            self.front.append(self.back.popleft())
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)
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
val = self.front.popleft() if self.front else self.back.popleft()
        self._balance()
return val
def popMiddle(self) -> int:
if not self.front and not self.back:
return -1
val = self.front.pop()
        self._balance()
return val
def popBack(self) -> int:
if not self.front and not self.back:
return -1
val = self.back.pop() if self.back else self.front.pop()
        self._balance()
return val

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Single list	O(n) middle ops	O(n)
Two balanced deques	O(1) amortized per op	O(n)

Why “amortized”? Each operation does constant deque work plus at most one rebalance move. So the total work per call stays constant.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
Empty queue pop	Return `-1`	All three pop methods must handle emptiness.
Even number of elements	Middle means front-middle	`popMiddle()` should remove the earlier middle.
Only one element	All pop methods return that element	Both deques must remain consistent after removal.

⚠ Common Mistake: Letting back become larger than front. Once that happens, the middle is no longer predictable. Rebalance after any operation that can change sizes.

← Back to Deque practice

LearningTree

LC 1670 · Design Front Middle Back Queue — Solution & Explanation | DSA Guide