用一个栈实现另一个栈的排序
【摘要】 用一个栈实现另一个栈的排序
用一个栈实现另一个栈的排序
【题目】
一个栈中元素的类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只许申请一个栈。除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序?
【思路】
需要排序的栈:stackData,用一个辅助栈:stackHelp
从stackData开始pop,记录为cur,那cur和stackHelp的栈顶比较,如果stackHelp的栈顶比cur小,就把stackHelp栈的数据一直往stackData压,知道条件不成立(stackHelp.peek()<cur),前提肯定是stackHelp不为空,然后就把cur压入stackHelp中,模拟下就可以看到一个现象,stackHelp的栈底总是比较大,然后往上面变小,最后stackHelp变成了从栈顶到栈底,数据逐渐变大,最后把stackHelp的数据弹出压入stackData,就行了,就实现了stackData栈从顶到底按从大到小。
【代码】
package pers.keafmd.accumulate.codeinterviewguide.stacksorting;
import java.util.Stack;
/**
* Keafmd
*
* @ClassName: StackSort
* @Description: 用一个栈排序另外一个栈
* @author: 牛哄哄的柯南
* @date: 2022-06-24 16:06
*/
public class StackSort {
public void sort(Stack<Integer> stackData){
Stack<Integer> stackHelp = new Stack<>();
while(!stackData.isEmpty()){
int cur = stackData.pop();
while(!stackHelp.isEmpty()&&stackHelp.peek()<cur){
stackData.push(stackHelp.pop());
}
stackHelp.push(cur);
}
while(!stackHelp.isEmpty()){
stackData.push(stackHelp.pop());
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(3);
stack.push(6);
stack.push(5);
stack.push(7);
stack.push(3);
stack.push(1);
stack.push(2);
stack.push(4);
System.out.print("排序前(栈顶到栈底):");
while (!stack.isEmpty()){
System.out.print(stack.pop()+" ");
}
System.out.println();
stack.push(3);
stack.push(6);
stack.push(5);
stack.push(7);
stack.push(3);
stack.push(1);
stack.push(2);
stack.push(4);
StackSort stackSort = new StackSort();
stackSort.sort(stack);
System.out.print("排序后(栈顶到栈底):");
while (!stack.isEmpty()){
System.out.print(stack.pop()+" ");
}
System.out.println();
}
}
效果:
排序前(栈顶到栈底):4 2 1 3 7 5 6 3
排序后(栈顶到栈底):7 6 5 4 3 3 2 1
Process finished with exit code 0
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)