1670-设计前中后队列(Design Front Middle Back Queue)

原文链接: https://leetcode-cn.com/problems/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 <= 10⁹
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] 。

示例 1：

输入：
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出：
[null, null, null, null, null, 1, 3, 4, 2, -1]

解释：
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();     // 返回 1 -> [4, 3, 2]
q.popMiddle();    // 返回 3 -> [4, 2]
q.popMiddle();    // 返回 4 -> [2]
q.popBack();      // 返回 2 -> []
q.popFront();     // 返回 -1 -> [] （队列为空）

提示：

1 <= val <= 10⁹
最多调用 1000 次 pushFront， pushMiddle， pushBack， popFront， popMiddle 和 popBack 。

通过代码

高赞题解

方法一：用数组模拟

思路与算法

最简单的方法就是使用一个语言自带的数组来模拟这个队列了，例如 C++ 的 std::vector 或者 Python 的 list。

需要注意的仅仅是正确计算「正中间」的位置，其它就按照题目要求的做就可以啦。

代码

[sol1-C++]
class FrontMiddleBackQueue {
private:
    vector<int> q;
    
public:
    FrontMiddleBackQueue() {}
    
    void pushFront(int val) {
        q.insert(q.begin(), val);
    }
    
    void pushMiddle(int val) {
        // 注意正确计算位置
        int pos = q.size() / 2;
        q.insert(q.begin() + pos, val);
    }
    
    void pushBack(int val) {
        q.push_back(val);
    }
    
    int popFront() {
        if (q.empty()) {
            return -1;
        }
        int ret = q[0];
        q.erase(q.begin());
        return ret;
    }
    
    int popMiddle() {
        if (q.empty()) {
            return -1;
        }
        // 注意正确计算位置
        int pos = (q.size() - 1) / 2;
        int ret = q[pos];
        q.erase(q.begin() + pos);
        return ret;
    }
    
    int popBack() {
        if (q.empty()) {
            return -1;
        }
        int ret = q.back();
        q.pop_back();
        return ret;
    }
};

[sol1-Python3]
class FrontMiddleBackQueue:

    def __init__(self):
        self.q = list()

    def pushFront(self, val: int) -> None:
        self.q[0:0] = [val]

    def pushMiddle(self, val: int) -> None:
        # 注意正确计算位置
        pos = len(self.q) // 2
        self.q[pos:pos] = [val]

    def pushBack(self, val: int) -> None:
        self.q.append(val)

    def popFront(self) -> int:
        if not self.q:
            return -1
        ret = self.q[0]
        self.q[0:1] = []
        return ret

    def popMiddle(self) -> int:
        if not self.q:
            return -1
        # 注意正确计算位置
        pos = (len(self.q) - 1) // 2
        ret = self.q[pos]
        self.q[pos:pos+1] = []
        return ret

    def popBack(self) -> int:
        if not self.q:
            return -1
        return self.q.pop()

复杂度分析

时间复杂度：$O(n^2)$，其中 $n$ 是操作次数。在最坏情况下，我们每次都调用 pushFront() 或者 pushMiddle()，插入元素的时间复杂度与数组的长度成正比，为 $O(n)$，因此总时间复杂度为 $O(n^2)$。
空间复杂度：$O(n)$。

方法二：用链表模拟

思路与算法

方法一的时间复杂度太高了，有啥数据结构可以 $O(1)$ 删除呢？容易想到「链表」，链表所有涉及最前面和最后面的操作都很简单，但正中间怎么办？我们可以想到的是，使用一个额外的指针实时地指向链表的正中间，在遇到任何一种操作时，由于都是添加或者删除一个元素，那么正中间对应的位置要么不变，要么向左或者向右移动一个位置。为了方便维护，我们可以记录链表的总长度以及当前正中间指针指向的元素到底是第几个。这样一来，在遇到任何一种操作后，链表的总长度发生变化，我们也可以计算出变化之后正中间应该是第几个元素，根据此调整指针的位置即可。

我们还可以发现，其实我们并不用时刻维护这个指针，而是在遇到 pushMiddle() 或者 popMiddle() 的时候再去移动它。这样做可能会移动超过一个位置，那么时间复杂度会增大吗？实际上是不会的，我们可以使用「均摊分析」，一次过去的操作最多会使未来最近的那一次 pushMiddle() 或者 popMiddle() 操作的指针多移动一个位置，那么均摊下来，指针移动的时间复杂度仍然为 $O(1)$。

细节

我们需要使用双向链表。由于 C++ 有 std::list 所以不用手写一个双向链表，但 Python 就需要手写啦。并且本题中由于链表可能为空，因此在头尾分别使用一个哑（dummy）节点，并且将链表的初始长度置为 $2$，可以很方便地处理边界情况。

代码

[sol2-C++]
class FrontMiddleBackQueue {
private:
    list<int> q;
    // 指向正中间的指针
    list<int>::iterator it;
    // 指针目前位于第几个元素
    int ptrpos;
    
public:
    FrontMiddleBackQueue(): q{initializer_list<int>{42, 42}}, it{q.begin()}, ptrpos{0} {}
    
    void pushFront(int val) {
        // 指针不指向哑头节点
        if (ptrpos != 0) {
            ++ptrpos;
        }
        q.insert(next(q.begin()), val);
    }
    
    void pushMiddle(int val) {
        int pos = q.size() / 2;
        // 均摊 O(1)
        advance(it, pos - ptrpos);
        q.insert(it, val);
        ptrpos = pos + 1;
    }
    
    void pushBack(int val) {
        // 指针指向哑尾节点
        if (ptrpos == q.size() - 1) {
            ++ptrpos;
        }
        q.insert(prev(q.end()), val);
    }
    
    int popFront() {
        if (q.size() == 2) {
            return -1;
        }
        int ret = *next(q.begin());
        if (ptrpos == 1) {
            it = q.erase(it);
        }
        else {
            q.erase(next(q.begin()));
            // 指针不指向哑头节点
            if (ptrpos != 0) {
                --ptrpos;
            }
        }
        return ret;
    }
    
    int popMiddle() {
        if (q.size() == 2) {
            return -1;
        }
        int pos = (q.size() - 1) / 2;
        // 均摊 O(1)
        advance(it, pos - ptrpos);
        int ret = *it;
        it = q.erase(it);
        ptrpos = pos;
        return ret;
    }
    
    int popBack() {
        if (q.size() == 2) {
            return -1;
        }
        int ret = *prev(prev(q.end()));
        if (ptrpos == q.size() - 2) {
            it = q.erase(it);
        }
        else {
            q.erase(prev(prev(q.end())));
            // 指针指向哑尾节点
            if (ptrpos == q.size()) {
                --ptrpos;
            }
        }
        return ret;
    }
};

[sol2-Python3]
class LinkedListNode:
    def __init__(self, val: int):
        self.val = val
        self.prev = None
        self.succ = None

class LinkedList:
    def __init__(self):
        self.head = LinkedListNode(42)
        self.tail = LinkedListNode(42)
        self.head.succ = self.tail
        self.tail.prev = self.head
        self.size = 2
    
    def __str__(self):
        ret = list()
        cur = self.head
        while cur:
            ret.append(cur.val)
            cur = cur.succ
        return str(ret)

    def insert(self, it: LinkedListNode, val: int):
        self.size += 1
        node = LinkedListNode(val)
        it.prev.succ = node
        node.prev = it.prev
        it.prev = node
        node.succ = it
    
    def erase(self, it: LinkedListNode) -> LinkedListNode:
        self.size -= 1
        ret = it.succ
        it.prev.succ = it.succ
        it.succ.prev = it.prev
        return ret
    
    def advance(self, it: LinkedListNode, dt: int) -> LinkedListNode:
        if dt > 0:
            for _ in range(dt):
                it = it.succ
        elif dt < 0:
            for _ in range(-dt):
                it = it.prev
        return it
    
class FrontMiddleBackQueue:

    def __init__(self):
        self.q = LinkedList()
        self.it = self.q.head
        self.ptrpos = 0

    def pushFront(self, val: int) -> None:
        # 指针不指向哑头节点
        if self.ptrpos != 0:
            self.ptrpos += 1
        self.q.insert(self.q.head.succ, val)

    def pushMiddle(self, val: int) -> None:
        pos = self.q.size // 2
        # 均摊 O(1)
        self.it = self.q.advance(self.it, pos - self.ptrpos)
        self.q.insert(self.it, val)
        self.ptrpos = pos + 1
        
    def pushBack(self, val: int) -> None:
        # 指针指向哑尾节点
        if self.ptrpos == self.q.size - 1:
            self.ptrpos += 1
        self.q.insert(self.q.tail, val)

    def popFront(self) -> int:
        if self.q.size == 2:
            return -1
        ret = self.q.head.succ.val
        if self.ptrpos == 1:
            self.it = self.q.erase(self.it)
        else:
            self.q.erase(self.q.head.succ)
            # 指针不指向哑头节点
            if self.ptrpos != 0:
                self.ptrpos -= 1
        return ret

    def popMiddle(self) -> int:
        if self.q.size == 2:
            return -1
        pos = (self.q.size - 1) // 2
        # 均摊 O(1)
        self.it = self.q.advance(self.it, pos - self.ptrpos)
        ret = self.it.val
        self.it = self.q.erase(self.it)
        self.ptrpos = pos
        return ret

    def popBack(self) -> int:
        if self.q.size == 2:
            return -1
        ret = self.q.tail.prev.val
        if self.ptrpos == self.q.size - 2:
            self.it = self.q.erase(self.it)
        else:
            self.q.erase(self.q.tail.prev)
            # 指针指向哑尾节点
            if self.ptrpos == self.q.size:
                self.ptrpos -= 1
        return ret

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是操作次数。
空间复杂度：$O(n)$。

统计信息

通过次数	提交次数	AC比率
4692	8923	52.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途