# Design Front Middle Back Queue
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-front-middle-back-queue)
Canonical: https://scaleengineer.com/dsa/problems/design-front-middle-back-queue
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream)
**Data structures:** Array, Linked List, Queue
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
Design a queue that supports `push` and `pop` operations in the front, middle, and back.

Implement the `FrontMiddleBack` class:

* `FrontMiddleBack()` Initializes the queue.
* `void pushFront(int val)` Adds `val` to the **front** of the queue.
* `void pushMiddle(int val)` Adds `val` to the **middle** of the queue.
* `void pushBack(int val)` Adds `val` to the **back** of the queue.
* `int popFront()` Removes the **front** element of the queue and returns it. If the queue is empty, return `-1`.
* `int popMiddle()` Removes the **middle** element of the queue and returns it. If the queue is empty, return `-1`.
* `int popBack()` Removes the **back** element of the queue and returns it. If the queue is empty, return `-1`.

**Notice** that when there are **two** middle position choices, the operation is performed on the **frontmost** middle position choice. For example:

* Pushing `6` into the middle of `[1, 2, 3, 4, 5]` results in `[1, 2, 6, 3, 4, 5]`.
* Popping the middle from `[1, 2, 3, 4, 5, 6]` returns `3` and results in `[1, 2, 4, 5, 6]`.

**Example 1:**

**Input:**
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
**Output:**
[null, null, null, null, null, 1, 3, 4, 2, -1]

**Explanation:**
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();     // return 1 -> [4, 3, 2]
q.popMiddle();    // return 3 -> [4, 2]
q.popMiddle();    // return 4 -> [2]
q.popBack();      // return 2 -> []
q.popFront();     // return -1 -> [] (The queue is empty)

**Constraints:**

* `1 <= val <= 109`
* At most `1000` calls will be made to `pushFront`, `pushMiddle`, `pushBack`, `popFront`, `popMiddle`, and `popBack`.

# Approaches
## Approach 1: Single Doubly Linked List
This approach uses a single standard data structure, a doubly linked list (specifically `java.util.LinkedList`), to store all the elements of the queue. While operations at the front and back are efficient, operations in the middle require traversing a portion of the list, leading to linear time complexity.
**Time:** - `pushFront`, `pushBack`, `popFront`, `popBack`: O(1)
- `pushMiddle`, `popMiddle`: O(N), as these operations require traversing to the middle of the linked list. · **Space:** O(N), where N is the number of elements in the queue, as we need to store all the elements.
**Pros:** Simple to understand and implement using a standard library data structure.; Efficient O(1) time complexity for front and back operations.
**Cons:** The middle operations, `pushMiddle` and `popMiddle`, have a time complexity of O(N), which can be inefficient for a large number of elements.
### Explanation
A `java.util.LinkedList` is used as the underlying storage for the queue. This choice is better than an `ArrayList` because `LinkedList` provides O(1) time complexity for adding and removing elements at both the front and the back (`addFirst`, `addLast`, `removeFirst`, `removeLast`).

However, for the middle operations, we first need to find the middle index. 
- `pushMiddle(val)` needs to insert an element at index `size / 2`.
- `popMiddle()` needs to remove an element from index `(size - 1) / 2`.

In a `LinkedList`, accessing an element by index is not a constant-time operation. The list must be traversed from the beginning (or end, whichever is closer) to reach the desired index. This traversal takes time proportional to the number of elements, resulting in an O(N) time complexity for `pushMiddle` and `popMiddle`.

```java
import java.util.LinkedList;

class FrontMiddleBackQueue {
    private LinkedList<Integer> list;

    public FrontMiddleBackQueue() {
        list = new LinkedList<>();
    }

    public void pushFront(int val) {
        list.addFirst(val);
    }

    public void pushBack(int val) {
        list.addLast(val);
    }

    public void pushMiddle(int val) {
        int middle = list.size() / 2;
        list.add(middle, val);
    }

    public int popFront() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeFirst();
    }

    public int popMiddle() {
        if (list.isEmpty()) {
            return -1;
        }
        int middle = (list.size() - 1) / 2;
        return list.remove(middle);
    }

    public int popBack() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeLast();
    }
}
```
### Algorithm
- Initialize a `java.util.LinkedList` to store the queue elements.
- For `pushFront(val)`, use the `list.addFirst(val)` method.
- For `pushBack(val)`, use the `list.addLast(val)` method.
- For `popFront()`, use the `list.removeFirst()` method.
- For `popBack()`, use the `list.removeLast()` method.
- For `pushMiddle(val)`, calculate the middle index as `mid = list.size() / 2` and insert the element using `list.add(mid, val)`.
- For `popMiddle()`, calculate the middle index as `mid = (list.size() - 1) / 2` and remove the element using `list.remove(mid)`.

## Approach 2: Two Deques
This optimal approach splits the queue into two halves, managed by two deques (e.g., `ArrayDeque` in Java). By carefully maintaining the relative sizes of the two deques, we can ensure that the front, back, and middle elements are always accessible at one of the ends of the deques. This allows all operations to be performed in constant time.
**Time:** O(1) for all operations (`pushFront`, `pushMiddle`, `pushBack`, `popFront`, `popMiddle`, `popBack`). Each method performs a constant number of O(1) deque operations. · **Space:** O(N), where N is the total number of elements stored across the two deques.
**Pros:** Extremely efficient, with O(1) time complexity for all required operations.; Scales well with a large number of operations and elements.
**Cons:** The implementation is more complex than the single list approach due to the need to manage two deques and maintain the balance between them.
### Explanation
We use two deques, `left` and `right`. The `left` deque stores the first half of the elements, and `right` stores the second half. The entire queue is conceptually the concatenation of `left`'s elements followed by `right`'s elements.

To achieve O(1) complexity for all operations, we enforce a size invariant: `left.size()` is either equal to `right.size()` or one greater. This means `left` will hold the first `ceil(N/2)` elements and `right` will hold the last `floor(N/2)` elements.

This structure makes the key positions readily available:
- **Front**: The head of the `left` deque.
- **Back**: The tail of the `right` deque.
- **Middle**: The tail of the `left` deque.

After any operation that could disrupt the size invariant, a `balance()` helper function is called. This function checks if `left` is too large or too small compared to `right` and moves a single element between them to restore balance. Since deques support O(1) additions and removals from both ends, this rebalancing step is also O(1).

```java
import java.util.ArrayDeque;
import java.util.Deque;

class FrontMiddleBackQueue {
    private Deque<Integer> left;
    private Deque<Integer> right;

    public FrontMiddleBackQueue() {
        left = new ArrayDeque<>();
        right = new ArrayDeque<>();
    }

    // Helper to maintain balance: left.size() is equal to right.size() or right.size() + 1
    private void balance() {
        if (left.size() > right.size() + 1) {
            right.addFirst(left.removeLast());
        }
        if (left.size() < right.size()) {
            left.addLast(right.removeFirst());
        }
    }

    public void pushFront(int val) {
        left.addFirst(val);
        balance();
    }

    public void pushMiddle(int val) {
        if (left.size() > right.size()) {
            right.addFirst(left.removeLast());
        }
        left.addLast(val);
    }

    public void pushBack(int val) {
        right.addLast(val);
        balance();
    }

    public int popFront() {
        if (isEmpty()) {
            return -1;
        }
        int val = left.removeFirst();
        balance();
        return val;
    }

    public int popMiddle() {
        if (isEmpty()) {
            return -1;
        }
        int val = left.removeLast();
        balance();
        return val;
    }

    public int popBack() {
        if (isEmpty()) {
            return -1;
        }
        int val;
        if (right.isEmpty()) {
            val = left.removeLast();
        } else {
            val = right.removeLast();
        }
        balance();
        return val;
    }
    
    private boolean isEmpty() {
        return left.isEmpty() && right.isEmpty();
    }
}
```
### Algorithm
- Initialize two deques (doubly-ended queues), `left` and `right`.
- Maintain an invariant: `left.size()` must be equal to `right.size()` or `right.size() + 1`.
- Create a `balance()` helper function to restore this invariant by moving one element from the larger deque to the smaller one if needed.
- `pushFront(val)`: Add `val` to the front of `left`. Call `balance()`.
- `pushBack(val)`: Add `val` to the back of `right`. Call `balance()`.
- `pushMiddle(val)`: To insert at the conceptual middle, if `left` has more elements than `right`, move `left`'s last element to `right`'s front. Then, add the new `val` to the end of `left`.
- `popFront()`: Remove and return from the front of `left`. Call `balance()`.
- `popBack()`: Remove and return from the back of `right` (or `left` if `right` is empty). Call `balance()`.
- `popMiddle()`: The middle element is always the last element of `left`. Remove and return it. Call `balance()`.

# Solutions
### Java

```java
class FrontMiddleBackQueue { private Deque < Integer > q1 = new ArrayDeque <>(); private Deque < Integer > q2 = new ArrayDeque <>(); public FrontMiddleBackQueue () { } public void pushFront ( int val ) { q1 . offerFirst ( val ); rebalance (); } public void pushMiddle ( int val ) { q1 . offerLast ( val ); rebalance (); } public void pushBack ( int val ) { q2 . offerLast ( val ); rebalance (); } public int popFront () { if ( q1 . isEmpty () && q2 . isEmpty ()) { return - 1 ; } int val = q1 . isEmpty () ? q2 . pollFirst () : q1 . pollFirst (); rebalance (); return val ; } public int popMiddle () { if ( q1 . isEmpty () && q2 . isEmpty ()) { return - 1 ; } int val = q1 . size () == q2 . size () ? q1 . pollLast () : q2 . pollFirst (); rebalance (); return val ; } public int popBack () { if ( q2 . isEmpty ()) { return - 1 ; } int val = q2 . pollLast (); rebalance (); return val ; } private void rebalance () { if ( q1 . size () > q2 . size ()) { q2 . offerFirst ( q1 . pollLast ()); } if ( q2 . size () > q1 . size () + 1 ) { q1 . offerLast ( q2 . pollFirst ()); } } } /** * Your FrontMiddleBackQueue object will be instantiated and called as such: * FrontMiddleBackQueue obj = new FrontMiddleBackQueue(); * obj.pushFront(val); * obj.pushMiddle(val); * obj.pushBack(val); * int param_4 = obj.popFront(); * int param_5 = obj.popMiddle(); * int param_6 = obj.popBack(); */
```

### JavaScript

```javascript
class FrontMiddleBackQueue { constructor () { this . q1 = new Deque (); this . q2 = new Deque (); } pushFront ( val ) { this . q1 . pushFront ( val ); this . rebalance (); } pushMiddle ( val ) { this . q1 . pushBack ( val ); this . rebalance (); } pushBack ( val ) { this . q2 . pushBack ( val ); this . rebalance (); } popFront () { if ( this . q1 . isEmpty () && this . q2 . isEmpty ()) { return - 1 ; } const val = this . q1 . isEmpty () ? this . q2 . popFront () : this . q1 . popFront (); this . rebalance (); return val !== undefined ? val : - 1 ; } popMiddle () { if ( this . q1 . isEmpty () && this . q2 . isEmpty ()) { return - 1 ; } const val = this . q1 . getSize () === this . q2 . getSize () ? this . q1 . popBack () : this . q2 . popFront (); this . rebalance (); return val !== undefined ? val : - 1 ; } popBack () { if ( this . q2 . isEmpty ()) { return - 1 ; } const val = this . q2 . popBack (); this . rebalance (); return val !== undefined ? val : - 1 ; } rebalance () { if ( this . q1 . getSize () > this . q2 . getSize ()) { this . q2 . pushFront ( this . q1 . popBack ()); } if ( this . q2 . getSize () > this . q1 . getSize () + 1 ) { this . q1 . pushBack ( this . q2 . popFront ()); } } } class Node { constructor ( value ) { this . value = value ; this . next = null ; this . prev = null ; } } class Deque { constructor () { this . front = null ; this . back = null ; this . size = 0 ; } pushFront ( val ) { const newNode = new Node ( val ); if ( this . isEmpty ()) { this . front = newNode ; this . back = newNode ; } else { newNode . next = this . front ; this . front . prev = newNode ; this . front = newNode ; } this . size ++ ; } pushBack ( val ) { const newNode = new Node ( val ); if ( this . isEmpty ()) { this . front = newNode ; this . back = newNode ; } else { newNode . prev = this . back ; this . back . next = newNode ; this . back = newNode ; } this . size ++ ; } popFront () { if ( this . isEmpty ()) { return undefined ; } const value = this . front . value ; this . front = this . front . next ; if ( this . front !== null ) { this . front . prev = null ; } else { this . back = null ; } this . size -- ; return value ; } popBack () { if ( this . isEmpty ()) { return undefined ; } const value = this . back . value ; this . back = this . back . prev ; if ( this . back !== null ) { this . back . next = null ; } else { this . front = null ; } this . size -- ; return value ; } frontValue () { return this . front ?. value ; } backValue () { return this . back ?. value ; } getSize () { return this . size ; } isEmpty () { return this . size === 0 ; } } /** * Your FrontMiddleBackQueue object will be instantiated and called as such: * var obj = new FrontMiddleBackQueue() * obj.pushFront(val) * obj.pushMiddle(val) * obj.pushBack(val) * var param_4 = obj.popFront() * var param_5 = obj.popMiddle() * var param_6 = obj.popBack() */
```

### CPP

```cpp
class FrontMiddleBackQueue { public: FrontMiddleBackQueue () { } void pushFront ( int val ) { q1 . push_front ( val ); rebalance (); } void pushMiddle ( int val ) { q1 . push_back ( val ); rebalance (); } void pushBack ( int val ) { q2 . push_back ( val ); rebalance (); } int popFront () { if ( q1 . empty () && q2 . empty ()) return - 1 ; int val = 0 ; if ( q1 . size ()) { val = q1 . front (); q1 . pop_front (); } else { val = q2 . front (); q2 . pop_front (); } rebalance (); return val ; } int popMiddle () { if ( q1 . empty () && q2 . empty ()) return - 1 ; int val = 0 ; if ( q1 . size () == q2 . size ()) { val = q1 . back (); q1 . pop_back (); } else { val = q2 . front (); q2 . pop_front (); } rebalance (); return val ; } int popBack () { if ( q2 . empty ()) return - 1 ; int val = q2 . back (); q2 . pop_back (); rebalance (); return val ; } private: deque < int > q1 ; deque < int > q2 ; void rebalance () { if ( q1 . size () > q2 . size ()) { q2 . push_front ( q1 . back ()); q1 . pop_back (); } if ( q2 . size () > q1 . size () + 1 ) { q1 . push_back ( q2 . front ()); q2 . pop_front (); } } }; /** * Your FrontMiddleBackQueue object will be instantiated and called as such: * FrontMiddleBackQueue* obj = new FrontMiddleBackQueue(); * obj->pushFront(val); * obj->pushMiddle(val); * obj->pushBack(val); * int param_4 = obj->popFront(); * int param_5 = obj->popMiddle(); * int param_6 = obj->popBack(); */
```

### Python

```python
class FrontMiddleBackQueue : def __init__ ( self ): self . q1 = deque () self . q2 = deque () def pushFront ( self , val : int ) -> None : self . q1 . appendleft ( val ) self . rebalance () def pushMiddle ( self , val : int ) -> None : self . q1 . append ( val ) self . rebalance () def pushBack ( self , val : int ) -> None : self . q2 . append ( val ) self . rebalance () def popFront ( self ) -> int : if not self . q1 and not self . q2 : return - 1 if self . q1 : val = self . q1 . popleft () else : # non-empty guaranteed, or else first if for both empty will return val = self . q2 . popleft () self . rebalance () return val def popMiddle ( self ) -> int : if not self . q1 and not self . q2 : return - 1 if len ( self . q1 ) == len ( self . q2 ): val = self . q1 . pop () else : val = self . q2 . popleft () self . rebalance () return val def popBack ( self ) -> int : if not self . q2 : return - 1 val = self . q2 . pop () self . rebalance () return val # q1-size <= q2-size <= 1 + q1-size def rebalance ( self ): if len ( self . q1 ) > len ( self . q2 ): self . q2 . appendleft ( self . q1 . pop ()) if len ( self . q2 ) > len ( self . q1 ) + 1 : self . q1 . append ( self . q2 . popleft ()) # Your FrontMiddleBackQueue object will be instantiated and called as such: # obj = FrontMiddleBackQueue() # obj.pushFront(val) # obj.pushMiddle(val) # obj.pushBack(val) # param_4 = obj.popFront() # param_5 = obj.popMiddle() # param_6 = obj.popBack()
```