学习目标
- 用输入栈和一个辅助栈对整数排序。
- 通过回退较大的元素维护辅助栈的顺序，允许重复和负数。
- 分析嵌套移动导致的
O(n²)最坏时间。
前置知识与环境
建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。
任务
按给定顺序逐个压入输入栈，因此最后一个输入元素最先从输入栈弹出。只能借助一个辅助栈移动元素，不使用排序库或其他存储全部元素的容器。最终从输入栈栈顶依次弹出时，数值应非递减。例如输入 3 1 2，输出 1 2 3。
输入格式
第一行 n；第二行 n 个整数，按给定顺序依次入栈。
输出格式
输出从小到大的排序结果，各元素以空格分隔，末尾换行。n=0 输出空行；相等元素保留原数量，无稳定性要求。
数据范围与限制
- 除题面另有说明外整数使用 64 位有符号范围。
0 <= n <= 5000；仅允许使用输入栈和一个辅助栈完成排序，栈排序最坏时间为O(n^2)，辅助空间为O(n)。- 标准输出只保留题目要求的结果；调试信息写入标准错误。
- 目标算法使用一个辅助栈完成排序，最坏时间
O(n^2)，辅助空间不超过O(n)。
边界与验收重点
- 空栈、已升序、逆序、重复值和负数。
- 辅助栈栈顶若阻碍当前值入栈，应把元素退回输入栈再比较。
- 只输出值的升序，不能丢失重复值。
如何验证
powershell
make doctor
make run
make score未安装 Make 时，在仓库根目录运行：
powershell
pnpm lab:validate -- labs/chapter-02/exercise/E-02-19-stack-sorting
pnpm lab:run -- labs/chapter-02/exercise/E-02-19-stack-sorting
pnpm lab:score -- labs/chapter-02/exercise/E-02-19-stack-sorting思考与复盘
- 为什么结束前要把辅助栈元素移回输入栈？
- 相等值能否直接加入辅助栈？
思考题参考
- 辅助栈的栈顶较大，移回输入栈后其栈顶才是最小值，符合升序弹出合同。
- 可以；排序只要求非递减，并不要求相等元素稳定排序。
题解
点击查看题解
思路与不变量
输入栈先按输入顺序压入，最后一个输入值先被处理。辅助栈保持从栈底到栈顶非递减；处理当前值时，只要辅助栈顶大于它，就把这些较大值退回输入栈，给当前值让出位置。
算法步骤
- 将输入序列压入输入栈；
- 从输入栈取出一个当前值；
- 将辅助栈中所有大于当前值的元素移回输入栈，再把当前值压入辅助栈；
- 输入栈为空后，将辅助栈全部移回输入栈；
- 此时输入栈顶是最小值，依次弹出即可得到非递减序列。
正确性说明
每次把当前值放入辅助栈前，辅助栈顶不大于它，因此辅助栈始终有序。所有较大元素暂时移回输入栈后最终仍会被处理，不会丢失。最后反向搬回使最小值位于输入栈顶，所以弹出顺序为升序。
复杂度分析
- 时间复杂度：最坏
O(n²)，元素可能在两栈之间反复移动； - 额外空间：
O(n)，只使用输入栈和一个辅助栈。
边界注意
- 相等元素可以直接压入辅助栈，题目只要求非递减；
n=0时不执行搬运，输出空行；- 不能使用排序库或第三个容器，否则违反“仅用辅助栈”的限制。