从零开始学数据结构和算法(三)栈与栈的应用栈

• 栈是限定仅在表尾进行插入和删除操作的线性表
• 允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表

栈的实现

• 顺序方式

• Stack.java 源码
  • 参考 D:\Android\学无止境\随记\SchemaLearningRecords\源码分析\java\Stack 源码分析.md

递归基础

程序调用自身的编程技巧称为递归（recursion）。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法， 它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解， 递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 递归的能力在于用有限的语句来定义对象的无限集合。 一般来说，递归需要有边界条件、递归前进段和递归返回段。 当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

执行特点

''' fun( 3 ) '''

经典递归算法 - 汉罗塔算法

需求：

​ A 放入 N 个盘子，并且盘子在柱子中从大到小依次向上小盘子不能在大盘子上，求把 A 中的盘子移到 C 中最少移动几次，如何移动。注意每次只能一个 。

分析：

​ 汉诺塔问题就是把A柱上的N-1个盘子经过C移动到B，再把A上的最大的盘子移到C，而B上的N-1再类似上述步骤递归循环移到C上。

动画演示：

上代码：

  private void move(String a,String c){
        System.out.println("从" + a + "到" + c);
    }

public void hanoi(int n ,String a,String b,String c){
    if(n == 1){
        move(a,c);
    }else{
        hanoi(n-1,a,c,b);
        move(a,c);
        hanoi(n-1,b,a,c);
    }
}

调用自己一次的情况

• 调用位置前面的代码是正循环，调用位置后面的代码是反循环

调用自己二次的情况

• 他是一个二叉树的中序遍历过程

作者：DevYK
链接：https://juejin.im/post/5c9453965188252db02e4be6