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

题目：一个栈中元素的类型为整型，想从栈顶到栈底按从大到小的顺序排序，只允许申请一个栈，可以申请变量，但不能使用其他数据结构。

思路：

主要要保证辅助栈中从栈顶到栈底为从小到大的顺序。

需要排序栈为stackA，辅助栈为stackB

1）stack执行pop操作，弹出元素记为cur，如果cur小于等于栈B的栈顶元素，则直接压入

2）如果cur大于栈B的栈顶元素，则将栈B中所有元素逐一弹出，逐一压入栈A中，直到cur小于等于栈B的栈顶元素，再将cur压入help中。

过程：

1）A弹出4，压入B中

2）A弹出5，5>4，则把B中的4弹出压入A中。5压入到B中

3）A弹出4，2，1，都压入B中

 4）A弹出3，3>1，3>2，1和2从B中弹出压入A中，3<4，3进B中

 5）A弹出2，1直接进栈，此时A为空，执行下面while循环，把B中元素一一弹出压入A中，即可完成排序。

    public static void sortStackByStack(Stack<Integer> stackA){
        Stack<Integer> stackB = new Stack<>();
        while (!stackA.isEmpty()) {
            //栈A弹出
            int cur = stackA.pop();
            
            while (!stackB.isEmpty() && stackB.peek() < cur){
                stackA.push(stackB.pop());
            }
            stackB.push(cur);
        }
        while (!stackB.isEmpty()) {
            stackA.push(stackB.pop());
        }
    }

最后

以上就是合适灰狼为你收集整理的用一个栈实现另一个栈的排序的全部内容，希望文章能够帮你解决用一个栈实现另一个栈的排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。