如何在Python中仅用栈操作借助辅助栈实现栈排序？

现有代码的问题 #

• 内层循环逻辑错误：stack2.push(temp)被写在内层while循环体内，每弹出一个stack2的大于temp的元素就会重复插入一次temp，既会产生冗余数据也会导致排序逻辑完全混乱，正确操作应该是待所有大于temp的stack2元素全部转移完成后，再将temp压入stack2
• 栈资源浪费：传入的第三个辅助栈stack3全程未被使用，你当前的写法是尝试用双栈逻辑完成排序，没有利用到第三个栈的优化空间
• 返回值错误：即使修复双栈逻辑的bug，排序完成的元素全部存储在stack2中，返回stack1只会得到空栈

正确实现（三栈优化版） #

我们默认实现**pop元素时从小到大输出（即栈顶为最小元素，栈底为最大元素）**的排序逻辑，利用第三个栈暂存stack2中弹出的大于temp的元素，避免反复向stack1中压入已比较过的元素，减少冗余操作：

def sort(stack1, stack2, stack3):
    # stack1是待排序栈，stack2存有序元素，stack3做临时转移用
    while not stack1.empty():
        temp = stack1.pop()
        # 把stack2中所有比temp大的元素暂存到stack3
        while not stack2.empty() and stack2.peek() > temp:
            stack3.push(stack2.pop())
        # 插入temp到stack2的正确位置
        stack2.push(temp)
        # 把暂存在stack3的元素再放回stack2
        while not stack3.empty():
            stack2.push(stack3.pop())
    # 排序完成后所有有序元素都在stack2中，直接返回即可
    return stack2

逻辑说明 #

• 每次从待排序栈stack1取出栈顶元素temp
• 把有序栈stack2里所有比temp大的元素临时转移到stack3，保证stack2插入temp的位置是严格有序的
• 插入temp后把stack3暂存的元素放回stack2，stack2始终保持升序（栈顶最小）的状态
• 当stack1为空时，stack2就是完全排序后的栈

如果需要的是栈顶为最大元素的排序，只要把内层判断条件的stack2.peek() > temp改成stack2.peek() < temp即可。

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