只使用递归实现栈的逆序操作

2017-06-23 20:36:02

解决该问题的核心其实是如果通过递归算法来获取栈底元素，也就是getLast函数的算法。

getLast算法实现：

首先获得stack的top元素，如果当前栈为空，则直接返回结果；

如果当前栈不为空，则递归的求解栈的栈底元素，之后再把当前的pop出来的元素压栈；

实现了getLast算法后，就可以很方便解决这个问题，每次得到栈底元素，然后递归的进行逆序即可。

    public void reverseStack(Stack<Integer> stack) {
        if (!stack.isEmpty()) {
            int tmp = getLast(stack);
            reverseStack(stack);
            stack.push(tmp);
        }
    }

    private int getLast(Stack<Integer> stack) {
        int top = stack.pop();
        if (stack.isEmpty()) return top;
        else {
            int res = getLast(stack);
            stack.push(top);
            return res;
        }
    }