Watch 8 video solutions for Design Front Middle Back Queue, a medium level problem involving Array, Linked List, Design. This walkthrough by Fraz has 2,407 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |