Design Front Middle Back Queue
MedPrompt
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)Addsvalto the front of the queue.void pushMiddle(int val)Addsvalto the middle of the queue.void pushBack(int val)Addsvalto 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
6into 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]returns3and 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
1000calls will be made topushFront,pushMiddle,pushBack,popFront,popMiddle, andpopBack.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a
java.util.LinkedListto store the queue elements. - For
pushFront(val), use thelist.addFirst(val)method. - For
pushBack(val), use thelist.addLast(val)method. - For
popFront(), use thelist.removeFirst()method. - For
popBack(), use thelist.removeLast()method. - For
pushMiddle(val), calculate the middle index asmid = list.size() / 2and insert the element usinglist.add(mid, val). - For
popMiddle(), calculate the middle index asmid = (list.size() - 1) / 2and remove the element usinglist.remove(mid).
Walkthrough
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 indexsize / 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.
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(); }}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.
Trade-offs
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,
pushMiddleandpopMiddle, have a time complexity of O(N), which can be inefficient for a large number of elements.
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.
Algorithm
- Initialize two deques (doubly-ended queues),
leftandright. - Maintain an invariant:
left.size()must be equal toright.size()orright.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): Addvalto the front ofleft. Callbalance().pushBack(val): Addvalto the back ofright. Callbalance().pushMiddle(val): To insert at the conceptual middle, iflefthas more elements thanright, moveleft's last element toright's front. Then, add the newvalto the end ofleft.popFront(): Remove and return from the front ofleft. Callbalance().popBack(): Remove and return from the back ofright(orleftifrightis empty). Callbalance().popMiddle(): The middle element is always the last element ofleft. Remove and return it. Callbalance().
Walkthrough
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
leftdeque. - Back: The tail of the
rightdeque. - Middle: The tail of the
leftdeque.
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).
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(); }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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(); */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() */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(); */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()Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.