给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数
package algorithmbasic.class18;
import java.util.Stack;
//给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数
public class ReverseStackUsingRecursive {
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
//拿到栈底元素lowValue。
int lowValue = f(stack);
reverse(stack);
stack.push(lowValue);
}
//黑盒：给我一个栈，在保证栈中元素顺序不变的情况下，弹出栈底元素。
public static int f(Stack<Integer> stack) {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
}
int last = f(stack);
stack.push(result);
return last;
}
// -------------------- for test ------------------------
public static void main(String[] args) {
Stack<Integer> test = new Stack<Integer>();
test.push(1);
test.push(2);
test.push(3);
test.push(4);
test.push(5);
reverse(test);
while (!test.isEmpty()) {
System.out.println(test.pop());
}
}
}
reverse主函数：
假设我们有一个f方法：可以拿到栈底元素，并保证其他元素栈中顺序不变。
上来就调用f方法，拿到栈底元素 lowValue 。此时stack中栈底元素被拿走了。
这个递归不断的调用f方法，直到栈为空。即：在递的过程中，将栈底元素都收集好了，并且顺序由前往后正好是倒序。
然后归的时候，直接将栈底元素入栈即可。
f函数：
f函数的功能是：可以拿到栈底元素，并保证其他元素栈中顺序不变。
首先进入的是第一层，定义两个变量，一个是result：记录当前层的元素，一个是last：记录栈底元素。
将第一层的元素弹出来放到result中，result就是当前层的元素。此时的stack栈顶飞了一个，last = f(stack)，继续调用递归
来到第二层，然后继续相同的工作。
一直递归，直至来到栈为空，此时result中记录的就是栈底元素。返回此时的result。来到第二层，此时last接收到返回的栈底元素，并将last返回。因为此时栈是空地，所以，将result压入栈中。然后一致归。文章来源：https://www.toymoban.com/news/detail-508855.html
文章来源地址https://www.toymoban.com/news/detail-508855.html
到了这里，关于18.5：给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
