Design Front Middle Back Queue
Medium · Stack & Strings · Array · Linked List · Design · Queue · Data Stream
Problem
Design a queue that supports pushing and popping at the front, the middle and the back.
Implement FrontMiddleBackQueue:
- FrontMiddleBackQueue() creates an empty queue.
- pushFront(val), pushMiddle(val) and pushBack(val) insert val at that position.
- popFront(), popMiddle() and popBack() remove and return the element at that position, or return -1 if the queue is empty.
When there are two middle positions, always use the front-most one. For example, pushing 9 into the middle of [1, 2, 3, 4] gives [1, 2, 9, 3, 4], pushing 9 into the middle of [1, 2, 3] gives [1, 9, 2, 3], and popping the middle of [1, 2, 3, 4] removes 2.
Tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments.
Examples
Input: ops = ["FrontMiddleBackQueue","pushBack","pushBack","pushFront","pushMiddle","popMiddle","popMiddle","popBack"], args = [[],[2],[3],[1],[9],[],[],[]] Output: [null,null,null,null,null,9,2,3]
[2, 3] becomes [1, 2, 3], then [1, 9, 2, 3]. Its front-most middle is 9; in [1, 2, 3] the middle is 2; 3 is left at the back.
Input: ops = ["FrontMiddleBackQueue","popFront","pushMiddle","popBack"], args = [[],[],[7],[]] Output: [null,-1,null,7]
Popping an empty queue gives -1; a single element is at every position.
Input: ops = ["FrontMiddleBackQueue","pushBack","pushBack","pushBack","pushBack","popMiddle","pushMiddle","popFront","popFront"], args = [[],[1],[2],[3],[4],[],[8],[],[]] Output: [null,null,null,null,null,2,null,1,8]
From [1, 2, 3, 4] the front-most middle is 2. Pushing 8 into the middle of [1, 3, 4] gives [1, 8, 3, 4].
Constraints
- 1 <= val <= 10^9
- At most 1000 calls are made in total
Approaches
- Baseline: one list, insert and remove by index — time O(n) per call, space O(n)
Follow-up
The tie rule decides which half may hold the extra element. The use cases flip it to the back-most middle, and replay only pushes and return the final queue, which shows where every middle push landed.
Related problems
Start free on Cariara · Coding problems · System design studio
