用递归逆序一个栈
用递归逆序一个栈

用递归逆序一个栈

Scroll Down

首先准备一个方法,将用来获得栈底的元素


  public  static Integer getAndRemoveBottom(Stack<Integer> stack) {
     /**
       *如果stack是空的话,stack.pop()会NPE,这里没有判断的原因是下一个函数调用本函数时,可以确保stack不为空
       **/
        Integer bottomItem = stack.pop();
        if (stack.isEmpty()) {
            return bottomItem;
        } else {
            Integer last = getAndRemoveBottom(stack);
            stack.push(bottomItem);
            return last;
        }
    }

主函数,每次获得stack的最底部元素,并将其入栈,执行到最后即得到一个逆序的stack

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

接下来是喜闻乐见的测试环节

 public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        s.push(1);
        s.push(2);
        s.push(99);
        reverse(s);
        while (!s.isEmpty()){
            System.out.println(s.pop());
        }
    }

输出结果

1
2
99

灵魂画手上线,来一波流程图讲解一下详细流程

本来想画图详细分析一波的,但是发现完全讲清楚递归,太难画了。。所以果断鸽了,本文适合有已经知道递归概念的同学,至于咋知道的,就emmmmcoolapk_emotion_55_doge