[LeetCode] 1670. Design Front Middle Back Queue

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.

设计前中后队列。

请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。
请你完成 FrontMiddleBack 类：
FrontMiddleBack() 初始化队列。
void pushFront(int val) 将 val 添加到队列的 最前面 。
void pushMiddle(int val) 将 val 添加到队列的 正中间 。
void pushBack(int val) 将 val 添加到队里的 最后面 。
int popFront() 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popMiddle() 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
请注意当有 两个 中间位置的时候，选择靠前面的位置进行操作。比方说：
将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, 6, 3, 4, 5] 。
从 [1, 2, 3, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-front-middle-back-queue
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这是一道设计题，思路是用两个双端队列deque做。首先我需要创建两个deque，first 和 second。first 在左边，second 在右边。当元素个数为偶数的时候，first 和 second 的元素个数是相同的；但是当元素个数为奇数的时候，right 会比 left 多一个元素。这里我用了一个 balance() 函数确保 right 至多比 left 多一个元素。

pushFront() - 只会从 left 的左侧加元素

pushBack() - 只会从 right 的右侧加元素

popFront() - 只会从 left 的左侧弹出元素

popBack() - 只会从 right 的右侧弹出元素

pushMiddle() - 如果两个 deque 元素个数相同，则加入 right；反之则加入 left

popMiddle() - 如果两个 deque 元素个数相同，则试图弹出 left 的最右侧元素（注意有可能为空）；反之则弹出 right 最左侧的元素

复杂度

时间O(1) - 均摊的O(1)，因为需要balance两个queue
空间O(n)

代码

Java实现

class FrontMiddleBackQueue {
    Deque<Integer> first;
    Deque<Integer> second;

    public FrontMiddleBackQueue() {
        first = new ArrayDeque<>();
        second = new ArrayDeque<>();
    }
    
    public void pushFront(int val) {
        first.offerFirst(val);
        balance();
    }
    
    public void pushMiddle(int val) {
        if (first.size() < second.size()) {
            first.offerLast(val);
        } else {
            second.offerFirst(val);
        }
    }
    
    public void pushBack(int val) {
        second.offerLast(val);
        balance();
    }
    
    public int popFront() {
        Integer num = first.pollFirst();
        if (num == null) {
            num = second.pollFirst();
            return num == null ? -1 : num;
        } else {
            balance();
            return num;
        }
    }
    
    public int popMiddle() {
        if (first.size() == second.size()) {
            Integer num = first.pollLast();
            return num == null ? -1 : num;
        } else {
            return second.pollFirst();
        }
    }
    
    public int popBack() {
        Integer num = second.pollLast();
        balance();
        return num == null ? -1 : num;
    }

    private void balance() {
        if (first.size() > second.size()) {
            second.offerFirst(first.pollLast());
        } else if (first.size() + 1 < second.size()) {
            first.offerLast(second.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();
 */