Design Front Middle Back Queue

medium queue deque design

Problem

Design a queue you can push to and pop from at three places: the front, the back, and the exact middle. pushMiddle(val) inserts at the frontmost middle position, popMiddle() removes and returns the frontmost middle element, and every pop returns −1 when the queue is empty.

For example, pushing 6 into the middle of [1, 2, 3, 4, 5] gives [1, 2, 6, 3, 4, 5]: whenever two positions could count as the middle, the frontmost one wins — for pushes and pops alike.

InputpushFront 1, pushBack 2, pushMiddle 3, pushMiddle 4, popFront, popMiddle, popMiddle, popBack, popFront

Output1, 3, 4, 2, -1

After the four pushes the queue reads [1, 4, 3, 2]; the pops then return the front 1, the middles 3 and 4, the back 2, and −1 once the queue is empty.

operations (semicolon-separated, e.g. pushFront 1; popMiddle)

from collections import deque

class FrontMiddleBackQueue:
    def __init__(self):
        self.a = deque()   # first half
        self.b = deque()   # second half, may hold one extra
    def _balance(self):
        if len(self.a) > len(self.b):
            self.b.appendleft(self.a.pop())
        elif len(self.b) > len(self.a) + 1:
            self.a.append(self.b.popleft())
    def push_front(self, val):
        self.a.appendleft(val); self._balance()
    def push_middle(self, val):
        self.b.appendleft(val); self._balance()
    def push_back(self, val):
        self.b.append(val); self._balance()
    def pop_front(self):
        if not self.b: return -1
        val = self.a.popleft() if self.a else self.b.popleft()
        self._balance(); return val
    def pop_middle(self):
        if not self.b: return -1
        return self.a.pop() if len(self.a) == len(self.b) else self.b.popleft()
    def pop_back(self):
        if not self.b: return -1
        val = self.b.pop(); self._balance(); return val

class FrontMiddleBackQueue {
  constructor() { this.a = []; this.b = []; } // a = first half, b = second half
  balance() {
    if (this.a.length > this.b.length) this.b.unshift(this.a.pop());
    else if (this.b.length > this.a.length + 1) this.a.push(this.b.shift());
  }
  pushFront(val) { this.a.unshift(val); this.balance(); }
  pushMiddle(val) { this.b.unshift(val); this.balance(); }
  pushBack(val) { this.b.push(val); this.balance(); }
  popFront() {
    if (this.b.length === 0) return -1;
    const val = this.a.length ? this.a.shift() : this.b.shift();
    this.balance();
    return val;
  }
  popMiddle() {
    if (this.b.length === 0) return -1;
    return this.a.length === this.b.length ? this.a.pop() : this.b.shift();
  }
  popBack() {
    if (this.b.length === 0) return -1;
    const val = this.b.pop();
    this.balance();
    return val;
  }
}

class FrontMiddleBackQueue {
    Deque<Integer> a = new ArrayDeque<>(), b = new ArrayDeque<>();
    void balance() {
        if (a.size() > b.size()) b.addFirst(a.pollLast());
        else if (b.size() > a.size() + 1) a.addLast(b.pollFirst());
    }
    public void pushFront(int val) { a.addFirst(val); balance(); }
    public void pushMiddle(int val) { b.addFirst(val); balance(); }
    public void pushBack(int val) { b.addLast(val); balance(); }
    public int popFront() {
        if (b.isEmpty()) return -1;
        int val = a.isEmpty() ? b.pollFirst() : a.pollFirst();
        balance();
        return val;
    }
    public int popMiddle() {
        if (b.isEmpty()) return -1;
        return a.size() == b.size() ? a.pollLast() : b.pollFirst();
    }
    public int popBack() {
        if (b.isEmpty()) return -1;
        int val = b.pollLast();
        balance();
        return val;
    }
}

class FrontMiddleBackQueue {
    deque<int> a, b;   // a = first half, b = second half
    void balance() {
        if (a.size() > b.size()) { b.push_front(a.back()); a.pop_back(); }
        else if (b.size() > a.size() + 1) { a.push_back(b.front()); b.pop_front(); }
    }
public:
    void pushFront(int val) { a.push_front(val); balance(); }
    void pushMiddle(int val) { b.push_front(val); balance(); }
    void pushBack(int val) { b.push_back(val); balance(); }
    int popFront() {
        if (b.empty()) return -1;
        int val;
        if (a.empty()) { val = b.front(); b.pop_front(); }
        else { val = a.front(); a.pop_front(); }
        balance();
        return val;
    }
    int popMiddle() {
        if (b.empty()) return -1;
        if (a.size() == b.size()) { int v = a.back(); a.pop_back(); return v; }
        int v = b.front(); b.pop_front(); return v;
    }
    int popBack() {
        if (b.empty()) return -1;
        int val = b.back(); b.pop_back();
        balance();
        return val;
    }
};

Explanation

One list would make middle operations O(n) by definition — you would have to walk or shift half the elements. The trick is to split the queue into two deques: A holds the first half and B the second half, with the invariant |A| ≤ |B| ≤ |A| + 1. The seam between them is the middle, so every operation touches only the ends of a deque — all O(1).

Pushes are end operations plus a fix-up: pushFront adds to A's front, pushBack to B's back, and pushMiddle to B's front (the frontmost middle slot). After each push a balance() call restores the invariant by shuttling one element across the seam — A's back to B's front if A grew too long, or B's front to A's back if B leads by two.

Pops mirror this. popFront takes A's front (or B's front when only one element remains), popBack takes B's back, and both rebalance. popMiddle needs no rebalance at all: when the halves are equal the frontmost middle is exactly A's back, and when B holds the extra element the middle is exactly B's front — either way the invariant survives the removal.

Walk the default example. pushFront(1), pushBack(2), pushMiddle(3), pushMiddle(4) leave A = [1, 4] and B = [3, 2], i.e. the queue [1, 4, 3, 2] — note how pushMiddle(4) landed in the frontmost middle slot and was then shuttled into A. popFront returns 1, popMiddle returns 3 (B's front, since B held the extra), popMiddle returns 4 (A's back, halves were equal), popBack returns 2, and the final popFront on an empty queue returns −1.

Emptiness checks reduce to one test: because |A| ≤ |B|, the queue is empty exactly when B is. Every operation does O(1) deque pushes/pops plus at most one balancing move, so each runs in O(1) time, and the two deques together store each element once for O(n) space.

Time: O(1) per operation Space: O(n)