用一个栈实现另一个栈的排序

【题目】 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

【解答】 将要排序的栈记为 stack，申请的辅助栈记为 help。在 stack 上执行 pop 操作，弹出的元素记为 cur。

• 如果 cur 小于或等于 help 的栈顶元素，则将 cur 直接压入 help；
• 如果 cur 大于 help 的栈顶元素，则将 help 的元素逐一弹出，逐一压入 stack，直到 cur小于或等于 help 的栈顶元素，再将 cur 压入 help。

一直执行以上操作，直到 stack 中的全部元素都压入到 help。最后将 help 中的所有元素逐一压入 stack，即完成排序。

/**
 * @program: interview
 * @description:
 * 【题目】
 * 一个栈中元素的类型为整型，现在想将该栈从顶到底按从的大到小顺序排序，只许申请一
 * 个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
 * @author: 
 * @create: 2023-03-25 22:00
 **/
public class SortStackByStack {

    public static void sortStackByStack(Stack<Integer> stack) {
        // 申请一个辅助栈空间
        Stack<Integer> help = new Stack<>();
        while (!stack.isEmpty()) {
            Integer cur = stack.pop();
            // 栈顶元素小于当前元素cur，就把help栈元素依次倒入stack栈中
            while (!help.isEmpty() && help.peek() < cur) {
                stack.push(help.pop());
            }
            // help栈倒空了或者help栈顶元素比cur大，就把cur元素放到help栈中。这样就达到了help栈元素越往栈底元素越大的效果
            help.push(cur);
        }
        // 最后，help从栈顶到栈底是由小到大的，只要把help元素依次倒进stack就能完成从栈顶到栈底由大到小的目的
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(2);
        stack.push(4);
        stack.push(1);
        stack.push(4);
        stack.push(9);
        sortStackByStack(stack);
//        Iterator<Integer> iterator = stack.iterator();
//        while (iterator.hasNext()) {
//            System.out.print(iterator.next() + " ");
//        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
}