题目描述

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

问题解答

其实刚开始遇到这个问题时，我也是不知道该怎么做。但是，仔细思考后，其实发现要想实现这个过程，要经过两步。只要将这两步考虑清楚后，就会知道接下来该怎么做。
第一步 将栈底元素取出
第二步 将取出的元素依靠递归来逆序压入栈中
第一步，其实也是要递归才能实现。而这两步实现的过程，很容易联想到树的遍历。

代码

import java.util.Stack;

public class ReverseStack {
    private Stack<Integer> stack;

    public ReverseStack(){
        stack = new Stack<>();
    }

    public int getlast(){
        int last = stack.pop();
        if (stack.isEmpty())
            return last;
        int result = getlast();
        stack.push(last);
        return result;
    }

    public void reverse(){
        if (stack.isEmpty()){
            return;
        }
        int begin = getlast();
        reverse();
        stack.push(begin);
    }

    public static void main(String[] args){
        ReverseStack reverseStack = new ReverseStack();
        reverseStack.stack.push(1);
        reverseStack.stack.push(2);
        reverseStack.stack.push(3);
        while (!reverseStack.stack.isEmpty()){
            System.out.println(reverseStack.stack.pop());
        }
        reverseStack.stack.push(1);
        reverseStack.stack.push(2);
        reverseStack.stack.push(3);
        reverseStack.reverse();
        while (!reverseStack.stack.isEmpty()){
            System.out.println(reverseStack.stack.pop());
        }

    }
}