Java进阶——数据结构与算法之栈与递归小结（三）

引言

前面一篇文章我们学习了线性表中的链式存储结构的链表，这篇文章好好总结另一种线性表中——栈。

一、栈的概述

栈（stack）也称为后进先出表是一种只能在一端（即允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)）进行插入和删除操作的特殊线性表。它按照先进后出（FILO）的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。向一个栈插入新元素又称作进栈、入栈或压栈——它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；而从一个栈顶删除元素又称作出栈或退栈——它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素，栈还有具有记忆作用，对栈的插入与删除操作中，都不需要改变栈底指针。通常栈底固定，而栈顶浮动，栈中元素个数为零时称为空栈，栈在程序语言系统中应用广泛，比如栈可以用来在函数调用的时候存储断点，还有做递归时也要用到栈。本质上栈和数组或者链表的底层机制大同小异（Stack是继承自Vector的，而ArrayList是去掉了线程安全的Vector），所以可以把栈看成操作受限的数组（顺序实现方式）或者链表（链式实现方式）。

二、栈的实现

1、栈的顺序实现与基本算法

JDK 中给我们实现了顺序栈即Stack类。

1.1、入栈（push）

入栈前首先需要检查栈是否已满，若已经满了则给出溢出反馈，并进行处理，比如说继续扩容，源码中Stack 是按照2倍进行扩容的，然后再把原来的数通过System.arrayCopy方法拷贝到新的数组中，然后top指针加1，再把新top索引处赋值。

1.2、出栈 （pop）

出栈前首先需要检查栈是否为空，若已为空了则给出反馈，并进行处理，反之就是元素出栈，栈顶指针减1

2、栈的链式实现与基本算法

栈的链式实现其实本质就是一个单链表，top指针相当于是单链表中的head 节点，而且采用链式存储相对于顺序存储来说更节省内存空间（因为链式存储不要求元素之间内存空间连续），事实上断点调试和递归都是吧代码通过链式存储结构的方式进行存储的。

1.1、入栈（push）和 出栈 （pop）

本质上入栈（push）就是单链表的添加操作，而出栈（pop）本质上则是单链表删除操作。

四、栈的应用

1、逆波兰表达式

逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示，计算机中的算术运算就是采用逆波兰表达式，它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算规则如下：如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。以前大学中的所做计算器就是结合栈来实现的，首先通过栈把中缀表达式转为后缀表达式（其中规则是：数字输出，符号进栈，括号匹配出栈，比栈顶优先级低的出栈（同样一符号也出栈）），然后再根据运算规则出入栈。

2、递归

程序调用自身的编程技巧称为递归（ recursion），递归做为一种算法在程序设计语言中广泛应用，递归是操作系统层面支持的机制，我们都知道寄存器是存储操作数的，而代码符号是存在内存里的，代码栈也是底层操作系统支持的，是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，而且普通方法的入栈规则与递归方法的入栈规则有所不同，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

2.1、递归的核心思想

递归就是把大问题分割为与大问题一样逻辑的小问题进行处理，先看下面这个简单的例子，如果传入2执行这个方法输出是？

    public void fun(int n){
        System.out.println("\t"+n);//代码1
        if(n<0){//递归出口
            return;//调出此处方法，回到上一次调用的代码的起始位置
        }else{
            System.out.print("\tbef\t"+n);//代码2
            fun(n-1);//调用自己形成递归
            System.out.print("\taft\t"+n);//代码3
        }
    }

是否与你想象中的一样呢，而又为什么会是这样的输出结果呢？这一切与我的栈有巨大的关系，首先传入2，首先执行代码1 输出 2并换行，然后执行到if 条件判断2<0不满足进到else分支，再次打印输出bef 2，接着调用自己（相当于是又回到了代码1开始执行，但是此时代码3呢，它也属于fun方法中的代码片段，按道理说每一次执行fun它都需要被执行呀，可是由于递归的存在，暂时剥夺了他运行的权利，仅仅是暂时），所以此时递归后的代码3 的起始地址被缓存到代码栈中（注意，此处这样子分离仅仅是为了说明流程并不严谨，因为实际上方法的调用就是入栈的过程，而方法的执行就是出栈的过程，每一次方法调用指令之前，JVM先会把方法被调用的对象引用压入操作数栈中，除了对象的引用之外，JVM还会把方法的参数依次压入操作数栈。在执行方法调用指令时，JVM会将函数参数和对象引用依次从操作数栈弹出，并新建一个栈帧，把对象引用和函数参数分别放入新栈帧的局部变量表slot0，1，2…，JVM把新栈帧push入虚拟机方法栈，并把PC指向函数的第一条待执行的指令。欲了解更多请深入JVM原理），然后相当于第一次执行fun方法的时候还剩下代码3待执行，简单理解成执行fun(3)时候还有代码3 待执行被缓存起来，然后执行fun(3-1)，再输出2 ，如此反复，当传入到-1时候的时候，先输出 -1，然后满足if 条件通过return回到上一次调用的位置（即fun(0-1)的处）往下执行，此时再从代码栈拿回之前的System.out.print(“\taft”+0);执行，需要注意这时候相当于是fun(0)执行完毕，即fun（1）中的fun(1-1)执行完毕自然走到下一句代码又回到栈中去拿执行System.out.print(“\taft”+1)，最后回到fun（2）中递归最开始处，从栈中拿回来执行，整个递归流程完毕。（整个流程可能对于方法调用机制描述过于简单，仅仅是为了说明递归流程，真正的JVM 执行方法流程请自己查阅）

2.2、斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N*）

    /**
     * fibonacciSequence数列   8=7+6   7=6+5  6=5+4
     * 1   1  2  3  5  8   13  21  34  55  89  144......
     * 返回第n项
     */
    public int fibonacciSequence(int n){
        if(n==1 || n==2){
            return 1;
        }else{
            return fibonacciSequence(n-1)+fibonacciSequence(n-2);
        }
    }

2.3、汉诺塔

    /**
     * @param n      盘子的个数
     * @param start   开始的柱子
     * @param middle   中介柱子
     * @param end      结果柱子
     */
    public static void hanoi(int n,int start,int middle,int end){
        if(n<=1){
            System.out.println(start+"----->"+end);
        }else{
            hanoi(n-1,start,end,middle);
            System.out.println(start+"----->"+end);
            hanoi(n-1,middle,start,end);
        }
    }

2.4、栈溢出与递归的优化

如果实际操作中递归深度过深则很容易发生栈溢出，所以对于一些递归（每一次方法执行完毕之后不需要在栈上存储参数，上一次的结果全部作为参数向下传递）我们可以采用“尾递归”进行优化，就是把每一次递归的结果向下传递，这样的话编译器会进行优化递归流程，返回的时候省略掉中间的一些递归流程。

悲剧的是JVM 自身并没有对尾递归进行优化，可以借助ProGuard 进行代码优化，Linux下C/C++ 的编译器则进行强大的优化，尾递归性能强过普通递归无数倍，举个例子用普通递归求斐波那契数列第40多个数耗时几十秒都不一定得到结果，而改成尾递归可以瞬间计算出第5000个的结果。

把斐波那契数列改成尾递归形式

    public int realfib( int n,  int f1,  int f2){
        if(n==0){
            return f1;
        }else{
            return realfib(n-1,f2,f1+f2);
        }
    }

    public int advfibSequence(int n){
        return realfib(n,0,1);
    }

原文地址：https://blog.csdn.net/CrazyMo_/article/details/84928590

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！