Problem
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)
Addsval
to the front of the queue.void pushMiddle(int val)
Addsval
to the middle of the queue.void pushBack(int val)
Addsval
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:
- Pushing
6
into 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]
returns3
and results in[1, 2, 4, 5, 6]
.
Examples
Example 1
|
|
Constraints
1 <= val <= 10^9
- At most
1000
calls will be made topushFront
,pushMiddle
,pushBack
,popFront
,popMiddle
, andpopBack
.
Solution
Method 1 – Two Deques (Double-Ended Queues)
Intuition
To efficiently support push and pop operations at the front, middle, and back, we can use two deques to represent the left and right halves of the queue. We keep the left deque always the same size as or one element larger than the right deque. This allows O(1) access to the front, back, and middle.
Approach
- Use two deques (or lists):
left
andright
. - For
pushFront
, insert at the front ofleft
, then rebalance if needed. - For
pushBack
, insert at the back ofright
, then rebalance if needed. - For
pushMiddle
, insert at the end ofleft
if sizes are equal, else at the front ofright
, then rebalance. - For
popFront
, remove from the front ofleft
(orright
ifleft
is empty), then rebalance. - For
popBack
, remove from the back ofright
(orleft
ifright
is empty), then rebalance. - For
popMiddle
, remove from the end ofleft
if sizes are equal or larger, else from the front ofright
, then rebalance. - After each operation, rebalance so that
left.size() == right.size()
orleft.size() == right.size() + 1
.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(1)
amortized per operation, as each element is moved at most a constant number of times between deques. - 🧺 Space complexity:
O(n)
, wheren
is the number of elements in the queue.