首页 > 代码库 > 栈和队列:用一个栈实现另一个栈的排序
栈和队列:用一个栈实现另一个栈的排序
题目: 一个栈中的元素类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只允许申请一个栈。如何完成排序?
将排序的栈记为 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名企算法与数据结构题目最优解, 左程云
栈和队列:用一个栈实现另一个栈的排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。