Design Front Middle Back Queue

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) 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:

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] returns 3 and results in [1, 2, 4, 5, 6].

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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 <= 10^9
At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

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 and right.
For pushFront, insert at the front of left, then rebalance if needed.
For pushBack, insert at the back of right, then rebalance if needed.
For pushMiddle, insert at the end of left if sizes are equal, else at the front of right, then rebalance.
For popFront, remove from the front of left (or right if left is empty), then rebalance.
For popBack, remove from the back of right (or left if right is empty), then rebalance.
For popMiddle, remove from the end of left if sizes are equal or larger, else from the front of right, then rebalance.
After each operation, rebalance so that left.size() == right.size() or left.size() == right.size() + 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


class FrontMiddleBackQueue {
    deque<int> left, right;
    void balance() {
        while (left.size() > right.size() + 1) {
            right.push_front(left.back());
            left.pop_back();
        }
        while (left.size() < right.size()) {
            left.push_back(right.front());
            right.pop_front();
        }
    }
public:
    FrontMiddleBackQueue() {}
    void pushFront(int val) {
        left.push_front(val);
        balance();
    }
    void pushMiddle(int val) {
        if (left.size() > right.size()) right.push_front(val);
        else left.push_back(val);
        balance();
    }
    void pushBack(int val) {
        right.push_back(val);
        balance();
    }
    int popFront() {
        if (left.empty() && right.empty()) return -1;
        int ans;
        if (!left.empty()) {
            ans = left.front();
            left.pop_front();
        } else {
            ans = right.front();
            right.pop_front();
        }
        balance();
        return ans;
    }
    int popMiddle() {
        if (left.empty() && right.empty()) return -1;
        int ans;
        if (left.size() >= right.size()) {
            ans = left.back();
            left.pop_back();
        } else {
            ans = right.front();
            right.pop_front();
        }
        balance();
        return ans;
    }
    int popBack() {
        if (left.empty() && right.empty()) return -1;
        int ans;
        if (!right.empty()) {
            ans = right.back();
            right.pop_back();
        } else {
            ans = left.back();
            left.pop_back();
        }
        balance();
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77


type FrontMiddleBackQueue struct {
    left, right []int
}
func Constructor() FrontMiddleBackQueue {
    return FrontMiddleBackQueue{}
}
func (q *FrontMiddleBackQueue) balance() {
    for len(q.left) > len(q.right)+1 {
        q.right = append([]int{q.left[len(q.left)-1]}, q.right...)
        q.left = q.left[:len(q.left)-1]
    }
    for len(q.left) < len(q.right) {
        q.left = append(q.left, q.right[0])
        q.right = q.right[1:]
    }
}
func (q *FrontMiddleBackQueue) PushFront(val int) {
    q.left = append([]int{val}, q.left...)
    q.balance()
}
func (q *FrontMiddleBackQueue) PushMiddle(val int) {
    if len(q.left) > len(q.right) {
        q.right = append([]int{val}, q.right...)
    } else {
        q.left = append(q.left, val)
    }
    q.balance()
}
func (q *FrontMiddleBackQueue) PushBack(val int) {
    q.right = append(q.right, val)
    q.balance()
}
func (q *FrontMiddleBackQueue) PopFront() int {
    if len(q.left) == 0 && len(q.right) == 0 {
        return -1
    }
    var ans int
    if len(q.left) > 0 {
        ans = q.left[0]
        q.left = q.left[1:]
    } else {
        ans = q.right[0]
        q.right = q.right[1:]
    }
    q.balance()
    return ans
}
func (q *FrontMiddleBackQueue) PopMiddle() int {
    if len(q.left) == 0 && len(q.right) == 0 {
        return -1
    }
    var ans int
    if len(q.left) >= len(q.right) {
        ans = q.left[len(q.left)-1]
        q.left = q.left[:len(q.left)-1]
    } else {
        ans = q.right[0]
        q.right = q.right[1:]
    }
    q.balance()
    return ans
}
func (q *FrontMiddleBackQueue) PopBack() int {
    if len(q.left) == 0 && len(q.right) == 0 {
        return -1
    }
    var ans int
    if len(q.right) > 0 {
        ans = q.right[len(q.right)-1]
        q.right = q.right[:len(q.right)-1]
    } else {
        ans = q.left[len(q.left)-1]
        q.left = q.left[:len(q.left)-1]
    }
    q.balance()
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


import java.util.*;
public class FrontMiddleBackQueue {
    Deque<Integer> left = new ArrayDeque<>(), right = new ArrayDeque<>();
    private void balance() {
        while (left.size() > right.size() + 1) right.addFirst(left.pollLast());
        while (left.size() < right.size()) left.addLast(right.pollFirst());
    }
    public FrontMiddleBackQueue() {}
    public void pushFront(int val) {
        left.addFirst(val);
        balance();
    }
    public void pushMiddle(int val) {
        if (left.size() > right.size()) right.addFirst(val);
        else left.addLast(val);
        balance();
    }
    public void pushBack(int val) {
        right.addLast(val);
        balance();
    }
    public int popFront() {
        if (left.isEmpty() && right.isEmpty()) return -1;
        int ans;
        if (!left.isEmpty()) ans = left.pollFirst();
        else ans = right.pollFirst();
        balance();
        return ans;
    }
    public int popMiddle() {
        if (left.isEmpty() && right.isEmpty()) return -1;
        int ans;
        if (left.size() >= right.size()) ans = left.pollLast();
        else ans = right.pollFirst();
        balance();
        return ans;
    }
    public int popBack() {
        if (left.isEmpty() && right.isEmpty()) return -1;
        int ans;
        if (!right.isEmpty()) ans = right.pollLast();
        else ans = left.pollLast();
        balance();
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


import java.util.ArrayDeque
class FrontMiddleBackQueue {
    private val left = ArrayDeque<Int>()
    private val right = ArrayDeque<Int>()
    private fun balance() {
        while (left.size > right.size + 1) right.addFirst(left.removeLast())
        while (left.size < right.size) left.addLast(right.removeFirst())
    }
    fun pushFront(v: Int) {
        left.addFirst(v)
        balance()
    }
    fun pushMiddle(v: Int) {
        if (left.size > right.size) right.addFirst(v)
        else left.addLast(v)
        balance()
    }
    fun pushBack(v: Int) {
        right.addLast(v)
        balance()
    }
    fun popFront(): Int {
        if (left.isEmpty() && right.isEmpty()) return -1
        val ans = if (left.isNotEmpty()) left.removeFirst() else right.removeFirst()
        balance()
        return ans
    }
    fun popMiddle(): Int {
        if (left.isEmpty() && right.isEmpty()) return -1
        val ans = if (left.size >= right.size) left.removeLast() else right.removeFirst()
        balance()
        return ans
    }
    fun popBack(): Int {
        if (left.isEmpty() && right.isEmpty()) return -1
        val ans = if (right.isNotEmpty()) right.removeLast() else left.removeLast()
        balance()
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


from collections import deque
class FrontMiddleBackQueue:
    def __init__(self):
        self.left = deque()
        self.right = deque()
    def balance(self):
        while len(self.left) > len(self.right) + 1:
            self.right.appendleft(self.left.pop())
        while len(self.left) < len(self.right):
            self.left.append(self.right.popleft())
    def pushFront(self, val: int) -> None:
        self.left.appendleft(val)
        self.balance()
    def pushMiddle(self, val: int) -> None:
        if len(self.left) > len(self.right):
            self.right.appendleft(val)
        else:
            self.left.append(val)
        self.balance()
    def pushBack(self, val: int) -> None:
        self.right.append(val)
        self.balance()
    def popFront(self) -> int:
        if not self.left and not self.right:
            return -1
        if self.left:
            ans = self.left.popleft()
        else:
            ans = self.right.popleft()
        self.balance()
        return ans
    def popMiddle(self) -> int:
        if not self.left and not self.right:
            return -1
        if len(self.left) >= len(self.right):
            ans = self.left.pop()
        else:
            ans = self.right.popleft()
        self.balance()
        return ans
    def popBack(self) -> int:
        if not self.left and not self.right:
            return -1
        if self.right:
            ans = self.right.pop()
        else:
            ans = self.left.pop()
        self.balance()
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74


use std::collections::VecDeque;
struct FrontMiddleBackQueue {
    left: VecDeque<i32>,
    right: VecDeque<i32>,
}
impl FrontMiddleBackQueue {
    fn new() -> Self {
        Self { left: VecDeque::new(), right: VecDeque::new() }
    }
    fn balance(&mut self) {
        while self.left.len() > self.right.len() + 1 {
            if let Some(x) = self.left.pop_back() {
                self.right.push_front(x);
            }
        }
        while self.left.len() < self.right.len() {
            if let Some(x) = self.right.pop_front() {
                self.left.push_back(x);
            }
        }
    }
    fn push_front(&mut self, val: i32) {
        self.left.push_front(val);
        self.balance();
    }
    fn push_middle(&mut self, val: i32) {
        if self.left.len() > self.right.len() {
            self.right.push_front(val);
        } else {
            self.left.push_back(val);
        }
        self.balance();
    }
    fn push_back(&mut self, val: i32) {
        self.right.push_back(val);
        self.balance();
    }
    fn pop_front(&mut self) -> i32 {
        if self.left.is_empty() && self.right.is_empty() {
            return -1;
        }
        let ans = if !self.left.is_empty() {
            self.left.pop_front().unwrap()
        } else {
            self.right.pop_front().unwrap()
        };
        self.balance();
        ans
    }
    fn pop_middle(&mut self) -> i32 {
        if self.left.is_empty() && self.right.is_empty() {
            return -1;
        }
        let ans = if self.left.len() >= self.right.len() {
            self.left.pop_back().unwrap()
        } else {
            self.right.pop_front().unwrap()
        };
        self.balance();
        ans
    }
    fn pop_back(&mut self) -> i32 {
        if self.left.is_empty() && self.right.is_empty() {
            return -1;
        }
        let ans = if !self.right.is_empty() {
            self.right.pop_back().unwrap()
        } else {
            self.left.pop_back().unwrap()
        };
        self.balance();
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


class FrontMiddleBackQueue {
    private left: number[] = [];
    private right: number[] = [];
    private balance() {
        while (this.left.length > this.right.length + 1) this.right.unshift(this.left.pop()!);
        while (this.left.length < this.right.length) this.left.push(this.right.shift()!);
    }
    pushFront(val: number): void {
        this.left.unshift(val);
        this.balance();
    }
    pushMiddle(val: number): void {
        if (this.left.length > this.right.length) this.right.unshift(val);
        else this.left.push(val);
        this.balance();
    }
    pushBack(val: number): void {
        this.right.push(val);
        this.balance();
    }
    popFront(): number {
        if (!this.left.length && !this.right.length) return -1;
        let ans: number;
        if (this.left.length) ans = this.left.shift()!;
        else ans = this.right.shift()!;
        this.balance();
        return ans;
    }
    popMiddle(): number {
        if (!this.left.length && !this.right.length) return -1;
        let ans: number;
        if (this.left.length >= this.right.length) ans = this.left.pop()!;
        else ans = this.right.shift()!;
        this.balance();
        return ans;
    }
    popBack(): number {
        if (!this.left.length && !this.right.length) return -1;
        let ans: number;
        if (this.right.length) ans = this.right.pop()!;
        else ans = this.left.pop()!;
        this.balance();
        return ans;
    }
}

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), where n is the number of elements in the queue.

Problem#

Examples#

Example 1#

Constraints#

Solution#

Method 1 – Two Deques (Double-Ended Queues)#

Intuition#

Approach#

Code#

Complexity#