用递归函数和栈操作逆序栈

一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底为1、2、3、4、5，也就是实现了栈中元素的逆序，请设计一个算法实现逆序栈的操作，但是只能用递归函数来实现，而不能用另外的数据结构。

看到这个题首先想到的就是新建一个栈，前一个栈每pop出一个元素，就将这个元素push进新栈中，这样很容易就实现了栈的逆序，但是题干中已经明确说明这么做是不行滴，必须用递归来做。事实上函数递归底层也是由系统维护的函数栈进行一系列的push和pop操作，只是这个栈不需要我们手动维护。

对于递归实现，解决该题需要分为如下两个步骤：

1. 实现getAndRemoveLastElement()用来抽出stack的栈底元素并返回
2. 递归调用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、表达式求值，都是笔试面试中常见的问题。