如何用栈实现另一个栈的排序，来处理长尾词排序问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计325个文字，预计阅读时间需要2分钟。
一+题目+一个栈中元素的类型为整数，现在想将该栈从顶到底按从大到小的顺序排序，只允许申请一个栈。除此外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？+二
一 题目
一个栈中元素的类型为整数，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
二 要求
将要排序的栈记为stack，申请的辅助栈记为help。在stack上执行pop操作，弹出的元素记为cur。
1.如果cur小于或等于help的栈顶元素，则将cur直接压入help；
2.如果cur大于help的栈顶元素，则将help元素逐一弹出，逐一压入stack，直到cur小于或等于help栈顶元素，再将cur压入help。
一直执行上述操作，直到stack中全部元素都压入到help。最后将help中所有元素逐一压入stack，即完成排序。
三 代码实现
public static void sortStackByStack(Stack<Integer> stack){
Stack<Integer> help = new Stack<Integer>();
while(!stack.isEmpty()){
int cur = stack.pop();
while(!help.isEmpty() && help.peek() < cur){
stack.push(help.pop());
}
help.push(cur);
}
while(!help.isEmpty()){
stack.push(help.pop());
}
}
本文共计325个文字，预计阅读时间需要2分钟。
一+题目+一个栈中元素的类型为整数，现在想将该栈从顶到底按从大到小的顺序排序，只允许申请一个栈。除此外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？+二
一 题目
一个栈中元素的类型为整数，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
二 要求
将要排序的栈记为stack，申请的辅助栈记为help。在stack上执行pop操作，弹出的元素记为cur。
1.如果cur小于或等于help的栈顶元素，则将cur直接压入help；
2.如果cur大于help的栈顶元素，则将help元素逐一弹出，逐一压入stack，直到cur小于或等于help栈顶元素，再将cur压入help。
一直执行上述操作，直到stack中全部元素都压入到help。最后将help中所有元素逐一压入stack，即完成排序。
三 代码实现
public static void sortStackByStack(Stack<Integer> stack){
Stack<Integer> help = new Stack<Integer>();
while(!stack.isEmpty()){
int cur = stack.pop();
while(!help.isEmpty() && help.peek() < cur){
stack.push(help.pop());
}
help.push(cur);
}
while(!help.isEmpty()){
stack.push(help.pop());
}
}