左神算法之单辅助栈排序算法

1. 题目

请编写一个程序，对一个栈里的整型数据，按升序进行排序（即排序前栈里的数据是无序的，排序后最大元素位于栈顶）。要求最多只能使用一个额外的栈存放临时数据，且不得将元素复制到别的数据结构中。

2. 解释

• 输入：一个无序的整数栈
• 输出：一个升序排列的栈（栈顶为最大元素）
• 限制条件：
  1. 只能使用一个额外的栈作为辅助空间
  2. 不能使用其他数据结构（如数组、队列等）
  3. 只能使用栈的标准操作（push, pop, peek, isEmpty）

3. 思路

核心算法：使用类似插入排序的思想，借助辅助栈实现排序

1. 初始化一个辅助栈 sortedStack（最终存放排序结果）
2. 当原栈不为空时：
   • 弹出原栈的栈顶元素 temp
   • 如果 sortedStack 不为空且 temp 比 sortedStack 的栈顶元素大，则将 sortedStack 的元素弹出并压回原栈，直到找到 temp 的正确位置 ，否则将元素temp放入到 sortedStack
   • 将 temp 压入 sortedStack
3. 最终 sortedStack 即为升序排列的栈

时间复杂度：O(n²)（最坏情况下需要反复移动元素）
空间复杂度：O(n)（仅使用一个额外栈）

4. 代码

import java.util.Stack;

public class StackSorter {
    public static Stack<Integer> sortStack(Stack<Integer> inputStack) {
        Stack<Integer> sortedStack = new Stack<>();
        while (!inputStack.isEmpty()) {
            int temp = inputStack.pop();
            // 将 sortedStack 中比 temp 大的元素移回 inputStack
            while (!sortedStack.isEmpty() && sortedStack.peek() > temp) {
                inputStack.push(sortedStack.pop());
            }
            sortedStack.push(temp);
        }
        return sortedStack;
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(1);
        stack.push(4);
        stack.push(2);
        stack.push(3);
        System.out.println("排序前: " + stack);
        Stack<Integer> sortedStack = sortStack(stack);
        System.out.println("排序后: " + sortedStack);
    }
}

输出示例：

排序前: [5, 1, 4, 2, 3]
排序后: [1, 2, 3, 4, 5]  // 栈顶为5（最大元素）

5. 总结

• 关键点：利用辅助栈实现类似插入排序的算法，通过比较和临时回退操作确保正确排序。
• 限制满足：仅使用一个额外栈，没有借助其他数据结构。
• 适用场景：适用于栈排序的经典问题，如面试题或算法练习。
• 优化思考：虽然时间复杂度为 O(n²)，但在栈操作限制下已是最优解法。

变体思考：

• 如果要降序排序（栈顶为最小元素），只需修改比较条件为 sortedStack.peek() < temp。
• 如果允许使用递归（隐式使用调用栈），可以尝试递归解法，但空间复杂度可能更高。