数据结构与算法之栈与递归

栈

栈是限定仅在表尾进行插入和删除操作的线性表

允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为先进后出的线性表

栈的实现

顺序方式：

1544528491818.png

链式方式：

1544528526381.png

入栈操作

1544528656592.png

出栈操作：

1544528702423.png

应用：

利用栈的特点实现反向输出链表（将链表的值一个个存入到栈中，再从栈中一个个读取）

public static void main(String args[]){
        Node node1 = new Node();
        Node node2 = new Node();
        Node node3 = new Node();
        node1.data = 1;
        node2.data = 2;
        node3.data = 3;
        node1.next = node2;
        node2.next = node3;
        printListReverse(node1);
   }
public static void printListReverse(Node headNode){
    Stack<Node> stack = new Stack<Node>();
    while (headNode != null){
        stack.push(headNode);
        headNode = headNode.next;
    }
    while (!stack.isEmpty()){
        System.out.println(stack.pop().data);
}

递归

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

执行特点

1544528980713.png

实例：汉诺塔算法

1544532455108.png

将A上的方块以B为辅助移动到C上去

702782-20161114213448920-1185627397.png

按照原理图来编码

  /**
     * @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);
        }
    }

步骤分析：

1544532572962.png 6c224f4a20a44623166a8b879922720e0df3d7b6.gif