Implement Queue Using Stacks

+10

用两个栈作为唯一的存储空间，构建一个先进先出的队列。栈只能在顶部添加元素、移除顶部元素、读取顶部元素，以及判断栈是否为空。队列支持 push x（在队尾添加 x）、pop（移除并返回队首元素）、peek（返回队首元素）和 empty（队列是否为空？）。

你会按顺序获得操作，存放在 ops 中，其中 args[i] 保存 push 操作的值，其他操作对应的值均为 0。在一个初始为空的队列上依次执行这些操作，并为每个操作返回一个字符串："null" 表示 push，pop 或 peek 返回的数字以文本形式表示，"true" 或 "false" 表示 empty 的结果。

函数

queueOps(ops: string-array, args: integer-array) → string-array

opsstring-array: 这些操作及其运行顺序
argsinteger-array: 每次执行 push 时的值，其他操作均为 0
返回值string-array: 每项操作对应一个答案，格式为文本

约束条件

1 ≤ ops.length ≤ 2000
args.length == ops.length
每个 ops[i] 都是 push、pop、peek 或 empty。
-10⁹ ≤ args[i] ≤ 10⁹ 表示 push 操作时的范围，其他操作则要求 args[i] == 0。
pop 和 peek 只有在队列中至少有一项时才会被调用。

示例

输入: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
输出: ["null", "null", "1", "1", "false"]
解释: 先推入 1，再推入 2，队首是 1，因此 peek 和 pop 都返回 "1"。2 仍在里面，所以 empty 返回 "false"。

输入: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
输出: ["null", "null", "4", "null", "7", "9", "true"]
解释: 第一次弹出的是 4，也就是最早进入的元素。7 还在等待时，9 加入了队列；因为 9 比 7 后加入，所以它在 7 之后弹出。此时队列为空，所以最后的答案是 "true"。

输入: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
输出: ["true", "null", "-3", "-3", "true"]
解释: 队列一开始是空的，所以第一个答案是 "true"。负数和其他数字一样存储：查看和弹出都会返回 "-3"，然后队列再次变为空。

进阶

怎样添加一个 back 操作，以 O(1) 的时间复杂度返回最新的项，同时不影响其他操作的均摊复杂度？

题解

栈按从最新到最旧的顺序返回元素，队列则按从最旧到最新的顺序返回元素。将一个栈倒入另一个栈会颠倒元素顺序，从而把栈的顺序变成队列的顺序。问题在于何时倒入：每次操作都倒入，成本都是 O(n)；而只在第二个栈为空时倒入，每个元素只会被转移一次。

每次压入时都重新排列整个栈

思路

将所有元素放在同一个栈 main 中，最旧的元素在顶部，这样 pop、peek 和 empty 都是单次栈操作。执行 push 时，必须将新元素放在底部：将所有元素移到 helper，把新元素推入空的 main，再将所有元素移回。经过两次反转，顺序就会恢复，新元素位于底部。

每次 push 都会将所有已存储的元素移动两次。连续推入 1,000 个元素的开销约为 2 × (0 + 1 + ... + 999)，接近一百万次移动。

算法

使用两个栈，main 的栈顶是最早加入的元素，另一个空栈是 helper。
对于 push x：将 main 中的所有元素逐个弹出并压入 helper，将 x 压入 main，然后将 helper 中的所有元素逐个弹出并压回 main。
对于 pop 和 peek：弹出或读取 main 的栈顶元素。
对于 empty：报告 main 是否为空。

class TwoStackQueue:
    def __init__(self):
        self.main = []    # the oldest item is on top
        self.helper = []

    def push(self, x):
        # Move everything aside, put x at the bottom, move everything back.
        while self.main:
            self.helper.append(self.main.pop())
        self.main.append(x)
        while self.helper:
            self.main.append(self.helper.pop())

    def pop(self):
        return self.main.pop()

    def peek(self):
        return self.main[-1]

    def empty(self):
        return not self.main


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

带延迟转移的输入栈和输出栈

思路

让两个栈各司其职。入栈操作将元素放入 inbox。出栈和查看栈顶操作从 outbox 读取，其中栈顶始终是最早放入的元素。当 outbox 为空时，将 inbox 中的所有元素倒入其中：最新的元素先离开 inbox 并落在底部，因此最早的元素会落在顶部。

只有当 outbox 为空时才倒入。只要其中还有元素，它们就比 inbox 中的任何元素都早，必须先离开。在第二个示例中，第一次出栈前会倒入 4 和 7，而 9 会留在 inbox 中，直到 7 离开。

每个值只会入栈到 inbox 一次、移到 outbox 一次，并出栈一次，因此 n 次操作的总耗时为 O(n)。

算法

保留两个空栈，inbox 和 outbox。
对于 push x：将 x 压入 inbox。
对于 pop 或 peek：如果 outbox 为空，就将 inbox 中的每个元素依次弹出并压入 outbox。然后弹出或读取 outbox 的栈顶元素。
对于 empty：报告两个栈是否都为空。

class TwoStackQueue:
    def __init__(self):
        self.inbox = []    # new items go on top
        self.outbox = []   # the oldest item is on top

    def push(self, x):
        self.inbox.append(x)

    def _refill(self):
        # Only when the outbox is empty: pouring the inbox over reverses it,
        # so the oldest item lands on top.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._refill()
        return self.outbox.pop()

    def peek(self):
        self._refill()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

易错点和边界情况

在 outbox 仍有元素时倒入。较新的元素会落在较旧元素上方，并先离开：在第二个示例中，9 会先于 7 出来。
仅根据 outbox 报告队列是否 empty。执行 push 后，元素会留在 inbox 中，因此队列并不为空。
执行 pop 时重新填充，但执行 peek 时不重新填充。在第一个示例中，执行两次 push 后再 peek，会发现 outbox 为空。
返回数字或布尔值。每个答案都是字符串，包括 push 时返回的 "null"。

常见问题3

用两个栈构建的队列的时间复杂度是多少？

push 的时间复杂度是 O(1)，pop 和 peek 的均摊时间复杂度是 O(1)。一次调用可能会把所有项倒到另一边，但这次倒入的开销由之前的 push 操作承担，因为每一项最多只会被倒一次。任意 n 次操作最多需要约 4n 次栈操作，空间复杂度为 O(n)。

为什么需要两个栈，而不是一个？

单个栈只能访问最新的元素，而队列需要最旧的元素。要取到底部的元素，就得移除它上面的所有元素，而这些元素需要一个地方暂存：第二个栈。把它们移过去会颠倒顺序，让最新的元素在前变成最旧的元素在前。

你能改用队列来实现栈吗？

可以，但没有摊还后的节省。使用一个队列时，每添加一个新元素，就从队首取出每个旧元素并将其添加到队尾，这样新元素最终就会位于队首。push 的时间复杂度变为 O(n)，pop 的时间复杂度为 O(1)。

def queueOps(ops, args):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

ops = ["push", "push", "peek", "pop", "empty"]
args = [1, 2, 0, 0, 0]

预期输出

["null", "null", "1", "1", "false"]