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:
6 into the middle of [1, 2, 3, 4, 5] results in [1, 2, 6, 3, 4, 5].[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 <= 1091000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.Problem Overview: Design a queue that supports insertion and deletion from three positions: the front, the middle, and the back. The data structure must expose operations like pushFront, pushMiddle, pushBack, and their corresponding pop operations while keeping the middle definition consistent as elements change.
Approach 1: Deque Based Approach (O(1) time, O(n) space)
The cleanest solution splits the queue into two balanced halves using two deque structures: left and right. The invariant is that left.size() is either equal to right.size() or exactly one larger. Front operations interact with the front of left, back operations interact with the end of right, and middle operations insert or remove from the boundary between them. After every operation, you rebalance by moving one element between the deques if the size difference breaks the invariant. Because deque operations like append, appendleft, pop, and popleft run in constant time, every queue operation also runs in O(1) time with O(n) space for stored elements.
This approach is practical in languages with efficient deque implementations such as Python and JavaScript. Conceptually it behaves like maintaining the left half and right half of the queue separately, which makes the "middle" position simply the boundary between them. It relies heavily on properties of a queue and efficient double-ended operations.
Approach 2: Linked List Based Approach (O(1) time, O(n) space)
A lower-level implementation uses a doubly linked list with explicit pointers to the head, tail, and middle node. Each insertion or deletion updates the relevant pointer and then adjusts the middle pointer depending on whether the size of the list becomes even or odd. For example, when inserting near the front while the size becomes odd, the middle pointer may move one step backward. When removing elements, similar pointer adjustments maintain the correct middle node.
This design mirrors how queues can be implemented from scratch without relying on built‑in containers. Every operation touches only a constant number of nodes and pointer updates, so the runtime remains O(1). Space usage is O(n) for the nodes themselves. It is a good exercise in pointer manipulation and fits naturally with classic design and data stream style problems.
Recommended for interviews: The two-deque solution is typically the expected answer. It demonstrates the key insight: keep the queue split into balanced halves so the middle element is always easy to access. A linked list version shows strong understanding of pointer-based data structures, but the deque approach communicates the idea faster and is easier to implement correctly under interview pressure.
This approach utilizes two separate deques (or double-ended queues) to manage the elements efficiently. One deque manages the left half of the queue and the other manages the right half.
For operations concerning the front, we utilize the front of the left deque. For back operations, we utilize the back of the right deque.
For middle operations, we ensure that the deques remain balanced or have at most a one-element difference. The 'middle' element is the last element of the left deque when both deques have equal size, or the first element of the right deque otherwise.
Balancing the two deques efficiently allows you to perform middle operations in constant amortized time.
The implementation utilizes two deques from the Python standard library to efficiently manage operations at the front, middle, and back. By maintaining two separate deques for the left and right segments of the queue, the solution is able to balance the elements by moving elements between the deques when necessary.
The balance method ensures that the sizes of the deques differ by at most one, which is crucial for correct middle element operations.
Python
JavaScript
Time Complexity: The time complexity for each operation is O(1) due to the efficient re-balancing of the deques.
Space Complexity: O(N), where N is the number of elements in the queue.
This approach uses a doubly linked list to implement the queue, which allows efficient insertion and deletion from both ends and from the middle.
By keeping a pointer/reference to the middle node, operations that involve the middle element can be performed in constant time. The challenge is to keep the middle pointer updated correctly as elements are added or removed.
This design achieves a consistent constant time complexity for all operations, though it requires careful handling of pointers due to frequent updates, especially in middle operations.
The C++ implementation uses a doubly linked list to manage the queue elements. Each node has pointers to its previous and next nodes, allowing for efficient insertion and removal from any position.
The solution maintains a pointer to the middle element, updating it as necessary to reflect changes in the list structure. This approach handles list elements in a highly flexible manner, supporting the required operations in constant time.
Time Complexity: O(1) for each operation, due to the efficient handling of linked list pointers and constant time updates of the middle node.
Space Complexity: O(N), where N is the number of elements in the queue.
We use two deques, where q_1 stores the first half, and q_2 stores the second half. The rebalance function is used to maintain the balance between the two queues, i.e., keeping the length of q_2 greater than or equal to the length of q_1, and the difference in length does not exceed 1.
In the pushFront, pushMiddle, and pushBack functions, we only need to add elements to q_1 or q_2, and call the rebalance function.
For the popFront function, we need to check whether q_1 and q_2 are empty. If both are empty, return -1. Otherwise, we need to check whether q_1 is empty. If not, pop the front element of q_1, otherwise pop the front element of q_2, and call the rebalance function.
For the popMiddle function, we need to check whether q_1 and q_2 are empty. If both are empty, return -1. Otherwise, we need to check whether the lengths of q_1 and q_2 are equal. If they are equal, pop the last element of q_1, otherwise pop the front element of q_2, and call the rebalance function.
For the popBack function, we only need to check whether q_2 is empty. If it is empty, return -1. Otherwise, pop the last element of q_2, and call the rebalance function.
The time complexity of the above operations is O(1), and the space complexity is O(n), where n is the number of elements in the queue.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Deque Based Approach | Time Complexity: The time complexity for each operation is O(1) due to the efficient re-balancing of the deques. |
| Linked List Based Approach | Time Complexity: O(1) for each operation, due to the efficient handling of linked list pointers and constant time updates of the middle node. |
| Two Deques | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Deques (Balanced Halves) | O(1) per operation | O(n) | Best practical solution when a language provides efficient deque operations |
| Doubly Linked List with Middle Pointer | O(1) per operation | O(n) | Useful when implementing custom data structures or practicing pointer manipulation |
Leetcode 1670. Design Front Middle Back Queue • Fraz • 2,407 views views
Watch 7 more video solutions →Practice Design Front Middle Back Queue with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor