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

【题目】

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

【思路】

需要排序的栈：stackData，用一个辅助栈：stackHelp

从stackData开始pop，记录为cur，那cur和stackHelp的栈顶比较，如果stackHelp的栈顶比cur小，就把stackHelp栈的数据一直往stackData压，知道条件不成立（stackHelp.peek()<cur）,前提肯定是stackHelp不为空，然后就把cur压入stackHelp中，模拟下就可以看到一个现象，stackHelp的栈底总是比较大，然后往上面变小，最后stackHelp变成了从栈顶到栈底，数据逐渐变大，最后把stackHelp的数据弹出压入stackData，就行了，就实现了stackData栈从顶到底按从大到小。

【代码】

package pers.keafmd.accumulate.codeinterviewguide.stacksorting;

import java.util.Stack;

/**
 * Keafmd
 *
 * @ClassName: StackSort
 * @Description: 用一个栈排序另外一个栈
 * @author: 牛哄哄的柯南
 * @date: 2022-06-24 16:06
 */
public class StackSort {

    public void sort(Stack<Integer> stackData){
        Stack<Integer> stackHelp = new Stack<>();
        while(!stackData.isEmpty()){
            int cur = stackData.pop();
            while(!stackHelp.isEmpty()&&stackHelp.peek()<cur){
                stackData.push(stackHelp.pop());
            }
            stackHelp.push(cur);
        }

        while(!stackHelp.isEmpty()){
            stackData.push(stackHelp.pop());
        }

    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(3);
        stack.push(6);
        stack.push(5);
        stack.push(7);
        stack.push(3);
        stack.push(1);
        stack.push(2);
        stack.push(4);

        System.out.print("排序前（栈顶到栈底）：");
        while (!stack.isEmpty()){
            System.out.print(stack.pop()+" ");
        }
        System.out.println();

        stack.push(3);
        stack.push(6);
        stack.push(5);
        stack.push(7);
        stack.push(3);
        stack.push(1);
        stack.push(2);
        stack.push(4);

        StackSort stackSort = new StackSort();
        stackSort.sort(stack);
        System.out.print("排序后（栈顶到栈底）：");
        while (!stack.isEmpty()){
            System.out.print(stack.pop()+" ");
        }
        System.out.println();

    }

}

效果：

排序前（栈顶到栈底）：4 2 1 3 7 5 6 3 
排序后（栈顶到栈底）：7 6 5 4 3 3 2 1 

Process finished with exit code 0