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

题目描述

将栈从底到顶按从大到小排序,只允许申请一个栈,除此之外,可以申请其他变量,但是不可以额外申请数据结构

思路

将要排序的栈记为stack,辅助栈为help,在stack上执行pop操作,用curr来存放每次从stack中pop出来的变量。

  • 如果curr小于或等于help的栈顶,则将curr直接压入help
  • 如果curr大于help栈顶,将help中的元素pop出来push进stack,直到curr小于help栈顶,将curr push到help中

直到stack中所有元素都到help中,再将help中元素push进stack,完成题目要求的排序

代码

public class StackSort {

    public static void sortStackByStack(Stack<Integer> stack){
        Stack<Integer> help = new Stack<>();
        while (!stack.empty()){
            int curr = stack.pop();

            while (!help.empty()&&help.peek()>curr){
                stack.push(help.pop());
            }

            help.push(curr);
        }

        while (!help.empty()){
            stack.push(help.pop());
        }
    }

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

        sortStackByStack(stack);
        for (int i : stack   ) {
            System.out.println(i);//输出代表从栈底到栈顶:7-0  
        }
    }
}
上一篇:【微信小程序】图片压缩-纯质量压缩,非长宽裁剪压缩


下一篇:Linux测试环境搭建的学习建议