你好，同学。很高兴看到你开始钻研基础数据结构的灵活运用。在 NOI（全国青少年信息学奥林匹克竞赛）中，虽然可以直接使用 STL，但理解数据结构的底层逻辑、通过限制条件实现特定功能是锻炼算法思维的必经之路。

下面我将这道 LeetCode 经典题改编为 NOI 风格的练习题，并为你提供辅导。

一、 题目描述：【模板】用栈实现队列 (Implement Queue using Stacks)

题目背景： 在计算机科学中，栈（Stack）和队列（Queue）是最基础的线性数据结构。栈遵循“后进先出”（LIFO），而队列遵循“先进先出”（FIFO）。现在要求你仅使用两个栈，模拟出一个标准的队列。

问题描述： 请设计一个名为 MyQueue 的数据结构，支持以下操作：

1. push x：将元素 $x$ 推到队列的末尾。
2. pop：从队列的开头移除并返回元素。
3. peek：返回队列开头的元素。
4. empty：返回队列是否为空。

输入格式： 第一行包含一个整数 $q$，表示操作次数。 接下来 $q$ 行，每行包含一个操作命令。

• push x：表示执行 push 操作。
• pop：表示执行 pop 操作。
• peek：表示执行 peek 操作。
• empty：表示执行 empty 操作。

输出格式： 对于每个 pop 和 peek 操作，输出对应的整数。 对于每个 empty 操作，输出 true 或 false。

数据范围：

• $1 \le q \le 100$
• $1 \le x \le 9$
• 假设所有操作都是有效的（例如，在调用 pop 或 peek 时，队列不为空）。
• 限制： 你只能使用标准的栈操作——即 push to top, peek/pop from top, size, 和 is empty 操作。

样例输入：

6
push 1
push 2
peek
pop
empty

样例输出：

1
1
false

二、 预备知识点

1. 栈（Stack）： 就像一叠盘子，最后放上去的先被拿走（LIFO）。
2. 队列（Queue）： 就像排队买饭，先排队的先买到（FIFO）。
3. 均摊复杂度分析（Amortized Analysis）： 某些单次操作虽然慢，但一系列操作下来的平均耗时很低。

三、 启发式思维引导（草稿纸上的推理过程）

现在，请拿出你的草稿纸，跟我一起画图分析：

1. 核心矛盾

• 栈： 输入 1, 2, 3 -> 弹出顺序 3, 2, 1（倒序）。
• 队列： 输入 1, 2, 3 -> 弹出顺序 1, 2, 3（正序）。
• 思考： 负负得正。如果我把数据在两个栈之间“倒腾”一遍，顺序会发生什么变化？

2. 角色分工

我们准备两个栈：s_in（负责进货）和 s_out（负责出货）。

3. 模拟步骤

假设我们要依次 push 1, push 2, 然后执行 pop。

• Step 1: push 1
  • s_in: [1] (栈顶)
  • s_out: []
• Step 2: push 2
  • s_in: [1, 2] (栈顶是2)
  • s_out: []
• Step 3: pop (需求是拿到1)
  • 此时 s_in 的栈顶是2，拿不到1。
  • 启发： 把 s_in 的所有东西倒入 s_out。
  • s_in 弹出 2 压入 s_out -> s_out: [2]
  • s_in 弹出 1 压入 s_out -> s_out: [2, 1] (栈顶是1)
  • Bingo! 现在的 s_out 栈顶就是我们要的队列首元素。

4. 优化思考：什么时候需要倒入？

每次 pop 都把 s_in 倒进 s_out 再倒回来吗？不需要。

• 只要 s_out 里还有元素，它的栈顶就一定是目前队列的最前端。
• 只有当 s_out 为空 时，才需要把 s_in 里的所有元素一次性挪过来。

四、 流程图 (Mermaid) 与算法伪代码

我们将逻辑拆解为两个部分。注意：在 NOI 比赛中，即便使用伪代码也要考虑边界情况。

graph TD
    A("push(x) 操作") --> B("直接压入 s_in 栈")
    
    C("pop() 或 peek() 操作") --> D{"s_out 是否为空?"}
    D -- "是 (Empty)" --> E("将 s_in 元素逐个弹出并压入 s_out")
    D -- "否 (Not Empty)" --> F("直接从 s_out 操作")
    E --> F
    F --> G("返回/弹出 s_out 的栈顶元素")

复杂度分析：

• 时间复杂度：
  • push: $O(1)$。
  • pop/peek: 每个元素最多被压入 s_in 一次，弹出 s_in 一次，压入 s_out 一次，弹出 s_out 一次。总共 4 次操作。对于 $N$ 个元素的序列，总时间 $O(N)$，均摊时间复杂度 为 $O(1)$。
• 空间复杂度： $O(N)$，需要存储所有元素。

五、 读题理解意的关键词

在做此类“模拟题”或“受限实现题”时，请务必圈出以下关键词：

1. “仅使用” (Only use)： 这是限制条件，意味着你不能直接使用 std::queue 或 std::vector 的随机访问功能。
2. “标准栈操作”： 提醒你只能用 push, pop, top, empty。
3. “均摊时间复杂度” (Amortized)： 这是高阶要求。如果你每次 pop 都进行搬运，虽然逻辑正确，但如果测试数据构造得比较极端，可能会导致 $O(N^2)$ 的总复杂度，在 NOI 中可能会被卡常或判 TLE。

教练提示： 在编写代码时，注意 peek() 和 pop() 的代码复用。你可以让 pop() 调用 peek() 来获取头部元素，这样可以减少逻辑冗余。祝你练习顺利！