理解java中的堆栈递归

Question

代码运行良好。只是我不明白。在递归部分有困难的。在此部分中:char a=st.peek（）；st.pop（）；insert_at_bottom(x)；st.push(a)；我的想法是，首先它将一直执行char a=st.peek()；st.pop()直到一个阈值。则它将执行st.push(a)；一次。因此a只会被赋值一次。显然那不是真的。

对我来说，困难的部分是在insert_at_bottom方法中，insert_at_bottom(x)做什么？在reverse方法中，reverse()、insert_at_bottom(x)做什么？

import java.util.Stack;
class Test {
    static Stack<Character> st = new Stack<>();
    static void insert_at_bottom(char x)
    {
        if(st.isEmpty()) st.push(x);
        else
        {char a = st.peek();
            st.pop();
            insert_at_bottom(x);
            st.push(a);
        }
    }
    
    static void reverse()
    {
        if(st.size() > 0)
        {           
            char x = st.peek();
            st.pop();
            reverse();
            insert_at_bottom(x);
        }
    }
    public static void main(String[] args)
    {   st.push('1'); st.push('2'); st.push('3'); st.push('4');     
        System.out.println("Original Stack");
        System.out.println(st);
        reverse();
        System.out.println("Reversed Stack");
        System.out.println(st); }}

Answer 1

要理解您的方法是做什么的，您必须理解堆栈是什么。堆栈就像一叠盘子：只能将盘子放在堆栈的顶部，或者从顶部取回盘子。否则，堆栈将崩溃。

如果要在盘子的底部加一个盘子，你得把之前所有的盘子都拆下来。简单的方法是这样做：当堆栈上有一个盘子时，你把它移走并放在一边。如果堆栈是空的，那么你可以把你的新盘子放在堆栈的底部。然后你必须把所有的盘子放回新底板上。

在insert_at_bottom中的操作完全相同，但使用了递归方法：当堆栈中有一个char（即它不是空的）时，将顶部的char（标记为a)放在一边，然后再次尝试将x放在底部。如果堆栈不为空，则重新执行该操作。一旦到达堆栈的底部，就可以将x放在那里，并开始按之前相同的顺序推送所有其他char。

reverse方法使用了几乎相同的过程，但有点小的变化：取顶部的char并将其放在一边，取第二个顶部的char并将其放在一边，...当您在最后一个char上时，您可以将其放在堆栈的底部。然后将先前的第二个底部char放在堆栈的底部...然后返回到前面的顶部char,将其放在最后的底部。然后你的堆栈全部被颠倒了。