你好，同学。欢迎来到 NOI 模拟赛后的专题强化训练。

今天我们要攻克的是数据结构基础中的经典转换问题：用队列实现栈。在竞赛中，灵活运用一种数据结构去模拟另一种数据结构的特性，是考查你对“线性表”本质理解程度的重要手段。

一、 预备知识点

在动手之前，请确保你已经熟练掌握以下内容：

1. 栈（Stack）的特性：后进先出（LIFO, Last In First Out）。
2. 队列（Queue）的特性：先进先出 (FIFO, First In First Out)。
3. C++ STL 标准库：std::queue 的基本操作：
   • push()：入队（队尾）
   • pop()：出队（队首）
   • front()：查看队首元素
   • empty()：判断是否为空
   • size()：获取元素个数

二、 NOI 竞赛题目描述

题目名称：用队列实现栈 (Implement Stack using Queues) 时间限制：1.0s 内存限制：256MB

【问题描述】 请你仅使用标准队列（std::queue）实现一个后进先出（LIFO）的栈，并支持普通栈的四种操作：push、top、pop 和 empty。

你只能使用队列的标准操作：

• push to back：将元素放入队列尾部。
• peek/pop from front：从队列头部查看或弹出元素。
• size：返回队列内的元素个数。
• is empty：返回队列是否为空。

【注意】：你所实现的“栈”必须在逻辑上符合栈的行为。

【输入格式】 输入包含若干行，每行包含一个操作命令。 第一行是一个整数 $N$，表示操作总数。 接下来的 $N$ 行，每行为以下格式之一：

1. push x：将元素 $x$ 压入栈顶。
2. pop：移除并返回栈顶元素。
3. top：返回栈顶元素。
4. empty：返回栈是否为空（true/false）。

【输出格式】 对于每个 pop、top、empty 操作，输出其对应的结果。

【样例输入】

6
push 1
push 2
top
pop
empty
top

【样例输出】

2
2
false
1

【数据规模与约定】

• $1 \le N \le 100$
• $1 \le x \le 9$
• 所有 pop 和 top 操作均合法。

三、 启发式思路引导：草稿纸上的推演

现在，请拿出你的草稿纸，我们一起画图思考。

1. 核心矛盾点

• 队列：像排队买票，先进去的先买到。
• 栈：像堆放书本，后放上去的先拿走。
• 思考：当我们把元素 1, 2, 3 依次 push 进队列，队列的状态是 [1, 2, 3]（左边是队首）。此时栈顶应该是 3，但队列只能从队首拿出 1。

2. 方案 A：双队列“移花接木”法

设两个队列 q1 和 q2。

• 思路：保持一个队列（比如 q1）始终以“栈”的顺序存储元素。
• 操作过程：
  1. 新来一个元素 x。
  2. 先把它放入 q2。
  3. 把 q1 里的所有元素逐个取出并 push 到 q2 的后面。
  4. 交换 q1 和 q2 的身份。
• 图形推导：
  • 初始：q1 为空。
  • push 1：q1 变 (1)。
  • push 2：2 进 q2 $\rightarrow$ q2 为 (2) $\rightarrow$ q1 的 1 挪到 q2 后面 $\rightarrow$ q2 为 (2, 1) $\rightarrow$ 交换给 q1。此时 q1 首元素是 2（栈顶）。

3. 方案 B：单队列“原地旋转”法（更优）

其实一个队列就够了！

• 思路：当你把一个元素 x 放入队列尾部时，它前面的 $n-1$ 个元素其实是“旧”的。
• 操作过程：
  1. 记录当前队列长度 n。
  2. 将 x 入队。
  3. 循环 n 次：将队首元素弹出，并立即重新入队。
• 图形推导：
  • 队列已有 (2, 1)，现在 push 3。
  • 队列变为 (2, 1, 3)。
  • 循环 2 次：
    • 第一次：弹出 2 入尾部 $\rightarrow$ (1, 3, 2)
    • 第二次：弹出 1 入尾部 $\rightarrow$ (3, 2, 1)
  • 看！此时队首变成了 3，完美符合栈的特性！

四、 复杂度分析与优化建议

• 时间复杂度：
  • push 操作：方案 B 需要旋转队列，复杂度为 $O(n)$。
  • pop/top/empty 操作：均为 $O(1)$。
  • NOI 考场策略：由于本题 $N$ 较小（100），$O(N^2)$ 的总复杂度完全可以通过。如果 push 频繁而 pop 较少，可以考虑哪种操作更适合承载复杂度。
• 空间复杂度：$O(n)$，仅需存储所有元素的空间。

五、 算法流程图（伪代码表达）

请参考以下逻辑结构编写 C++ 代码。注意在 Mermaid 语法中，我们使用特殊符号替代以防解析错误。

graph TD
    subgraph Push_Operation_Single_Queue
    A{Start Push x} --> B(Get current size n)
    B --> C(Queue push x)
    C --> D{Loop i from 1 to n}
    D -- Yes --> E(temp = Queue front)
    E --> F(Queue pop)
    F --> G(Queue push temp)
    G --> D
    D -- No --> H(End Push)
    end

    subgraph Pop_Operation
    I{Start Pop} --> J(result = Queue front)
    J --> K(Queue pop)
    K --> L(Return result)
    end

六、 读题关键词总结

在 NOI 竞赛中，遇到“模拟”类题目，请务必关注以下关键词：

1. “仅使用...” (Only use...)：限制了你的工具箱，考查能否用受限资源完成目标。
2. “标准操作” (Standard operations)：意味着你不能通过底层指针（如 deque 的迭代器）去作弊，必须严格遵守 FIFO/LIFO 原则。
3. “合法性” (Valid operations)：注意到“所有操作均合法”意味着你不需要在 pop 时判断 empty，但在工程实践中建议加上。

教练寄语：数据结构的本质是数据的组织形式。当你能用一种形式模拟另一种形式时，你才真正理解了它们的异同。去吧，尝试用 C++ STL 完成这道题！