Leetcode 1670. Design Front Middle Back Queue

1670. Design Front Middle Back Queue
      Medium
      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].

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 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

解法1：这题调通不容易。有点像find median in a stream那题，不过那题是用两个set，这里不需要两个set，用两个deque就可以了，因为deque取两端的值的时间复杂度都是O(1)。
需要注意的是：

1. rightsize-1 <= left.size <= right.size，也就是说left不会比right长，但最短也就比right少一个元素。
2. 每次push/pop front/back了都必须要balance。
3. push/pop middle的时候要选择到底是从left还是从right push/pop，不需要balance，因为可以自己选择。

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

private:
    deque<int> left, right;
    void balance() {
        if (left.size() > right.size()) {
            right.push_front(left.back());
            left.pop_back();
        } else if (right.size() > left.size() + 1) {
            left.push_back(right.front());
            right.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();
 */
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
78
79
80
81
82
83
84