# 1670. Design Front Middle Back Queue

## Problem Description

The given LeetCode problem asks to design a custom queue structure that allows for insertion (`push`) and removal (`pop`) of elements not only from the traditional front and back but also from the middle of the queue. A `FrontMiddleBack` class needs to be implemented with the following operations:

• `FrontMiddleBack()`: This initializes the queue.
• `pushFront(int val)`: Adds `val` to the front of the queue.
• `pushMiddle(int val)`: Adds `val` to the middle of the queue. If there are two middle positions, it places the value in the frontmost position.
• `pushBack(int val)`: Adds `val` to the back of the queue.
• `popFront()`: Removes and returns the front element of the queue. If the queue is empty, it returns `-1`.
• `popMiddle()`: Removes and returns the middle element of the queue. If the queue is empty, or it has even number of elements, it removes the frontmost middle element and returns it. Otherwise, it returns `-1`.
• `popBack()`: Removes and returns the back element of the queue. If the queue is empty, it returns `-1`.

The operations should be designed such that they maintain the integrity of the queue structure, adjusting the middle as necessary when elements are added or removed.

## Intuition

The intuition behind solving this problem efficiently is to maintain two balanced halves of the queue, such that you can always access the front, middle, or back elements in constant time. The solution involves using two double-ended queues (`deque`), where the first `deque` (`q1`) holds the front half of the elements, and the second `deque` (`q2`) holds the back half.

To ensure that the operations can be performed in constant time, a `rebalance()` function is used to balance the two deques so that either both deques have the same number of elements, or the back deque (`q2`) has one more element than the front deque (`q1`). This way, the `pushMiddle` and `popMiddle` operations can determine the middle element consistently.

Upon each operation, whether it's a push or a pop, we call `rebalance()` to ensure the deques stay balanced for the next operation. When pushing to the middle, the element is appended to the end of `q1` before rebalancing. For popping the middle, the element is taken from `q1` or the front of `q2`, depending on their sizes.

Keeping two queues like this allows for an elegant management of the queue's elements in a way that gives direct access to front, middle, and back elements without needing to iterate through the queue or resort to complex index calculations.

## Solution Approach

The solution approach involves implementing the `FrontMiddleBackQueue` class with methods that manipulate two separate `deque` data structures. Deques are a double-ended queue type available in Python's `collections` module, perfect for this use-case as they allow fast appends and pops from both ends.

Let's go step by step through each method and the `rebalance` method:

• `__init__`: This is the initializer for the `FrontMiddleBackQueue` class. Two `deque` objects are created, `q1` and `q2`, which will be used to store the front and back halves of the queue, respectively.

• `pushFront`: To push an element to the front, we perform the operation on the `q1` deque by using its `appendleft` method. This inserts the element at the front. After inserting, we call the `rebalance` function to ensure `q1` and `q2` are in a balanced state.

• `pushMiddle`: For pushing into the middle, the element is appended to the end of `q1`. After appending, `rebalance` is called to maintain the balanced state.

• `pushBack`: To push an element to the back, we use the `append` method on `q2`. This inserts the element at the end of `q2`. After insertion, `rebalance` is invoked to balance `q1` and `q2`.

• `popFront`: When popping from the front, we attempt to pop from `q1` using `popleft`. If `q1` is empty but `q2` is not, we pop from the front of `q2` instead. After popping, we call `rebalance`.

• `popMiddle`: For popping the middle element, we check if `q1` and `q2` are the same size. If they are, we pop from `q1`. Otherwise, we pop from the front of `q2`. Again, `rebalance` is called post-operation.

• `popBack`: Popping from the back is direct; we just pop from `q2` using its `pop` method. `rebalance` follows.

• `rebalance`: This method maintains the queue in a balanced state. It operates under two conditions: if `q1` has more elements than `q2`, it moves an element from the end of `q1` to the front of `q2`; if `q2` has more than one additional element than `q1`, it moves an element from the front of `q2` to the end of `q1`.

By maintaining the size of `q1` either equal to or one less than the size of `q2`, we can ensure `popMiddle` and `pushMiddle` operations are performed consistently and efficiently. The use of `deque` ensures that all push and pop operations are handled in constant time (`O(1)`), which is critical for the performance of the queue. It's a clever use of two simple data structures to solve a complex problem, demonstrating the power of algorithm design and data structure choice.

๐ช
Level Up Your
Algo Skills

### Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Suppose we perform the following sequence of operations on an initially empty `FrontMiddleBackQueue`:

1. `pushFront(1)`: Adds `1` to the front of the queue.
2. `pushBack(2)`: Adds `2` to the back of the queue.
3. `pushMiddle(3)`: Adds `3` to the middle of the queue.
4. `pushBack(4)`: Adds `4` to the back of the queue.
5. `popFront()`: Removes the front element of the queue.
6. `popMiddle()`: Removes the middle element of the queue.
7. `popBack()`: Removes the back element of the queue.

Here's how the operations will affect the queue:

1. After `pushFront(1)`, the queue (represented by `q1` | `q2`) will be:

``1[1] | []``
2. After `pushBack(2)`, the queue will be:

``1[1] | [2]``

The `rebalance()` is called, and the queue remains the same as it's already balanced.

3. After `pushMiddle(3)`, the queue will be:

``1[1, 3] | [2]``

The `rebalance()` moves `3` to `q2` to maintain the balance, resulting in:

``1[1] | [3, 2]``
4. After `pushBack(4)`, the queue will be:

``1[1] | [3, 2, 4]``
5. After `popFront()`, the element `1` is popped from the front (`q1`). The queue becomes:

``1[] | [3, 2, 4]``

The `rebalance()` is then called to redistribute the elements, shifting one from `q2` to `q1`:

``1[3] | [2, 4]``
6. After `popMiddle()`, we remove the middle element. Since `q1` has one element and `q2` has two elements, we pop from the front of `q2` (which is the value `2`). The resulting queue is:

``1[3] | [4]``
7. Finally, after `popBack()`, we remove the back element from `q2`, which is `4`:

``1[3] | []``

The queue is left with a single element `3` in `q1`.

Each operation involves pushing or popping on `q1` and `q2`, followed by a `rebalance()` to maintain the easy access to front, middle, and back of the queue. This example demonstrates how `rebalance()` plays a critical role in maintaining the queue's order after each operation.

## Python Solution

``````1from collections import deque
2
3class FrontMiddleBackQueue:
4    def __init__(self):
5        self.frontDeque = deque()  # Queue part representing the front
6        self.backDeque = deque()   # Queue part representing the back
7
8    def pushFront(self, val: int) -> None:
9        """Insert a value at the front of the queue."""
10        self.frontDeque.appendleft(val)  # Insert value to the front
11        self._rebalance()  # Ensure the two deques are balanced
12
13    def pushMiddle(self, val: int) -> None:
14        """Insert a value into the middle of the queue."""
15        # When inserting in the middle, we add to the end of the front deque
16        self.frontDeque.append(val)
17        self._rebalance()  # Rebalance the two deques after insertion
18
19    def pushBack(self, val: int) -> None:
20        """Insert a value at the back of the queue."""
21        self.backDeque.append(val)  # Insert value to the back deque
22        self._rebalance()  # Rebalance the two deques after insertion
23
24    def popFront(self) -> int:
25        """Remove and return the value at the front of the queue; return -1 if the queue is empty."""
26        if not self.frontDeque and not self.backDeque:
27            return -1  # Queue is empty
28        val = self.frontDeque.popleft() if self.frontDeque else self.backDeque.popleft()
29        self._rebalance()  # Rebalance after removal
30        return val
31
32    def popMiddle(self) -> int:
33        """Remove and return the value in the middle of the queue; return -1 if the queue is empty."""
34        if not self.frontDeque and not self.backDeque:
35            return -1  # Queue is empty
36        if len(self.frontDeque) == len(self.backDeque):
37            val = self.frontDeque.pop()  # If equal lengths, pop from front deque
38        else:
39            val = self.backDeque.popleft()  # Otherwise, pop from the start of the back deque
40        self._rebalance()  # Rebalance after removal
41        return val
42
43    def popBack(self) -> int:
44        """Remove and return the value at the back of the queue; return -1 if the queue is empty."""
45        if not self.backDeque:
46            return -1  # Queue is empty or only front part has elements
47        val = self.backDeque.pop()  # Pop value from the back deque
48        self._rebalance()  # Rebalance after removal
49        return val
50
51    def _rebalance(self):
52        """Private method to balance the two internal deques. Ensures neither is too long compared to the other."""
53        # Move element from front to back if front deque is longer
54        if len(self.frontDeque) > len(self.backDeque):
55            self.backDeque.appendleft(self.frontDeque.pop())
56        # Conversely, move element from back to front if back deque is bigger by more than one element
57        if len(self.backDeque) > len(self.frontDeque) + 1:
58            self.frontDeque.append(self.backDeque.popleft())
59
60
61# Instantiate the queue and perform operations as required. For example:
62# queue = FrontMiddleBackQueue()
63# queue.pushFront(1)
64# queue.pushMiddle(2)
65# queue.pushBack(3)
66# front = queue.popFront()
67# middle = queue.popMiddle()
68# back = queue.popBack()
69``````

## Java Solution

``````1class FrontMiddleBackQueue {
2    private Deque<Integer> frontQueue = new ArrayDeque<>();
3    private Deque<Integer> backQueue = new ArrayDeque<>();
4
5    // Constructor for the queue.
6    public FrontMiddleBackQueue() {
7        // No initialization is required as the Deques are initialized already.
8    }
9
10    // Adds an element to the front of the queue.
11    public void pushFront(int val) {
12        frontQueue.offerFirst(val);
13        rebalanceQueues();
14    }
15
16    // Adds an element to the middle of the queue.
17    public void pushMiddle(int val) {
18        if(frontQueue.size() <= backQueue.size()) {
19            frontQueue.offerLast(val);
20        } else {
21            backQueue.offerFirst(val);
22        }
23        rebalanceQueues();
24    }
25
26    // Adds an element to the back of the queue.
27    public void pushBack(int val) {
28        backQueue.offerLast(val);
29        rebalanceQueues();
30    }
31
32    // Removes and returns the front element of the queue.
33    public int popFront() {
34        if (isEmpty()) {
35            return -1; // Return -1 if the queue is empty.
36        }
37        int val = frontQueue.isEmpty() ? backQueue.pollFirst() : frontQueue.pollFirst();
38        rebalanceQueues();
39        return val;
40    }
41
42    // Removes and returns the middle element of the queue.
43    public int popMiddle() {
44        if (isEmpty()) {
45            return -1; // Return -1 if the queue is empty.
46        }
47        int val = frontQueue.size() >= backQueue.size() ? frontQueue.pollLast() : backQueue.pollFirst();
48        rebalanceQueues();
49        return val;
50    }
51
52    // Removes and returns the back element of the queue.
53    public int popBack() {
54        if (backQueue.isEmpty()) {
55            return -1; // Return -1 if the queue is empty.
56        }
57        int val = backQueue.pollLast();
58        rebalanceQueues();
59        return val;
60    }
61
62    // Helper method to check if the queue is empty.
63    private boolean isEmpty() {
64        return frontQueue.isEmpty() && backQueue.isEmpty();
65    }
66
67    // Maintains the balance between the two deques so that they represent the proper ordering of elements.
68    private void rebalanceQueues() {
69        // Rebalance if frontQueue has more elements than backQueue.
70        if (frontQueue.size() > backQueue.size() + 1) {
71            backQueue.offerFirst(frontQueue.pollLast());
72        }
73        // Rebalance if backQueue has more elements than frontQueue.
74        if (backQueue.size() > frontQueue.size()) {
75            frontQueue.offerLast(backQueue.pollFirst());
76        }
77    }
78}
79/**
80 * The above FrontMiddleBackQueue class is structured to provide ease of maintaining and rebalancing
81 * the elements in frontQueue and backQueue for all the front, middle, and back operations.
82 */
83``````

## C++ Solution

``````1#include <deque>
2
3// Class for a custom queue that supports inserting and deleting from front, middle, and back.
4class FrontMiddleBackQueue {
5public:
6    // Constructor for the queue.
7    FrontMiddleBackQueue() {}
8
9    // Inserts an element at the front of the queue.
10    void pushFront(int val) {
11        frontQueue.push_front(val);
12        balanceQueues();
13    }
14
15    // Inserts an element in the middle of the queue.
16    void pushMiddle(int val) {
17        frontQueue.push_back(val); // Temporarily insert at the end of the front queue
18        balanceQueues(); // Balance the queues so that the new element is in the middle
19    }
20
21    // Inserts an element at the back of the queue.
22    void pushBack(int val) {
23        backQueue.push_back(val);
24        balanceQueues();
25    }
26
27    // Deletes and returns the front element of the queue. Returns -1 if the queue is empty.
28    int popFront() {
29        if (frontQueue.empty() && backQueue.empty()) return -1;
30        int val = 0;
31        if (!frontQueue.empty()) {
32            val = frontQueue.front();
33            frontQueue.pop_front();
34        } else {
35            val = backQueue.front();
36            backQueue.pop_front();
37        }
38        balanceQueues();
39        return val;
40    }
41
42    // Deletes and returns the middle element of the queue. Returns -1 if the queue is empty.
43    int popMiddle() {
44        if (frontQueue.empty() && backQueue.empty()) return -1;
45        int val = 0;
46        if (frontQueue.size() == backQueue.size()) {
47            val = frontQueue.back();
48            frontQueue.pop_back();
49        } else {
50            val = backQueue.front();
51            backQueue.pop_front();
52        }
53        balanceQueues();
54        return val;
55    }
56
57    // Deletes and returns the back element of the queue. Returns -1 if the queue is empty.
58    int popBack() {
59        if (backQueue.empty()) return -1;
60        int val = backQueue.back();
61        backQueue.pop_back();
62        balanceQueques();
63        return val;
64    }
65
66private:
67    std::deque<int> frontQueue; // Front half of the queue
68    std::deque<int> backQueue; // Back half of the queue
69
70    // Balances the elements between the front and back queues.
71    void balanceQueues() {
72        // If the front queue has more elements than the back queue, move the last element
73        // of the front queue to the front of the back queue.
74        if (frontQueue.size() > backQueue.size()) {
75            backQueue.push_front(frontQueue.back());
76            frontQueue.pop_back();
77        }
78        // If the back queue has more than one extra element compared to the front queue,
79        // move the front element of the back queue to the back of the front queue.
80        if (backQueue.size() > frontQueue.size() + 1) {
81            frontQueue.push_back(backQueue.front());
82            backQueue.pop_front();
83        }
84    }
85};
86
87/**
88 * You may use the FrontMiddleBackQueue class as follows:
89 * FrontMiddleBackQueue* queue = new FrontMiddleBackQueue();
90 * queue->pushFront(value);
91 * queue->pushMiddle(value);
92 * queue->pushBack(value);
93 * int front = queue->popFront();
94 * int middle = queue->popMiddle();
95 * int back = queue->popBack();
96 * delete queue;
97 */
98``````

## Typescript Solution

``````1// Queue class which supports operations on both ends and the middle.
2class FrontMiddleBackQueue {
3    private left: number[];
4    private right: number[];
5
6    constructor() {
7        this.left = [];
8        this.right = [];
9    }
10
11    // Adds an element to the front of the queue.
12    public pushFront(val: number): void {
13        this.left.unshift(val);
14        this.rebalance();
15    }
16
17    // Adds an element to the middle of the queue.
18    public pushMiddle(val: number): void {
19        this.left.push(val);
20        this.rebalance();
21    }
22
23    // Adds an element to the back of the queue.
24    public pushBack(val: number): void {
25        this.right.push(val);
26        this.rebalance();
27    }
28
29    // Removes and returns the element from the front of the queue.
30    public popFront(): number {
31        if (this.isEmpty()) return -1;
32        const num: number = this.left.length === 0 ? this.right.shift()! : this.left.shift()!;
33        this.rebalance();
34        return num;
35    }
36
37    // Removes and returns the middle element from the queue.
38    public popMiddle(): number {
39        if (this.isEmpty()) return -1;
40        const num: number = (this.left.length === this.right.length) ? this.left.pop()! : this.right.shift()!;
41        this.rebalance();
42        return num;
43    }
44
45    // Removes and returns the element from the back of the queue.
46    public popBack(): number {
47        if (this.isEmpty()) return -1;
48        const num: number = this.right.pop()!;
49        this.rebalance();
50        return num;
51    }
52
53    // Helper function to keep the queue balanced between left and right sections.
54    private rebalance(): void {
55        while (this.left.length > this.right.length) {
56            this.right.unshift(this.left.pop()!);
57        }
58        while (this.right.length > this.left.length + 1) {
59            this.left.push(this.right.shift()!);
60        }
61    }
62
63    // Checks if the queue is empty.
64    private isEmpty(): boolean {
65        return this.left.length === 0 && this.right.length === 0;
66    }
67}``````

In this TypeScript rewrite:

• `number[]` is the type annotation specifying the array with elements of type `number`.
• `void` is the return type annotation for methods that do not return a value.
• Methods and variables are given access modifiers such as `private` and `public` to indicate their visibility outside the class.
• The non-null assertion operator (`!`) is used to assert that the value won't be `null` or `undefined`. This is necessary because TypeScript's strict null checking would otherwise object to popping and shifting elements from possibly empty arrays.

Creating an instance of this class and using its methods would be done in the same way as the JavaScript version:

``````1const queue = new FrontMiddleBackQueue();
2queue.pushFront(1);
3queue.pushMiddle(2);
4queue.pushBack(3);
5const front = queue.popFront(); // Should return 1
6const middle = queue.popMiddle(); // Should return 2
7const back = queue.popBack(); // Should return 3
8``````

## Time and Space Complexity

### Time Complexity

• `__init__`: O(1) - Constant time complexity as it initializes two deques.
• `pushFront`: Amortized O(1) - Appending to the front of a deque is typically O(1), rebalance may cause an O(1) operation.
• `pushMiddle`: O(1) - Appending to the end of `q1` deque is O(1), rebalance may cause an O(1) operation.
• `pushBack`: Amortized O(1) - Appending to the end of a deque is typically O(1), rebalance may cause an O(1) operation.
• `popFront`: O(1) - Popping from the front of the deque is O(1), rebalance may cause an O(1) operation.
• `popMiddle`: O(1) - Popping from `q1` or `q2` is O(1), rebalance may cause an O(1) operation.
• `popBack`: O(1) - Popping from the back of `q2` is O(1), rebalance may cause an O(1) operation.
• `rebalance`: O(1) - The rebalance function does at most one operation of moving an element from one deque to another, which is O(1).

For the rebalance operations, when we say amortized O(1), it is because deque operations are generally O(1) unless a resize of the underlying array is necessary. Given that the average case does not trigger a resize, we consider these operations to have an amortized constant time complexity. Note that amortized analysis is a way to represent the complexity of an algorithm over a sequence of operations, reflecting the average cost per operation in the worst case.

### Space Complexity

• Overall: O(n) - The space complexity is based on the number of elements in the queue which could be up to `n`.
• `__init__`: O(1) - Only two deques are initialized, no elements are added initially.
• `pushFront`, `pushMiddle`, `pushBack`, `popFront`, `popMiddle`, `popBack`: These operations don't change the overall space complexity, which remains O(n) depending on the number of elements at any point in time.
๐
Become an
Algo Monster

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ
โTA ๐จโ๐ซ