前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神的书让我对算法有了新的感悟认识！

问题介绍

原问题
使用递归函数和栈的操作实现一个能够逆序栈的工具
如：
入栈：
98765
逆序后：
56789

解决方案

1、首先知道递归方式可以将栈值全部都弹出，但是没有办法逆序push进来
2、但是一次递归可以将任何一个值一直返回到第一层，所以想到抽取最底层
3、循环抽取最底层然后再push进去，但是只有一个栈怎么办？
4、再次递归代替循环抽取底层
解决思路，具体逻辑为：
1、通过递归的方式进行抽取栈底
2、再通过递归的方式将栈底放入栈中
时间：因为每一次抽取底部需要递归一波，一共递归n次，所以 O(n^2)
空间 O(n)

代码编写

java语言版本

public class ReverseStackUtils{
    /**
     * 递归取栈底并放入,通用方法
     */
    public static <T> void reverse(Stack<T> stack){
        try {
            if(stack.isEmpty()){
                return;
            }else{
                T t = getAndRemoveLastElement(stack);
                reverse(stack);
                stack.push(t);
            }
        }catch (Exception e){
            e.printStackTrace();
        }
        return;
    }

    /**
     * 取栈底值
     * 1、递归的截止条件一定要在调用递归方法之前
     * 2、递归方法之前就是营造一个能够截止递归的操作，如stack.pop()，而截止递归操作就是为了获取栈底
     * 3、递归方法之后则是处理本次递归的剩余逻辑，如 将栈顶再放回去
     */
    public static <T> T getAndRemoveLastElement(Stack<T> stack){
        try {
            T t = stack.pop();
            if(stack.isEmpty()){
                return t;
            }else{
                T t2 = getAndRemoveLastElement(stack);
                stack.push(t);
                return t2;
            }
        }catch (Exception e){
            e.printStackTrace();
        }
        return null;
    }


    /**
     * 普通方法，intger类型
     * @param stack
     * @return
     */
    public static void reverseForInt(Stack<Integer> stack){
        if (stack.isEmpty()){
            return;
        }
        Integer curlast = getLastAndRemoveForInt(stack);
        reverse(stack);
        stack.push(curlast);
    }


    public static Integer getLastAndRemoveForInt(Stack<Integer> stack){
        Integer pop = stack.pop();
        if (stack.isEmpty()){
            return pop;
        }
        Integer last = getLastAndRemoveForInt(stack);
        stack.push(pop);
        return last;
    }

    /**
     * 测试用例
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        Stack<Integer> testStack = new Stack<>();
        Arrays.stream(arr).forEach(u -> testStack.push(u));
        System.out.println(testStack.toString());
        // 逆序
        ReverseStackUtils.reverseForInt(testStack);
        System.out.println(testStack.toString());
    }
}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题将栈和递归的思想进行了结合，栈的每一次的pop都是递归的一次状态，每一次的递归都会存储当前的pop作为当前层递归的局部变量，而每一次的递归return都是将当前层的局部变量处理完成后返回。
比如：
1、刚开始写getLastAndRemoveForInt时，只需要写Integer pop = stack.pop();即可，但是总会有空的时候，所以这个时候需要判断stack如果是空才会返回，但是我们想要返回底值，所以stack为空时就是当前底值，直接返回当前值pop
2、返回之后走到的应该是上一层调用递归处的下一句话（stack.push(pop);），而返回值就是下一层的返回值last，除了last以外，其他的状态都要“收尾”，也就是重新放回stack，因此（stack.push(pop);），最后再将底值返回给上一层继续调用处的后半段代码。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可咨询2260755767@qq.com或在评论区回复即可.
再次感谢左大神的书对我算法的指点迷津！