Implement Stack using Queues
构建一个后进先出的栈，唯一的存储结构是队列。队列只能在末尾添加元素、移除或读取队首元素，并报告自身大小。栈支持 push x（将 x 放到栈顶）、pop（移除并返回栈顶元素）、top（返回栈顶元素并保留它）和 empty（栈是否为空？）。
操作按顺序存放在 ops 中，其中 args[i] 保存 push 操作的值，其他情况下为 0。在一个空栈上依次执行这些操作，并为每个操作返回一个字符串：push 操作返回 "null"，pop 或 top 操作返回以文本形式表示的数字，empty 操作返回 "true" 或 "false"。
函数
- opsstring-array
- 这些操作，按运行顺序排列
- argsinteger-array
- 每次入栈的值，其他所有操作均为 0
- 返回值string-array
- 每次操作提供一个答案，以文本形式
约束条件
1 ≤ ops.length ≤ 1000args.length == ops.length- 每个
ops[i]都是push、pop、top或empty。 -109 ≤ args[i] ≤ 109表示执行 push 操作，args[i] == 0表示执行其他任何操作。- 只有当栈中至少有一个元素时，才会调用
pop和top。
示例
- 输入
- ops = ["push", "push", "top", "pop", "empty"]args = [1, 2, 0, 0, 0]
- 输出
- ["null", "null", "2", "2", "false"]
- 解释
- 2 最后放入，所以它在顶部：
top和pop都会返回"2"。1 仍然在里面，所以empty会返回"false"。
- 输入
- ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
- 输出
- ["null", "null", "7", "null", "9", "4", "true"]
- 解释
- 第一次弹出的是 7，也就是最新添加的项。随后 9 放到 4 的上面，并先于它离开，因此接下来弹出的是
"9"和"4"，最后栈为空。
- 输入
- ops = ["empty", "push", "top", "pop", "empty"]args = [0, -3, 0, 0, 0]
- 输出
- ["true", "null", "-3", "-3", "true"]
- 解释
- 栈一开始是空的，所以第一个答案是
"true"。负值的存储方式和其他值一样：top 和 pop 都返回"-3"，栈又变空了。
进阶
你能否保留一个队列，但把工作从 push 移到 pop，这样 push 的时间复杂度就是 O(1)？
提示
逐个打开提示，每个都会多透露一点。
队列会先返回最早加入的项，而栈会先返回最新加入的项。要让队列最先返回最新加入的项，它必须放在哪里？
将队首元素移除并添加到队尾，队列就会向后轮转一位。轮转一整圈后，队列会恢复原样；轮转不到一整圈时，队首的元素会移到其他元素后面。
将
x入队后，把其他size-1个元素逐个从队首移到队尾。现在x位于队首，较早入队的元素按从新到旧的顺序排列在它后面，因此，弹出和查看队首都只需操作队首。
题解
队列按从最早到最晚的顺序释放项目，栈则按从最新到最早的顺序释放项目，而队列永远不会让你看到队尾的项目。你唯一能用的操作是从队首出队，再从队尾入队，这样就能旋转队列。旋转队列，把最新的项目移到队首，在需要读取它时进行，或者在它到达后立即进行。
两个队列，弹出时取出最新的项
思路
按到达顺序将项目保存在队列 main 中，这样最新的项目就在队尾，而一次 push 就是一次入队。pop 会将除一个项目外的所有其他项目移到第二个队列 spare 中，直到只剩下一个项目：最新的项目。将它出队并交换两个队列，因为此时 spare 中保存着其余项目，且顺序与原来相同。top 会执行相同的遍历，但也会将最新的项目入队到 spare 中。
每次 pop 或 top 都会移动每个已存储的项目一次：执行 500 次 push，每次之后都执行一次 top，代价为 1 + 2 + ... + 500，约为 125,000 次移动。
算法
- 保留两个队列：
main中的元素按到达顺序排列，另一个spare为空。 - 对于
push x：将x入队到main。 - 对于
pop和top：将元素从main移到spare，直到只剩一个元素，然后将它出队作为答案。对于top，也将它入队到spare。交换这两个队列。 - 对于
empty：报告main是否为空。
from collections import deque
class QueueStack:
def __init__(self):
self.main = deque() # the oldest item at the front, the newest at the back
self.spare = deque() # empty between operations
def push(self, x):
self.main.append(x)
def _move_all_but_newest(self):
# Pass every item except the newest to the spare queue, in order.
while len(self.main) > 1:
self.spare.append(self.main.popleft())
def pop(self):
self._move_all_but_newest()
newest = self.main.popleft()
self.main, self.spare = self.spare, self.main
return newest
def top(self):
self._move_all_but_newest()
newest = self.main.popleft()
self.spare.append(newest) # top keeps the item
self.main, self.spare = self.spare, self.main
return newest
def empty(self):
return not self.main
def stackOps(ops, args):
stack = QueueStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
result.append(str(stack.pop()))
elif op == "top":
result.append(str(stack.top()))
else:
result.append("true" if stack.empty() else "false")
return result一个队列，每次推入后都轮转
思路
始终让队列保持栈的顺序，最新的元素在队首。这样，pop 就是出队，top 读取队首，也不需要第二个队列。新元素 x 加入队尾，排在较旧的元素后面，而这些元素已经按从新到旧的顺序排列。将队首元素出队，再入队到队尾，重复 size-1 次：每一步都会把一个较旧的元素移到 x 后面，同时保持它们的顺序，因此 x 最终会到达队首。
在第一个示例中，将 2 压入 [1] 得到 [1, 2]，旋转一次后得到 [2, 1]。向包含 k 个元素的队列执行压入操作，需要旋转 k 次，因此压入操作的时间复杂度为 O(n)，其余操作的时间复杂度为 O(1)。
算法
- 保留一个队列，队首始终是栈顶。
- 对于
push x：将x入队，然后重复size-1次：将队首元素出队，再将它入队。 - 对于
pop：将队首元素出队并返回。 - 对于
top：返回队首元素，但不将其移除。 - 对于
empty：报告队列是否为空。
from collections import deque
class QueueStack:
def __init__(self):
self.queue = deque() # the newest item is always at the front
def push(self, x):
self.queue.append(x)
# Rotate the older items behind x, so x comes out first.
for _ in range(len(self.queue) - 1):
self.queue.append(self.queue.popleft())
def pop(self):
return self.queue.popleft()
def top(self):
return self.queue[0]
def empty(self):
return not self.queue
def stackOps(ops, args):
stack = QueueStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
result.append(str(stack.pop()))
elif op == "top":
result.append(str(stack.top()))
else:
result.append("true" if stack.empty() else "false")
return result
易错点和边界情况
- 旋转
size次，而不是size-1次。一整圈后，x会留在队尾，所以接下来的弹出操作会返回最旧的元素。 - 在将
x入队之前旋转。较旧的元素会绕圈移动，而x仍会到达队尾。 - 使用两个队列时，没有将元素放回
top。这样，接下来的弹出操作会返回它下面的元素。 - 使用两个队列时，没有交换它们。元素留在
spare中，而empty会过早地返回"true"。 - 返回数字或布尔值。每个答案都是字符串，包括入栈时返回的
"null"。
常见问题3
用队列构建的栈的时间复杂度是多少？
使用一个在每次入队时轮转的队列，入队的时间复杂度是 O(n)，出队、查看队首和判空的时间复杂度是 O(1)。使用两个在每次出队时移动元素的队列，入队的时间复杂度是 O(1)，出队和查看队首的时间复杂度是 O(n)。无论哪种方式，每个元素只存储一次，因此空间复杂度是 O(n)。
为什么用队列实现的栈比用栈实现的队列慢？
把一个栈倒入另一个栈会颠倒顺序，所以倒一次就能把栈的顺序变成队列的顺序，而且每个元素一生只移动一次。在队列之间移动元素会保持它们的顺序，因此转移不会颠倒任何内容。这就是为什么这里的一次操作总是需要 O(n) 时间。
应该让 push 还是 pop 成为耗时操作？
让较少执行的操作承担开销。如果读取栈顶和弹出操作的频率远高于栈增长的频率，就在压入时进行轮换，这样每次读取都是 O(1)。如果多次压入之后才进行少量弹出，就让压入保持 O(1)，并在弹出时移动元素。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def stackOps(ops, args):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
ops = ["push", "push", "top", "pop", "empty"] args = [1, 2, 0, 0, 0]
预期输出
["null", "null", "2", "2", "false"]