使用递归的方式反转栈

反转栈

最容易想到的是，利用额外的空间，比如数组来暂存数据，然后反序放入栈

递归也是可以的，可以使用递归调用产生的栈帧暂存数据，利用递归的回溯过程来反转栈

• 难点是：每次要去取出栈底的元素，这个与栈的常用的提供的pop()方法相悖，也就是getAndRomoveBottom()方法的具体实现。

代码

import java.util.Stack;

public class Main {
    private static Stack<Integer> stack;
    public static void main(String[] args) {
        stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack);
        reverseStack(stack); // 反转
        System.out.println(stack);
    }

    private static void reverseStack(Stack<Integer> stack){
        if(stack.isEmpty()){
            return;
        }else{
            reverse(stack);
        }
    }

    /**
     * stack 非空才能用这个函数
     * @param stack
     */
    private static void reverse(Stack<Integer> stack) {
        int data = getAndRomoveBottom(stack);
        System.out.println("栈帧暂存"+data);
        if(!stack.isEmpty()){
            reverse(stack);
        }
        System.out.println("回溯压栈"+data);
        stack.push(data);
    }

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