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

原题(来源牛客网)

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

解法

思想

申请一个辅助栈,应让该辅助栈成为一个单调栈,可以这样做:

原栈每次弹出一个元素,如果比辅助栈顶元素小(或辅助栈内为空)就直接压入辅助栈,如果比辅助栈顶元素大,则先保留该元素,将辅助栈内的比该元素小的元素压回原栈,再将该元素压入辅助栈,如此往复,直到辅助栈成为一个栈顶到栈底递增的栈,再将辅助栈内的元素压回原栈。

代码

class Solution {
    public void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<>();
        while(!stack.isEmpty()){
            int cur = stack.pop();
            while(!help.isEmpty()&&help.peek()<cur){
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while(!help.isEmpty()){
            stack.push(help.pop());
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e7%94%a8%e4%b8%80%e4%b8%aa%e6%a0%88%e5%ae%9e%e7%8e%b0%e5%8f%a6%e4%b8%80%e4%b8%aa%e6%a0%88%e7%9a%84%e6%8e%92%e5%ba%8f/

发表评论

电子邮件地址不会被公开。