一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底为1、2、3、4、5，也就是实现了栈中元素的逆序，请设计一个算法实现逆序栈的操作，但是只能用递归函数来实现，而不能用另外的数据结构。
看到这个题首先想到的就是新建一个栈，前一个栈每pop出一个元素，就将这个元素push进新栈中，这样很容易就实现了栈的逆序，但是题干中已经明确说明这么做是不行滴，必须用递归来做。事实上函数递归底层也是由系统维护的函数栈进行一系列的push和pop操作，只是这个栈不需要我们手动维护。
对于递归实现，解决该题需要分为如下两个步骤：
- 实现
getAndRemoveLastElement()用来抽出stack的栈底元素并返回 - 递归调用
reverseStackRecursively()函数，每次从栈中抽出底部元素，直到把栈抽空，再回溯反压入栈
代码如下
import java.util.Stack;
/**
* Created by wangshiyi on 17/7/26.
*
* 只用递归函数实现栈的逆序
*/
public class ReverseStack {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println("原始栈：" + stack); // [1, 2, 3, 4, 5]
reverseStackRecursively(stack);
System.out.println("逆序后的栈：" + stack); // [5, 4, 3, 2, 1]
}
/**
* 递归实现栈的逆序
*
* @param stack
*/
public static void reverseStackRecursively(Stack<Integer> stack) {
if (stack.isEmpty()) { // 已把栈抽空，开始回溯（反压）
return;
}
int i = getAndRemoveLastElement(stack);
reverseStackRecursively(stack);
stack.push(i); // 把抽出的元素反压入栈
}
/**
* 移除stack的栈底元素，其他元素不变
*
* @param stack
* @return 返回所移除的栈底元素
*/
public static int getAndRemoveLastElement(Stack<Integer> stack) {
int result = stack.pop();
if (stack.isEmpty()) { // 如果result为栈底元素，将栈底元素回溯
return result;
} else {
int last = getAndRemoveLastElement(stack); // 拿到栈底元素
stack.push(result); // push回之前pop的元素
return last;
}
}
}
牛客网上有该题的练习，只不过是用数组来描述栈的，对于实现getAndRemoveLastElement()反而更简单，传送门
另外此前做过一些有关栈的题目，用两个栈模拟实现一个队列、Pop Sequence、表达式求值，都是笔试面试中常见的问题。
