Contents

1. 1. 一、栈是什么
2. 2. 二、栈能干什么
   1. 2.1. 最先想到的应该是递归
   2. 2.2. 紧接着在想能否拿一个东西来缓存一下呢，这时候就可以用到栈的结构
   3. 2.3. 其他应用

一、栈是什么

栈，理解为一个先进后出的容器。我们经常会提到几个词，程序栈，调用栈。此时就是用到了栈的数据结构

这边可以用链式表表示

Stack {
    int size;
    Node top;
}

结合图形学习

二、栈能干什么

开始前，先介绍一个经典的数列“斐波那契数列”

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368

可以得出的基本运算方式为

Fib {    
    0 -> 0
    1 -> 1
    n -> Fib(n-1) + Fib(n-2) 
} 

要求，用一套算法来计算得出这个数列第n个数的值

最先想到的应该是递归

/** 
 * 方法内部调用并返回
 * return Fib(n-1) + Fib(n-2)
**/
function Fib(n){
    if(n == 0){
        return 0;
    }else if( n == 1 ){
        return 1;
    }else{
        return Fib(n-1) + Fib(n-2);
    }
}

紧接着在想能否拿一个东西来缓存一下呢，这时候就可以用到栈的结构

/**
 * 用一个栈缓存需要计算的信息
 * */
// 0 1 1 2 3 5 8 
function Fib2(n){
	var s = [];
	var w;
	var temp;
	var sum = 0;
	w = n;
	s.push(w);
	while ( s.length != 0 ){
		temp = s.pop();
		if(temp == 0){
		} else if(temp == 1 || temp == 2 ){
			sum ++;
		} else {
			s.push(temp-2);
			s.push(temp-1);
		}
	}
	return sum;
}
console.log(Fib2(7));

具体的算法思维如下图所示

首先将需要计算的fib数推入到栈中，然后取出最上层的数进行fib计算后，得到两个值继续推入栈中，直生成 0 ， 1 ，2 中一值后，返回上一层继续计算（有种回溯的思维）

其他应用

栈的结构非常适合用于深度优先遍历，如树的先序遍历和图的深度优先遍历，后面会讲到