链接：https://www.nowcoder.com/questionTerminal/ba7d7f5d1edf4d1690d66e12e951f6ea
来源：牛客网

题目：

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

给定一个栈Stack以及栈的大小top，请返回逆序后的栈。

测试样例：
[1,2,3,4,5],5
返回：[5,4,3,2,1]

思路：

一、

二、

要取得每次的栈底元素，分别为1,2,3,4,5，再压入5,4,3,2,1。如何取得栈底元素？递归pop，直至栈为空，返回递归最深的那个元素，其他的还要再压回去，否则栈就变了。注意栈底元素return之后就不压回去了，这样下次递归的时候才能取得倒数第二位的。

1. 第一个递归函数：取得栈底元素，并移除。

public static int getAndRemoveLastElement(Stack<Integer> stack) {
		int result = stack.pop();
		if(stack.isEmpty()) {
			return result;
		}else {
			int last = getAndRemoveLastElement(stack); //递归到找到最后一个元素，命名为last
			stack.push(result);   //其他名称仍叫result，要重新压入栈
			return last;     //只返回last一个元素
		}
	}

2. 第二个递归函数，就是题目最终要求的函数，reverse，其中调用上一个函数，获取栈底。

public static void reverse(Stack<Integer> stack) {
		if(stack.isEmpty()) {
			return;
		}
		int last = getAndRemoveLastElement(stack);  //取得当前栈底元素
		reverse(stack);     //递归，依次取出所有栈底元素
		stack.push(last);   //依次压入
	}

完整解答：

import java.util.Stack;
 
/** * 仅用递归函数和栈逆序一个栈：ReverseStack【2】 * * 【一个栈依次压入1、2、3，将栈转置，使栈顶到栈底依次是1、2、3，只能用递归函数，不能借用额外的数据结构包括栈】 * * 算法思想：两个递归函数（getAndRemoveBottom、reverse） * * @Author: zyx * @Date: 2019/4/25 16:24 * @Description: */
 
public class ReverseStack {
    public static int[] reverseStackRecursively(int[] stack, int top) {
        // write code here
        if (stack == null || stack.length == 0) {
            return null;
        }
        Stack<Integer> s = new Stack<Integer>();
        for (int i = 0; i <= top - 1; i++) {
            s.push(stack[i]);
        }
        reverse(s);
        for (int i = top - 1; i >= 0; i--) {
            stack[i] = s.pop();
        }
        return stack;
    }
 	
  /** * 每层递归取出栈底的元素并缓存到变量中，直到栈空； * * 然后逆向将每层变量压入栈，最后实现原栈数据的逆序。 * * @param stack */
    public static void reverse(Stack<Integer> stack) {
        if (stack.empty()) {
            return;
        }
        int i = getAndRemoveBottom(stack);// 依次返回1、2、3
        reverse(stack);
        stack.push(i);// 依次压入3、2、1
    }
 	
   /** * 返回并移除当前栈底元素（栈内元素<栈底>1、2、3<栈顶>变为2、3<栈顶>）. */ 	
    public static int getAndRemoveBottom(Stack<Integer> stack) {
        int result = stack.pop();
        if (stack.empty()) {
            return result;
        } else {
            int Bottom = getAndRemoveBottom(stack);
            stack.push(result);
            return Bottom;// 第一轮时，返回栈底元素1
        }
    }

    public static void main(String[] args){
	    int a[] = { 1, 2, 3, 4, 5 };
	    int b[] = new int[a.length];
	    b = reverseStackRecursively(a, a.length);
	    for(int i = 0;i < b.length; i++)
	    {
	        System.out.print(b[i] + " ");
	    }
	}
}

参考：

  1. 仅用递归函数和栈逆序一个栈
  2. 仅用递归函数，栈操作，来逆序一个栈