用一个栈实现另一个栈的排序
发布网友
发布时间：2022-04-23 19:21
共1个回答
热心网友
时间：2023-10-14 16:39
import java.util.Stack;
/**
* 一个栈元素的类型为整数，现在要想将该栈从顶到底按从大到小的顺序排列，只允许申请一个栈，除此之外，
* 可以申请一个变量，可以申请额外的变量，但是不能申请额外的数据结构，如何完成排序
* @author Think
* 思路：我们需要排序的栈为stack,然后我们申请一个栈记为help,在stack上面执行pop()操作，弹出的元素记为cur
* 如果cur小于或者等于栈顶元素，则将cur压入help,
* 如何cur大于help的栈顶元素，则将help的元素涿步弹出，涿一压入stack，直到cur小于或等于help的栈顶元素、再讲
* cur压入help
*/
public class SortStackByStack {
public static void main(String[] args) {
Stack<Integer> s=new Stack<Integer>();
s.push(3);
s.push(2);
s.push(5);
s.push(4);
s.push(1);
s=sortStackbyStack(s);
while(!s.isEmpty()){
System.out.println(s.pop());
}
}
public static Stack<Integer> sortStackbyStack(Stack<Integer> stack){
Stack<Integer> help=new Stack<Integer>();
while(!stack.isEmpty()){
int cur=stack.pop();
while(!help.isEmpty() && cur>help.peek()){
stack.push(help.pop());
}
// help.push(stack.pop()); 这个地方要是写了就pop了2次，显然不正确
help.push(cur);
}
while(!help.isEmpty()){
stack.push(help.pop());
}
return stack;
}
/**
* 如果我采用下面的方法，cur<=help.peek(); 然后去执行help.pop();很明显help是空的，会报错
* 所以我们应该采取相反的思路去解决这个问题，cur>help.peek()，这个时候有确保help里面没有数据的话
* 会把stack的pop();出来的数据压倒help里面，下次注意
*/
// public static Stack<Integer> sortStackbyStack1(Stack<Integer> stack){
// Stack<Integer> help=new Stack<Integer>();
// while(!stack.isEmpty()){
// int cur=stack.pop();
// while(!help.isEmpty() && cur<=help.peek()){
// help.push(cur);
// }
//// help.push(stack.pop()); 这个地方要是写了就pop了2次，显然不正确
// stack.push(help.pop());
// }
// while(!help.isEmpty()){
// stack.push(help.pop());
// }
// return stack;
// }
}追问我只是想知道我写的哪里错了。。
