【算法导论02】栈的逆序递归

思路

1. 将栈底元素取出，并删除栈底元素。
2. 然后将取出的栈底元素压入栈内。
3. 重复执行1,2

方法1（重点）：取出，并去除栈底元素

public static int getAndRemoveLastElement(Stack<Integer> stack){
	        int result = stack.pop();
	        if (stack.isEmpty()){
	            return result; //stack pop完之后，result就是最底的元素1，将1返回
	        }else {
	            int last = getAndRemoveLastElement(stack); //last = 1, result = 2
	            stack.push(result); // 根据递归的嵌套，一个个push入栈，stack:2 -->stack:32 --> stack: 432
	            return last;
	        }
	    }    

方法2：将取出的栈底元素，压入栈顶

	public static void reverse(Stack<Integer> stack){
        if (stack.isEmpty()){
            return;
        }
        int i = getAndRemoveLastElement(stack);// 取出最后一个元素，并压入栈的最上方
        // stack:1432 --> 2143 --> 3214 --> 4321
        reverse(stack);
        stack.push(i);
    }

主函数

public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        reverse(stack);
        while (!stack.isEmpty()){
            System.out.print(stack.pop()+" ");
        }
    }