用栈实现队列:双栈法的思路与实现
副标题 / 摘要 当系统只提供栈(LIFO)时,如何构建队列(FIFO)?本文用双栈法给出清晰实现与工程要点。 目标读者 刷题与面试准备的开发者 需要理解数据结构转换的人 希望掌握复杂度分析的初中级工程师 背景 / 动机 队列的先进先出与栈的后进先出相反。 双栈法通过“翻转顺序”实现队列语义,是经典的结构变换题。 核心概念 栈(LIFO):后进先出 队列(FIFO):先进先出 双栈翻转:把输入顺序倒置为输出顺序 实践指南 / 步骤 入队:压入 in 栈 出队/取队首:若 out 栈为空,将 in 栈全部弹出并压入 out 栈 从 out 栈弹出:即为队首 保持延迟搬运:只在 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 的逆序输出。 ...