前端也要会的数据结构 （不定期更新篇）

一说到前端大家脑子里只有，布局、展示数据、修改样式等等。可是数据是哪里来的呢？后端给的后端给的。数据的结构呢？后端给啥用啥。

这就是前端的一个软肋。我们的业务让我们并不需要过深入的了解数据结构，数据结构和算法是一个 程序员 的基础。无论是前端开发还是后端开发、还是AI机器学习大数据，我认为都需要一定的数据结构和算法知识（除了前端，其余的都是强烈的刚需。。。），前端的伙伴们学会数据结构有什么好处呢？改变思考方式，深入了解js执行的一些过程，在代码中不知不觉考虑代码层面的性能优化。用处很多，接下来开始吧。

什么是数据结构？

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。（来自百度百科）

计算机存储是什么意思呢？就是我们常说的存储结构。

组织数据的方式与特定关系呢？就是我们的逻辑结构。

一堆按一定的存储结构和逻辑结构组合起来的数据集合就是数据结构。

这是我的一些理解。所以当一种数据结构摆在我的面前我就会考虑，它是以哪种形式存储起来，它有什么特殊的逻辑组合起来。这种方式有哪些好处呢？当我明白这些的时候，这种数据结构我就算基本了解了。

首先我们先说一下线性表，线性表是数据的逻辑结构，元素之间是一对一的关系，你个线性表中，任何一个元素的前一个或者后一个都只有一个元素，而不会出现任何一个元素的前一个或者后一个元素对应多个元素的情况。

线性表分为一般性的线性表、与受限的线性表。一般性的线性表就好比数组。就是最常见的一般性线性表，而受限的线性表就是栈与队列。

好了好了 我们开始正题了

你好 神奇的栈结构

栈型结构，最大的特点是什么？先进后出，先进入的元素要比后进入的元素更晚的离开这个容器，这像什么一堆摞起来的书籍。你这能拿走书的最上面的。（你要是给书推倒了，那就只能说明你比较睿智）

所以我们要实现一个栈型结构很自然的想到了

容器：数组

方法：数组的push与pop方法 下面开始实现一个栈的构造函数

function Stack(){
    // 用let创建一个私有容器，无法用this选择到dataStore；
    let dataStore = [];
    // 模拟进栈的方法 
    this.push = function(element){
        dataStore.push(element);
    };
    // 模拟出栈的方法，返回值是出栈的元素。
    this.pop = function(){
        return dataStore.pop();
    };
    // 返回栈顶元素
    this.peek = function(){
        return dataStore[dataStore.length-1];  
    };
    // 是否为空栈
    this.isEmpty = function(){
        return dataStore.length === 0 
    };
    // 获取栈结构的长度。
    this.size = function(){
        return dataStore.length;
    };
    //  清除栈结构内的所有元素。
    this.clear = function(){
        dataStore = [];
    }
}
复制代码

好了伙伴们 栈的构造函数我们已经写好了。

// 一个单独的栈生成了。
let stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(5);
stack.peek(); // return 5
stack.size(); // return 3
stack.clear();
stack.peek(); // undefined
复制代码

一个基本的栈型结构就实现了。 真的很是简单。但是这个东西在js中有什么用处呢？

在js中的用处

用处很大，首先我们都知道递归如果没有设置好边界值，就会报堆栈溢出。 什么意思？？？ 我们的js代码在执行的时候，会生成一个调用栈（里面装满了所有执行中的函数）

在这个调用栈第一个进栈的也就是压在最下面的就是全局函数，这个全局函数只会在浏览器关闭后才会出栈，浏览器关闭了这个堆栈也就随之消失了。 当浏览器执行下去的时候执行一个函数的时候，就会把这个执行中的函数加入到调用栈中，被调用了就要进调用栈（比较好理解吧），同时控制权也会转交给这个函数，这个函数中如果有别的函数，执行到别的函数时，做着一样的事情，进栈。当任何一个函数执行结束之后，那么不好意思，他就要退栈了。离开这个调用栈了。因为调用栈中内容过多，代表着垃圾资源没有回收，从而导致浏览器卡顿，这是不合理的，执行完毕就会退栈。

退栈之后，那么执行权就要交回到包含着它的函数了。

堆栈的三种场景

1:递归是一种怎样的情况呢？

当我们没有考虑递归的出口的时候，
简化函数
function fn(){
    let a = 1; fn()
}
fn()  // 报错！！！！ Maximum call stack size exceeded
      // 最大调用堆栈大小超过
复制代码

当我没有设定出口时，并没有任何一个函数会出栈，在不断的循环调用后，你的堆栈肯定不会是无限的，那么就只好提醒你堆栈溢出，程序报错。

2: 你知道redux的洋葱模型图吗？

所谓redux的洋葱模型（其实redux我没用过，但是在公司分享会上听过一段对于这个洋葱模型图的分享），大家也可以理解一下express框架的写接口时的next函数。

在我们洋葱在最外层执行完毕后就会进入里面，到最内部后再循坏退出来。

function fn1(){
    console.log('fn1 first');
    fn2()
    console.log('fn1 last');
}
function fn2(){
    console.log('fn2 first');
    fn3()
    console.log('fn2 last');
}
function fn3(){
    console.log('fn3 first');
    console.log('fn3 last');
}
fn1()
复制代码

打印结果中我们可以看出，fn1执行的时候在，遇到fn2执行进栈后，将控制权转交给fn2,fn2执行遇到fn3执行进栈，将控制权交给fn3，fn3执行完毕后退栈，控制权还给fn2，那么fn2后面的代码会继续执行，fn2的代码执行完毕，退栈。继续执行fn1后面的代码直到退栈。可能这种简单的模式大家看起来比较清晰，如果有比较复杂的内容，大家记得画图不要弄错了。

3: 不说你就会忘的闭包

为什么闭包使用过多会导致程序卡顿，性能不好？？？

这个问题很让人费解，但是扯上调用栈后，我觉得可以解释一波（代码我就不上了，大家可以去找找闭包得代码看一看） 闭包得私有变量怎么产生的？ 在一个函数执行后，它执行完毕就一定会退栈。

function A(){
  var count = 0;
  function B(){
    count ++;
    console.log(count);
  }
  return B;
}
var C = A();
C();// 1
C();// 2
C();// 3
复制代码

不好意思我食言了，方便大家理解还是上一波代码吧。

在A函数执行得时候，我们发现执行过程中，遇到B函数，好了它开始调用进栈执行，执行完毕后，控制权回归A函数，然后把B函数return出去了。B函数中保持对count变量的引用，你就把它return出去了？？？？好吧你愿意你就这么干。

B函数被推出去到外面的世界（外面的函数体内）；将B赋值给C，好了C需要count变量的支持，count就不能离开内存（也就是不能被垃圾回收）；拿咋办？ A函数执行完了我也该离开了（函数执行完毕后，函数内部的变量会被回收掉）。不好意思，外面执行着的函数还有对你的引用，那不好意思你别退栈了，并不允许离开调用栈，因为要保留count变量的环境。

好吧每一个这种情况就会有几个函数无法退栈，调用栈里面的内容越堆越多。就会越加卡顿。一辆公交车，咱们的乘客到站就下车了，但是总有几个乘客死活不下车，车上人越来越多，车也越来越沉，好吧跑起来就越来越慢了。