数据结构和算法【3】只用递归函数逆序栈

皮皮克克 2023-06-02

132

点击关注公众号，干货第一时间送达

各位，请听题：

解题：

这题，我们需要使用到两个递归函数。

（1）第一个递归函数：获取并移除栈底元素

    public static int getAndRemoveBottom(Stack<Integer> stack){
        int pop = stack.pop();
        if (stack.isEmpty()){
            return pop;
        } else {
            int next = getAndRemoveBottom(stack);//不断弹出栈顶，直到栈空，就会返回pop
            stack.push(pop);
            return next;
        }
    }

方法测试：

    public static void main(String[] args) {

        Stack<Integer> stack = new Stack<Integer>();
        stack.add(1);
        stack.add(2);
        stack.add(3);
        stack.add(4);

        System.out.println("底部元素："+getAndRemoveBottom(stack));
        System.out.println("栈大小："+stack.size());
    }

输出：

D:\java\bin\java.exe
底部元素：1
栈大小：3

（2）借助上面的函数，我们就可以通过递归，不断获取栈底部元素，暂存起来，然后再压入栈，完成逆序

完整代码：

public class CodingDemo {


    /**
     * TODO: 只用递归函数，逆序一个栈
     * @param stack
     */
    public static void reverseStack(Stack<Integer> stack){
        if (stack.isEmpty()){
            return;
        }
        int bottom = getAndRemoveBottom(stack);
        reverseStack(stack);
        stack.push(bottom);
    }

    public static int getAndRemoveBottom(Stack<Integer> stack){
        int pop = stack.pop();
        if (stack.isEmpty()){
            return pop;
        } else {
            int next = getAndRemoveBottom(stack);//不断弹出栈顶，直到栈空，就会返回pop
            stack.push(pop);
            return next;
        }
    }


    public static void main(String[] args) {

        Stack<Integer> stack = new Stack<Integer>();
        stack.add(1);
        stack.add(2);
        stack.add(3);
        stack.add(4);

        reverseStack(stack);
        System.out.println("输出栈：");
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}

输出：

D:\java\bin\java.exe
输出栈：
1
2
3
4

结束语：

Ok，到此为止，就是本篇文章的全部内容了。

该文章主要讲了数据结构和算法：只用递归函数逆序栈。

如果各位有不懂的地方，欢迎发消息给小编，小编会进行详细地解答。

最后，请屏幕前的各位小可爱，动动你们的小手，给小编一个“在看”吧！

递归递归算法数据结构

文章转载自皮皮克克，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构和算法【3】只用递归函数逆序栈

评论