暴力递归——逆序栈，不能申请额外的数据结构，只能使用递归函数

2022-05-16 19:19:45

给你一个栈,请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现?

我们先不想如何逆序这个栈，我们先想办法实现一个这样的函数：栈传进这个函数以后，返回栈底的元素，并且栈底上面的元素依次盖下来。（就如同数组删除一个元素后，后面的元素依次往前挪动一个位置），如下图：

如何实现这个函数呢？

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

暴力递归——逆序栈，不能申请额外的数据结构，只能使用递归函数

这个函数的功能就是移除栈底元素并返回栈底元素，上面的元素盖下来。大家可以配合代码和截图自己过一遍。

这个功能实现了之后，主函数的实现就很简单了。

public static void reverse(Stack<Integer> stack) {
        if(stack.isEmpty()) {
            return ;
        }
        int i=removeAndReturnBottomElement(stack);
        reverse(stack);
        stack.push(i);
    }

暴力递归——逆序栈，不能申请额外的数据结构，只能使用递归函数

完整代码：

package com.harrison.class12;

import java.util.Stack;

public class Code02_ReverseStackUsingRecursive {
    public static int removeAndReturnBottomElement(Stack<Integer> stack) {
        int result=stack.pop();
        if(stack.isEmpty()) {
            return result;
        }else {
            int last=removeAndReturnBottomElement(stack);
            stack.push(result);
            return last;
        }
    }
    
    public static void reverse(Stack<Integer> stack) {
        if(stack.isEmpty()) {
            return ;
        }
        int i=removeAndReturnBottomElement(stack);
        reverse(stack);
        stack.push(i);
    }
    
    public static void main(String[] args) {
        Stack<Integer> stack=new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        reverse(stack);
        while(!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

通过这个问题，我们明白了递归栈是可以保存信息的，并且你想怎么试，你就可以怎么写。问题就是要记住，把一个大问题拆成含义一样的子问题的时候，只是数据量变小了。具体尝试的过程是想怎么试就可以怎么写。

但是尝试的过程是有优劣的，比如汉诺塔问题，可以用六个递归过程去尝试，也可以抽象化只用一个递归过程。推荐看看这篇文章——暴力递归——汉诺塔问题。

在面试过程中很少需要用到用暴力解的方法，因为所以尝试这件事情是有优劣的，但如何评价这个好坏，请继续关注后序动态规划的文章，后边动态规划会描述如何设计一个尝试，能够优化出最优的解。感谢您的三连或者点赞支持????‍????‍????‍

码农公寓

给你一个栈,请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现?

相关文章