数据结构

副标题 / 摘要 只有队列（FIFO）时，也能实现栈（LIFO）。本文展示单队列旋转法，并分析复杂度与边界。 目标读者 刷题与面试准备的开发者 需要理解数据结构转换的人 初中级算法学习者 背景 / 动机 栈的后进先出与队列的先进先出相反。 “旋转队列”可以把最新元素移动到队头，从而模拟栈顶。 核心概念 队列（FIFO）：先进先出 栈（LIFO）：后进先出 队列旋转：把新元素转到队首 实践指南 / 步骤 入栈：将元素入队 旋转队列：把队首依次出队再入队，直到新元素位于队首 出栈：直接出队 取栈顶：查看队首 可运行示例 from collections import deque class MyStack: def __init__(self): self.q = deque() def push(self, x: int) -> None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) -> int: return self.q.popleft() def top(self) -> int: return self.q[0] def empty(self) -> bool: return not self.q if __name__ == "__main__": s = MyStack() s.push(1) s.push(2) print(s.top()) print(s.pop()) print(s.empty()) 解释与原理 每次 push 后旋转队列，使新元素位于队首。 这样 pop 就相当于弹出“栈顶”。 ...

副标题 / 摘要 当系统只提供栈（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 的逆序输出。 ...