设计前中后队列

标签: 设计 队列 数组 链表 数据流

难度: Medium

请你设计一个队列，支持在前，中，后三个位置的 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 <= 109
  • 最多调用 1000 次 pushFront， pushMiddle， pushBack， popFront， popMiddle 和 popBack 。

Submission

运行时间: 76 ms

内存: 15.6 MB

from collections import deque


class FrontMiddleBackQueue:

    def __init__(self):
        self.front = deque()
        self.back = deque()

    def pushFront(self, val: int) -> None:
        self.front.appendleft(val)
        if len(self.front) > len(self.back) + 1:
            val = self.front.pop()
            self.back.appendleft(val)

    def pushMiddle(self, val: int) -> None:
        if len(self.front) > len(self.back):
            self.back.appendleft(self.front.pop())
        self.front.append(val)

    def pushBack(self, val: int) -> None:
        self.back.append(val)
        if len(self.back) > len(self.front):
            val = self.back.popleft()
            self.front.append(val)

    def popFront(self) -> int:
        if len(self.front) == 0:
            return -1
        ret = self.front.popleft()
        if len(self.front) < len(self.back):
            val = self.back.popleft()
            self.front.append(val)
        return ret

    def popMiddle(self) -> int:
        if len(self.front) == 0:
            return -1
        ret = self.front.pop()
        if len(self.front) < len(self.back):
            val = self.back.popleft()
            self.front.append(val)
        return ret

    def popBack(self) -> int:
        if len(self.front) == 0:
            return -1
        if len(self.back) == 0:
            return self.front.pop()
        ret = self.back.pop()
        if len(self.front) > len(self.back) + 1:
            val = self.front.pop()
            self.back.appendleft(val)
        return ret

# Your FrontMiddleBackQueue object will be instantiated and called as such:
# obj = FrontMiddleBackQueue()
# obj.pushFront(val)
# obj.pushMiddle(val)
# obj.pushBack(val)
# param_4 = obj.popFront()
# param_5 = obj.popMiddle()
# param_6 = obj.popBack()

Explain

此题解采用了两个双端队列（deque）来高效地支持队列的前中后操作。两个队列分别称为 front 和 back，其中 front 队列处理前半部分的元素，而 back 队列处理后半部分的元素。对于中间的操作，当 front 队列的长度比 back 队列长时，将会调整元素以保持平衡。此方法通过两个队列来协调元素，使得添加和删除操作都可以尽可能接近 O(1) 时间复杂度。

时间复杂度: O(1)

空间复杂度: O(n)

from collections import deque

class FrontMiddleBackQueue:

    def __init__(self):
        self.front = deque()  # 前半部分的双端队列
        self.back = deque()   # 后半部分的双端队列

    def pushFront(self, val: int) -> None:
        self.front.appendleft(val)  # 在前面添加元素
        # 平衡两个队列的长度
        if len(self.front) > len(self.back) + 1:
            val = self.front.pop()
            self.back.appendleft(val)

    def pushMiddle(self, val: int) -> None:
        # 确保 front 和 back 的长度适当
        if len(self.front) > len(self.back):
            self.back.appendleft(self.front.pop())
        self.front.append(val)  # 在中间添加元素

    def pushBack(self, val: int) -> None:
        self.back.append(val)  # 在后面添加元素
        # 平衡两个队列的长度
        if len(self.back) > len(self.front):
            val = self.back.popleft()
            self.front.append(val)

    def popFront(self) -> int:
        if len(self.front) == 0:
            return -1  # 队列为空时返回 -1
        ret = self.front.popleft()  # 从前面弹出元素
        # 平衡两个队列的长度
        if len(self.front) < len(self.back):
            val = self.back.popleft()
            self.front.append(val)
        return ret

    def popMiddle(self) -> int:
        if len(self.front) == 0:
            return -1  # 队列为空时返回 -1
        ret = self.front.pop()  # 从中间弹出元素
        # 平衡两个队列的长度
        if len(self.front) < len(self.back):
            val = self.back.popleft()
            self.front.append(val)
        return ret

    def popBack(self) -> int:
        if len(self.front) == 0:
            return -1  # 队列为空时返回 -1
        if len(self.back) == 0:
            return self.front.pop()  # 如果 back 为空，从 front 弹出
        ret = self.back.pop()  # 从后面弹出元素
        # 平衡两个队列的长度
        if len(self.front) > len(self.back) + 1:
            val = self.front.pop()
            self.back.appendleft(val)
        return ret

Explore

这种设计选择主要是为了保持队列的中间元素位置正确并简化操作。当元素从一个队列的末尾移动到另一个队列的开头时，我们能更容易地维持中间元素的位置，特别是在执行中间添加或删除操作时。这样的移动方式可以确保在任何操作后，两个队列都能迅速平衡，而不需要进行额外的元素重排。

在设计中，当队列元素总数为偶数时，中间位置的元素被视为靠近前半部分队列的最后一个元素。因此，pushMiddle 操作会将新元素添加到 front 队列的末尾。如果添加后 front 队列比 back 队列长，会将 front 的最后一个元素移动到 back 的开头。对于 popMiddle，操作总是从 front 队列的末尾移除元素，这样可以保持操作简单并确保两个队列的平衡。

在 pushBack 操作中，每当一个元素被添加到 back 队列后，算法会检查两个队列的长度。如果 back 队列的长度超过 front 队列，此时会从 back 队列的开头移除一个元素，并将其添加到 front 队列的末尾。这种平衡策略确保了两个队列长度的平衡，同时也维持了队列中元素的顺序。

当 front 队列为空而需要执行 popFront 操作时，最简单和直接的方法是直接从 back 队列中转移元素到 front 队列。这种做法不仅简化了操作过程，而且由于 back 队列的元素本来就是队列后半部分的元素，直接转移不会影响队列元素的整体顺序。在 popFront 需要执行时，通常意味着队列正在从一个非常不平衡的状态恢复平衡，因此，这种简单的转移操作是恢复平衡的最快方式。