1670. Design Front Middle Back Queue

MediumDesignQueueArrayLinked ListData Stream
Leetcode Link

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.

Learn more about Queue, Linked List and Data Stream patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which technique can we use to find the middle of a linked list?

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

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.

Solution Implementation

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
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
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
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}
68```
69
70In this TypeScript rewrite:
71
72- `number[]` is the type annotation specifying the array with elements of type `number`.
73- `void` is the return type annotation for methods that do not return a value.
74- Methods and variables are given access modifiers such as `private` and `public` to indicate their visibility outside the class.
75- 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.
76
77Creating an instance of this class and using its methods would be done in the same way as the JavaScript version:
78
79```typescript
80const queue = new FrontMiddleBackQueue();
81queue.pushFront(1);
82queue.pushMiddle(2);
83queue.pushBack(3);
84const front = queue.popFront(); // Should return 1
85const middle = queue.popMiddle(); // Should return 2
86const back = queue.popBack(); // Should return 3
87
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

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.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Recommended Readings

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Median of Data Stream

Median of Data Stream Given a stream of numbers find the median number at any given time accurate to 1 decimal place Example add_number 1 add_number 2 add_number 3 get_median 2 0 add_number 4 get_median 2 5 Try it yourself Explanation Intuition Brute force way is to sort the entire list every time we get a new number This would be O N log N for each add_number operation One step up is to notice that the list is sorted before we add any new number to it So every

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 πŸ‘¨β€πŸ«