副标题 / 摘要

当系统只提供栈（LIFO）时，如何构建队列（FIFO）？本文用双栈法给出清晰实现与工程要点。

目标读者

  • 刷题与面试准备的开发者
  • 需要理解数据结构转换的人
  • 希望掌握复杂度分析的初中级工程师

背景 / 动机

队列的先进先出与栈的后进先出相反。
双栈法通过“翻转顺序”实现队列语义，是经典的结构变换题。

核心概念

  • 栈（LIFO）：后进先出
  • 队列（FIFO）：先进先出
  • 双栈翻转：把输入顺序倒置为输出顺序

实践指南 / 步骤

  1. 入队：压入 in 栈
  2. 出队/取队首：若 out 栈为空，将 in 栈全部弹出并压入 out 栈
  3. 从 out 栈弹出：即为队首
  4. 保持延迟搬运：只在 out 为空时搬运

可运行示例

class MyQueue:
    def __init__(self):
        self._in = []
        self._out = []

    def push(self, x: int) -> None:
        self._in.append(x)

    def _move(self) -> None:
        if not self._out:
            while self._in:
                self._out.append(self._in.pop())

    def pop(self) -> int:
        self._move()
        return self._out.pop()

    def peek(self) -> int:
        self._move()
        return self._out[-1]

    def empty(self) -> bool:
        return not self._in and not self._out


if __name__ == "__main__":
    q = MyQueue()
    q.push(1)
    q.push(2)
    print(q.peek())
    print(q.pop())
    print(q.empty())

解释与原理

in 栈负责“输入顺序”，out 栈负责“输出顺序”。
当 out 为空时，把 in 全部倒入 out，就实现了 FIFO 的逆序输出。

常见问题与注意事项

  1. 每次出队都搬运会不会慢？
    是的，所以只在 out 为空时搬运。

  2. 复杂度是多少？
    均摊 O(1)，每个元素最多被搬运两次。

  3. 能否只用一个栈？
    可以，但需要递归或额外结构，复杂度更高。

最佳实践与建议

  • 采用“延迟搬运”策略
  • 对空队列操作做边界检查
  • 在多线程场景中加锁

小结 / 结论

双栈法通过顺序翻转实现队列语义，结构简单且均摊高效。
它是数据结构转换的经典范例。

参考与延伸阅读

  • CLRS 数据结构章节
  • LeetCode 232

元信息

  • 阅读时长：6~8 分钟
  • 标签：队列、栈、双栈
  • SEO 关键词：用栈实现队列, 双栈
  • 元描述：解释双栈法实现队列的思路与复杂度。

行动号召（CTA）

用你熟悉的语言实现双栈队列，并写一个最小测试用例验证它。