首页 > 代码库 > 栈和队列:用一个栈实现另一个栈的排序

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

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

 

 

 

 

 

将排序的栈记为 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名企算法与数据结构题目最优解, 左程云

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