首页 > 编程语言 > 详细

栈和队列:用一个栈实现另一个栈的排序

时间:2017-04-02 12:29:06      阅读:225      评论:0      收藏:0      [点我收藏+]

题目: 一个栈中的元素类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只允许申请一个栈。如何完成排序?

 

 

 

 

 

将排序的栈记为 stack,辅助栈记为 help,在stack上执行pop操纵,弹出的元素为 tmp

1. 如果 tmp 大于或等于 help 的栈顶元素或 help 为空,则将 tmp 压入 help;

2. 如果 tmp 小于 help 的栈顶则将 help 的元素弹出,逐一压入 stack,直到 tmp 大于或等于 help 的栈顶元素,再将 tmp 压入 help;

一直执行到 stack 中所有元素都压入 help 即完成排序。

 

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

        return help;
    }

 

参考资料:程序员代码面试指南IT名企算法与数据结构题目最优解, 左程云

栈和队列:用一个栈实现另一个栈的排序

原文:http://www.cnblogs.com/2015110615L/p/6658686.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!