学习目标
- 借助栈反转队列前
k个元素，同时保留后缀相对顺序。 - 处理
k=0、k=1和k=n，明确输入顺序为队头到队尾。 - 证明每个元素只经历常数次入队/出队。
前置知识与环境
建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。
任务
队列最初从队头到队尾依次为输入的 a[0]..a[n-1]。仅将前 k 个元素逆序，后 n-k 个元素原顺序接在后面。例如 [1,2,3,4,5] 且 k=3 时，输出 [3,2,1,4,5]。
输入格式
第一行两个整数 n k；第二行从队头到队尾给出 n 个 64 位有符号整数。保证 0 <= k <= n <= 200000；n=0 时第二行为空。
输出格式
输出操作后从队头到队尾的整个队列，元素以空格分隔，末尾换行；n=0 输出空行。
数据范围与限制
- 输入规模不超过
200000，除题面另有说明外整数使用 64 位有符号范围。 - 标准输出只保留题目要求的结果；调试信息写入标准错误。
- 目标算法应为线性或摊还线性时间，辅助空间不超过
O(n)。
边界与验收重点
k=0或k=1时队列不变；k=n时整个队列逆序。- 前缀使用 LIFO 反转后，原后缀仍需保持 FIFO 顺序。
- 重复值不能代替位置判断，输入顺序才决定答案。
如何验证
powershell
make doctor
make run
make score未安装 Make 时，在仓库根目录运行：
powershell
pnpm lab:validate -- labs/chapter-02/exercise/E-02-18-reverse-first-k-queue
pnpm lab:run -- labs/chapter-02/exercise/E-02-18-reverse-first-k-queue
pnpm lab:score -- labs/chapter-02/exercise/E-02-18-reverse-first-k-queue思考与复盘
- 为什么反转前缀后仍要把原后缀轮转到队尾？
k=0时应有多少次栈的压入与弹出？
思考题参考
- 前缀逆序元素是追加在队尾的，原后缀还在前面；轮转后才能得到正确顺序。
- 零次；结果与原队列完全相同。
题解
点击查看题解
思路与不变量
先把队头前 k 个元素依次压入栈，再将栈顶元素依次入队，就能把这段前缀反转。此时原后缀仍在队头，前缀反转结果在队尾；再把原后缀轮转到队尾，整体顺序就变为“反转前缀 + 原后缀”。
算法步骤
- 读入全部元素建立队列；
- 弹出前
k个元素并压栈； - 清空栈，将元素按栈顶到栈底顺序追加到队尾；
- 将当前队头的原后缀元素轮转到队尾；
- 依次输出队列。
正确性说明
栈的后进先出性质使前 k 个元素逆序追加。第 4 步恰好跳过这 k 个新追加元素，只轮转原来的 n-k 个后缀，因此后缀相对顺序保持不变，最终得到题目要求的排列。
复杂度分析
- 时间复杂度：
O(n)，每个元素只经历常数次队列或栈操作； - 额外空间：
O(n)，队列和辅助栈均为线性规模。
边界注意
k=0时栈为空，轮转全部n个元素后队列仍不变；k=1不改变前缀；k=n时没有后缀需要轮转；- 输出顺序由元素位置决定，重复值不能用来替代位置推理。