题目描述
将栈从底到顶按从大到小排序,只允许申请一个栈,除此之外,可以申请其他变量,但是不可以额外申请数据结构
思路
将要排序的栈记为stack,辅助栈为help,在stack上执行pop操作,用curr来存放每次从stack中pop出来的变量。
- 如果curr小于或等于help的栈顶,则将curr直接压入help
- 如果curr大于help栈顶,将help中的元素pop出来push进stack,直到curr小于help栈顶,将curr push到help中
直到stack中所有元素都到help中,再将help中元素push进stack,完成题目要求的排序
代码
public class StackSort {
public static void sortStackByStack(Stack<Integer> stack){
Stack<Integer> help = new Stack<>();
while (!stack.empty()){
int curr = stack.pop();
while (!help.empty()&&help.peek()>curr){
stack.push(help.pop());
}
help.push(curr);
}
while (!help.empty()){
stack.push(help.pop());
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(2);
stack.push(3);
stack.push(5);
stack.push(0);
stack.push(1);
stack.push(7);
stack.push(4);
sortStackByStack(stack);
for (int i : stack ) {
System.out.println(i);//输出代表从栈底到栈顶:7-0
}
}
}