双栈排序

请编写一个程序,按升序对栈进行排序(即最大元素位于栈顶),要求最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。
除了原栈外,需要借助一个栈help。用某种规则使得原栈的元素进入help栈,且help栈是排好序的而且栈顶最小,这样从help中搬运元素回原栈时,原栈才是排好序的,且栈顶最大。


整个过程中,想象两个栈是两支试管口对口横着放:


每次取出栈顶元素t,
情况1: 若help为空或t小于help栈顶,则压入help中
情况2:若help不为空且t大于help栈顶,则从help中弹出元素压入原栈内,直至到达情况1为止。然后将t压入help中。
情况1比较容易理解,要想栈排序使得栈顶最小,那么新元素小于栈顶,就可以直接压栈。
情况2中,为了达到1的情况,所以从help中弹出元素,直到发生情况1为止。整个过程有点像插入排序,更形象来说,像是算盘拨珠子的过程。
因为元素不能扔掉,所以help弹出来的都压入了原栈内。这些元素不必刻意处理,在后续过程会回到合适位置的。

处理4
处理3
处理5

CODE

    void StackSort(stack<int> &s){
        stack<int> help;
        while(!s.empty()){
            int t=s.top();
            s.pop();
            while(!help.empty() && help.top()>t){ //因为短路求值的特性,不会抛出异常
                int uu=help.top();
                help.pop();
                s.push(uu);
            }
            help.push(t);
        }
        s=help;
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目描述 Tom最近在研究一个有趣的排序问题。如图所示,通过2个栈S1和S2,Tom希望借助以下4种操作实现将输入...
    晨昏巷阅读 578评论 0 0
  • 请编写一个程序,按升序对栈进行排序(即最大元素位于栈顶),要求最多只能使用一个额外的栈存放临时数据,但不得将元素复...
    X_Y阅读 285评论 0 0
  • Lua 5.1 参考手册 by Roberto Ierusalimschy, Luiz Henrique de F...
    苏黎九歌阅读 13,952评论 0 38
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 173,928评论 25 709
  • 寻找体育场地 预约场地时间和人数
    刘雪玲0909阅读 370评论 0 0