给你一个栈,请你逆序这个栈,不能申请额外的数据结构,只能使用递归函数。如何实现?
我们先不想如何逆序这个栈,我们先想办法实现一个这样的函数:栈传进这个函数以后,返回栈底的元素,并且栈底上面的元素依次盖下来。(就如同数组删除一个元素后,后面的元素依次往前挪动一个位置),如下图:
如何实现这个函数呢?
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()); } } }
通过这个问题,我们明白了递归栈是可以保存信息的,并且你想怎么试,你就可以怎么写。问题就是要记住,把一个大问题拆成含义一样的子问题的时候,只是数据量变小了。具体尝试的过程是想怎么试就可以怎么写。
但是尝试的过程是有优劣的,比如汉诺塔问题,可以用六个递归过程去尝试,也可以抽象化只用一个递归过程。 推荐看看这篇文章——暴力递归——汉诺塔问题。
在面试过程中很少需要用到用暴力解的方法,因为所以尝试这件事情是有优劣的,但如何评价这个好坏,请继续关注后序动态规划的文章,后边动态规划会描述如何设计一个尝试,能够优化出最优的解。感谢您的三连或者点赞支持🙇🙇🙇