栈Stack——递归替身？

栈Stack——递归替身？

在编程中，递归是一种常见的算法设计方法，但在处理大量数据时可能会导致栈溢出。本文将介绍Stack数据结构如何作为递归的替代方案，特别是在单向链表反转打印等场景中，使用Stack可以节省内存空间。

对于Stack这个集合类，由类继承关系可知是Vector的子类，根据push入栈方法跟踪代码，可知Vector是一个线程安全的类（高并发场景下使用，那可能不是一个好的选择）
看到这里，显然可以得知Stack入栈出栈的大致原理，就是Vector的
elementData对象数组
，用来储存数据，入栈时依次存放，出栈时倒序从数组中取出即可

在单向链表反转打印这样的场景中，我们可以很自然地想到使用递归来实现，相比递归我们可以使用Stack类依次将单向链表的
Node节点
存放至Stack的对象数组中，然后反向出栈取出即可。

  
    public void reversePrint(Node node) {
        Stack<Node> stack = new Stack<>();
        while (node != null) {
            stack.push(node);
            node = node.next;
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
    public void recursion(Node node) {
        if (node.next != null) {
            recursion(node.next);
        }
        System.out.println(node);
    }  

显然，在链表中节点元素较多的场景下，使用Stack的方案明显所需的memory更少。我们可以根据这个简单的示例，在递归场景下优先考虑Stack方案的可能性~（使用了数据结构来优化：方法调用所需要的内存空间）
当程序执行一个方法时，它会在调用栈上创建一个新的栈帧（Stack Frame）。这个栈帧包含了执行该方法所需的所有信息。当方法执行完毕并准备返回时，它的栈帧会从调用栈中弹出，控制权返回给调用者。
对于递归方法，每次递归调用都会创建一个新的栈帧，并将其推入调用栈中。如果递归调用过深，即调用栈中的栈帧数量超过了系统或JVM（Java虚拟机）等环境为调用栈分配的内存限制，就会发生栈溢出错误（StackOverflowError）。