求助：借助两个临时栈排序整数栈（禁止大数压小数）

核心思路 #

我们要把待排序的原栈元素，通过两个临时栈中转，最终得到一个完全有序的栈——全程所有栈（原栈、两个临时栈）都必须保持「小元素在下，大元素在上」的状态，绝对不能出现大数压在小数上面的情况。

具体操作步骤 #

假设三个栈分别是：input（待排序的原栈）、temp1（最终要变成有序栈的容器）、temp2（临时中转栈）。

1. 先把input的第一个元素弹出，直接压入temp1。
2. 循环处理input里剩下的每个元素：
   • 取出input的栈顶元素，记为current。
   • 把temp1中所有比current大的元素依次弹出，全部压入temp2（因为current比这些元素小，不能放在它们上面，先移去暂存，此时temp2的元素依然符合小下大上的规则）。
   • 把current压入temp1，这时候temp1里current的位置是对的，下面的元素都比它小。
   • 再把temp2里的所有元素依次弹出，压回temp1，此时temp1里current上面的元素都比它大，整个栈依然合规。
3. 等input空了，temp1就是排好序的栈（栈底最小，栈顶最大）。

示例演示（原栈栈底到栈顶为 [3,1,4,2]） #

• 第一步：把3压入temp1，此时temp1=[3]
• 处理元素1：
  • temp1里的3比1大，弹出3到temp2，temp2=[3]
  • 压入1到temp1，temp1=[1]
  • 把temp2的3压回temp1，temp1=[1,3]
• 处理元素4：
  • temp1里的所有元素都比4小，直接压入，temp1=[1,3,4]
• 处理元素2：
  • 弹出temp1里的4、3到temp2，temp2=[4,3]
  • 压入2到temp1，temp1=[1,2]
  • 把temp2的3、4压回temp1，temp1=[1,2,3,4]
    此时input为空，排序完成。

关键提醒 #

• 每一步操作后，都要检查所有栈的状态，确保没有大数在小数上面的情况，这是核心限制。
• temp2只是临时存放大元素的容器，用完一定要把元素移回temp1，别让它留着元素导致后续操作混乱。

内容的提问来源于stack exchange，提问作者Souvik