给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数

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压入栈中。然后一致归。