栈与队列的相互模拟
用两个栈实现队列，再用两个队列实现栈，并解释每种方法的摊销成本。
栈与队列的相互模拟 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
为什么要用一种结构模拟另一种结构
用两个栈实现队列以及用两个队列实现栈，是经典的设计类面试题。它们考查您对这两种数据结构不变量的理解，以及您使用一种结构的基本操作来维护另一种结构保证的能力。面试官还会借此引出均摊复杂度的讨论。
关键洞察是：栈遵循 LIFO，队列遵循 FIFO。要在两者之间进行转换，必须反转顺序——将一个栈反转到另一个栈后，会得到原始的插入顺序，也就是 FIFO 顺序。
使用两个栈实现队列（延迟方式）
延迟方式是：使用 inbox 栈处理压入操作，使用 outbox 栈处理弹出操作。调用出队操作时，如果 outbox 为空，就将 inbox 中的所有元素转移到 outbox 中——这种反转会恢复 FIFO 顺序。如果 outbox 不为空，则直接从中弹出元素。转移操作只会延迟执行，从而将 O(n) 的转移成本均摊到多次操作中。
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def _transfer(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._transfer()
return self.outbox.pop()
def peek(self):
self._transfer()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.pop()) # 2
q.push(4)
print(q.pop()) # 3使用栈实现队列的 O(1) 均摊分析
每个元素从 inbox 转移到 outbox 的次数最多为一次。从 outbox 弹出元素的复杂度为 O(1)，并且只在 outbox 为空时进行转移，因此 n 次压入和 n 次弹出的总工作量最多为 2n 次栈操作——总复杂度为 O(n)，每次操作的均摊复杂度为 O(1)。这意味着单次操作在最坏情况下可能达到 O(n)，但平均复杂度为 O(1)。
# Trace transfer costs for 10 push/pop interleaved
class TrackedQueue:
def __init__(self):
self.inbox = []; self.outbox = []; self.transfers = 0
def push(self, x): self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
self.transfers += 1
return self.outbox.pop()
q = TrackedQueue()
for i in range(5):
q.push(i)
for _ in range(5):
q.pop()
q.push(10); q.push(20)
q.pop()
print('Total transfer operations:', q.transfers) # at most n使用两个队列实现栈（延迟弹出）
由于队列遵循 FIFO，使用两个队列实现栈不太自然。延迟弹出方式是：保留一个主队列和一个临时队列。在 push 操作中，将元素加入主队列（O(1)）。在 pop 或 peek 操作中，将除最后一个元素之外的所有元素移入临时队列，保存最后一个元素，然后交换两个队列。每次 pop 的复杂度为 O(n)，但每次 push 的复杂度为 O(1)。
from collections import deque
class MyStack:
def __init__(self):
self.main = deque()
self.temp = deque()
def push(self, x):
self.main.append(x) # O(1)
def pop(self):
# Move all but last element to temp
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main.popleft() # the 'top'
self.main, self.temp = self.temp, self.main # swap
return val
def top(self):
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main[0]
self.temp.append(self.main.popleft())
self.main, self.temp = self.temp, self.main
return val
def empty(self):
return len(self.main) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.pop()) # 2使用一个队列实现栈（压入时旋转）
一种简洁的单队列实现方式是：执行 push 时，先将新元素加入队列，然后旋转队列，使新元素位于前端。旋转意味着将压入操作之前已经存在的所有元素出队，再重新加入队列。这样，pop 和 peek 的复杂度就是 O(1)（只需从前端出队或查看前端元素）。push 的复杂度为 O(n)，这与双队列版本的取舍相反。
from collections import deque
class MyStackOneQueue:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
# Rotate: move all preceding elements behind x
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStackOneQueue()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2取舍总结：应选择哪种变体
对于用两个栈实现队列：push 为 O(1)，pop/peek 的均摊复杂度为 O(1)——当弹出操作频繁时优先选择它。对于用两个队列实现栈：push 为 O(1)，pop 为 O(n)——当压入操作远多于弹出操作时优先选择它。对于用一个队列实现栈：push 为 O(n)，pop 为 O(1)——当弹出操作占主导时优先选择它。在面试中请明确说明这些取舍，以展示您考虑的不只是“能否运行”。
print('Queue from 2 stacks: push O(1), pop O(1) amortised')
print('Stack from 2 queues: push O(1), pop O(n)')
print('Stack from 1 queue: push O(n), pop O(1)')为什么反转可以恢复 FIFO
当元素 1、2、3 被压入一个栈（输入栈）时，它们从栈底到栈顶依次为 1、2、3。将所有元素弹出并压入第二个栈（输出栈）后，顺序会反转：输出栈的栈底是 3，栈顶是 1。从输出栈弹出元素时，顺序为 1、2、3——这正好是 FIFO 的插入顺序。这就是为什么恰好两次反转（使用两个栈）可以恢复 FIFO，而单个栈只能产生 LIFO 顺序。
# Demonstrate double-reversal = FIFO
inbox = [1, 2, 3] # pushed in this order
outbox = []
while inbox:
outbox.append(inbox.pop())
print('outbox (one reversal):', outbox) # [3, 2, 1] top-to-bottom
# Pop from outbox gives FIFO
result = []
while outbox:
result.append(outbox.pop())
print('dequeued:', result) # [1, 2, 3] — FIFO!LeetCode 232：使用栈实现队列
LeetCode 232 是直接的“用两个栈实现队列”问题。预期解法是延迟的输出栈转移方案。在面试中，请说明每个元素从输入栈移动到输出栈的次数最多为一次，因此所有操作的均摊复杂度为 O(1)。还要说明，单次 pop 调用在最坏情况下可能是 O(n)（当输出栈为空时），但 n 次操作的平均复杂度为 O(1)。
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def pop(self):
self.peek() # ensure outbox is populated
return self.outbox.pop()
def peek(self):
if not self.outbox:
while self.inbox: # transfer lazily
self.outbox.append(self.inbox.pop())
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
# Simulation
q = MyQueue()
q.push(1); q.push(2)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.empty()) # FalseLeetCode 225：使用队列实现栈
LeetCode 225 是“用队列实现栈”问题。使用一个队列并在 push 时旋转，是最简洁的解法。压入元素 x 后，通过将队列中原本已有的所有元素移到 x 的后面来旋转队列。每次 push 的成本为 O(n)，但 top 和 pop 的复杂度为 O(1)。请说明这种取舍，并确认它符合约束条件（例如压入操作较少或弹出操作较多的工作负载）。
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x): # O(n)
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self): # O(1)
return self.q.popleft()
def top(self): # O(1)
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2
print(s.empty()) # False在一个数组中扩展为三个栈
一个相关的设计挑战是：使用单个数组实现三个栈。一种方法是将数组划分为三个大小相等的固定区域。更灵活的方法是使用带指针的交错存储，让每个栈从自己的区域增长，并在边界相撞时进行复制。这会考查动态数组管理能力，也是高级职位面试中常见的问题。固定区域方法更简单，但如果各个栈的增长不均匀，就会浪费空间。
class ThreeStacks:
def __init__(self, size):
self.data = [0] * (3 * size)
self.tops = [-1, -1, -1] # relative top of each stack
self.size = size
def push(self, stack_num, val):
self.tops[stack_num] += 1
if self.tops[stack_num] >= self.size:
raise OverflowError('stack full')
self.data[stack_num * self.size + self.tops[stack_num]] = val
def pop(self, stack_num):
if self.tops[stack_num] < 0:
raise IndexError('stack empty')
val = self.data[stack_num * self.size + self.tops[stack_num]]
self.tops[stack_num] -= 1
return val
ts = ThreeStacks(5)
ts.push(0, 10); ts.push(1, 20); ts.push(2, 30)
print(ts.pop(0), ts.pop(1), ts.pop(2)) # 10 20 30要点：模拟模式
相互模拟问题揭示了一个更广泛的原则：只要有足够的中间缓冲和逆序操作，就可以用一种数据结构构建另一种数据结构。模拟的成本取决于您优化的是哪些操作——您总能让 push 或 pop 达到 O(1)，但要让两者都达到 O(1)，则需要使用摊销分析或多个辅助结构。
在面试中，请始终询问：“哪些操作更频繁？”这有助于指导您选择实现变体，也能体现您对操作需求的高级思考。
快速检查
请测试您对本课中“数据结构与算法——编程面试准备”概念的理解。
课程回顾
在本课中，您学到了：由两个栈构成的队列通过将元素延迟从输入栈转移到输出栈，实现摊销 O(1) 的 pop；由一个队列构成的栈通过每次 push 时旋转队列，实现 O(1) 的 pop（push 为 O(n)）；以及应根据使用模式决定将哪个操作设为 O(1)。接下来，我们将探索哈希映射的内部机制和冲突处理。
常见问题解答
「栈与队列的相互模拟」课时是免费的吗？
是的 — 「栈与队列的相互模拟」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「栈与队列的相互模拟」这节课中我会学到什么？
用两个栈实现队列，再用两个队列实现栈，并解释每种方法的摊销成本。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「栈与队列的相互模拟」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。