数据结构 | fdd’Blog

数据结构和 JavaScript 内存空间

数据结构

堆-Heap

堆数据结构是一种树状结构，利用完全二叉树维护的一组无序数据，比如对象的key-value数据。
堆分为最大堆和最小堆。
最大堆：将根节点最大的堆叫做最大堆或大根堆。最小堆：根节点最小的堆叫做最小堆或小根堆。
最大堆：

栈-Stack

栈是只能在某一端插入和删除的特殊线性表。
按照先进后出或后进先出（LIFO—last in first out）的原则存储数据，最先进入栈内的被压入栈底，最后的数据子栈顶。
入栈：往栈内添加元素
出栈：从栈内删除元素

使用数组实现一个栈

/**
 * 实现一个先进后出的栈结构
 * 添加元素push
 * 弹出元素pop
 * 返回栈顶元素top
 * 是否空栈isEmpty
 * 返回元素个数size
 * 清空栈元素clear
 */
function MyStack() {
  let items = []; //内部变量，保护
  //方法
  //向栈顶添加元素
  this.push = function (value) {
    items.push(value);
  };
  //弹出栈顶元素,返回
  this.pop = function () {
    return items.pop();
  };
  //返回栈顶元素
  this.top = function () {
    return items[items.length - 1];
  };
  //判断栈是否为空
  this.isEmpty = function () {
    return items.length === 0;
  };
  //返回栈里元素个数
  this.size = function () {
    return items.length;
  };
  //情况栈元素
  this.clear = function () {
    items = [];
  };
}

栈的应用

判断括号是否合法
思路：如果是(就入栈，如果是)就查看栈是否为空，如果栈为空就不合法，如果不为空，就弹出一个栈顶元素。循环结束，查看栈是否为空，为空就是合法，否则就不合法。

function is_leagl_brackets(string) {
let stack = new MyStack();
for (let i = 0; i < string.length; i++) {
    let str = string[i];
    if (str === "(") {
    stack.push(str);
    } else if (str === ")") {
    if (stack.isEmpty()) {
        return false;
    } else {
        stack.pop();
    }
    }
}
return stack.isEmpty();
}
console.log(is_leagl_brackets("()()))"));//false
console.log(is_leagl_brackets("(sd(qwqw)sd(sd))"));//true
console.log(is_leagl_brackets("()()sd()(sd()fw))("));//false

计算逆波拉表达式
逆波兰表达式也叫后缀表达式，将复杂的表达式转换为可以依靠简单的操作得到计算结果的表达式，例如(a+b)*(c+d)转换为ab+cd+*
根据简单的逆波兰表达式数组，计算表达式结果。
思路：如果是数字就入栈，如果是符号（只是简单的例子，不考虑错误的情况）就连续弹出两个栈顶元素，用两个元素和操作符组成计算表达式（第二个元素在操作符左边），利用eval计算结果，取整，变成字符串再放入栈中。

function calc_exp(arr) {
let stack = new MyStack();
arr.forEach((item) => {
    if (["+", "-", "/", "*"].indexOf(item) > -1) {
    let v1 = stack.pop();
    let v2 = stack.pop();
    let exp = v2 + item + v1;
    let result = parseInt(eval(exp));
    stack.push(result.toString());
    } else {
    stack.push(item);
    }
});
return stack.pop();
}
console.log(calc_exp(["4", "13", "5", "/", "+"]));//6

实现一个有 min 方法的栈
思路：利用两个栈，一个存放数据，一个存放最小值

function MinStack() {
let data_stack = new MyStack(); //存储数据
let min_stack = new MyStack(); //存储最小值
//入栈
this.push = function (item) {
    data_stack.push(item);
    //如果最小值栈是空的或当前元素小于最小栈顶元素，就入栈到最小栈顶
    if (min_stack.isEmpty() || item < min_stack.top()) {
    min_stack.push(item);
    } else {
    //如果当前值大于最小值栈顶元素，就把最小值栈顶元素再次入栈
    min_stack.push(min_stack.top());
    }
};
//出栈
this.pop = function () {
    min_stack.pop();
    return data_stack.pop();
};
//最小值
this.min = function () {
    return min_stack.top();
};
}
let minStack = new MinStack();
minStack.push(3);
console.log(minStack.min()); //3
minStack.push(6);
console.log(minStack.min()); //3
minStack.push(9);
console.log(minStack.min()); //3
minStack.push(1);
console.log(minStack.min()); //1
minStack.pop();
console.log(minStack.min()); //3

队列-Queue

队列也是一种操作受限制的线性表。
只允许在前端（头）进行删除操作，在后端（尾）进行插入操作。所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）
队列没有元素时，成为空队列。
入队：往队列中插入元素
出队：从队列中删除元素

使用数组实现一个队列

/**
 * enqueue从队列尾部添加一个元素
 * dequeue从队列头部删除一个元素
 * head返回头部的元素
 * size 返回队列大小
 * clear 清空对列
 * isEmpty 判断队列是否为空
 */
function MyQueue() {
  let items = [];
  //入队
  this.enqueue = function (item) {
    items.push(item);
  };
  //出队
  this.dequeue = function () {
    return items.shift();
  };
  //返回头部元素
  this.head = function () {
    return items[0];
  };
  //返回队列大小
  this.size = function () {
    return items.length;
  };
  //清空队列
  this.clear = function () {
    items = [];
  };
  //队列是否为空
  this.isEmpty = function () {
    return items.length === 0;
  };
}

队列的应用

约瑟夫环
题目：一个数组a[100]存放0-99，要求每隔两个数删掉一个数，到末尾时循环至开头继续执行（删除逻辑也是继续），求最后一个被删掉的数。

function circle(arr_list) {
let queue = new MyQueue();
arr_list.forEach((v) => queue.enqueue(v));
let index = 0;
while (queue.size() > 1) {
    let item = queue.dequeue();
    index++;
    if (index % 3 != 0) {
    queue.enqueue(item);
    }
}
return queue.head();
}
let arr_list = new Array(100).fill(0).map((v, i) => i);
console.log(circle(arr_list));

斐波那契数列
公式：fn= f(n-2)+f(n-1)
前两位是 1，1

function fib(n) {
  if (n === 1 || n === 2) return 1;
  let queue = new MyQueue();
  //初始值前两位是1
  queue.enqueue(1);
  queue.enqueue(1);
  let index = 2;
  while (index < n) {
      //弹出队头
      let num1 = queue.dequeue();
      //获取队头
      let num2 = queue.head();
      //计算下一个数据
      let num3 = num1 + num2;
      //将新数据入队
      queue.enqueue(num3);
      index++;
  }
  //弹出队头
  queue.dequeue();
  return queue.head();
}
console.log("fib", fib(5));

链表

JavaScript 内存空间

内存空间管理

JavaScript 的内存生命周期：

为变量分配所需要的内存
使用分配到的内存（读、写）
不再使用时将其销毁，释放内存

内存管理不善，会出现内存泄漏，造成浏览器内存占用过多，页面卡顿等问题。
例子：

1
2
3

var a = 20;  // 在内存中给数值变量分配空间
alert(a + 100);  // 使用内存
a = null; // 使用完毕之后，释放内存空间

垃圾回收机制

JavaScript 有自动的垃圾回收机制，会通过标记清除的算法，找出不再继续使用的变量对象，释放其内存。
开发者也可通过设置a=null手动标记清除，让其原本对应的值失去引用，脱离执行环境，这个值会在下一次垃圾回收执行时找到并释放。而在适当的时候解除引用，是为页面获得更好性能的一个重要方式。
局部环境中，函数执行完成后，函数局部环境声明的变量不再需要时，就会被垃圾回收销毁（理想的情况下，闭包会阻止这一过程）。
全局环境只有页面退出时才会出栈，解除变量引用。所以开发者应尽量避免在全局环境中创建全局变量，如需使用，也要在不需要时手动标记清除，将其内存释放掉。

简单介绍一下 V8 引擎的垃圾回收机制

v8 的垃圾回收机制基于分代回收机制，这个机制又基于世代假说，这个假说有两个特点，一是新生的对象容易早死，另一个是不死的对象会活得更久。基于这个假说，v8 引擎将内存分为了新生代和老生代。

新创建的对象或者只经历过一次的垃圾回收的对象被称为新生代。经历过多次垃圾回收的对象被称为老生代。

新生代被分为 From 和 To 两个空间，To 一般是闲置的。当 From 空间满了的时候会执行 Scavenge 算法进行垃圾回收。当我们执行垃圾回收算法的时候应用逻辑将会停止，等垃圾回收结束后再继续执行。这个算法分为三步：

（1）首先检查 From 空间的存活对象，如果对象存活则判断对象是否满足晋升到老生代的条件，如果满足条件则晋升到老生代。如果不满足条件则移动 To 空间。

（2）如果对象不存活，则释放对象的空间。

（3）最后将 From 空间和 To 空间角色进行交换。

新生代对象晋升到老生代有两个条件：

（1）第一个是判断是对象否已经经过一次 Scavenge 回收。若经历过，则将对象从 From 空间复制到老生代中；若没有经历，则复制到 To 空间。

（2）第二个是 To 空间的内存使用占比是否超过限制。当对象从 From 空间复制到 To 空间时，若 To 空间使用超过 25%，则对象直接晋升到老生代中。设置 25% 的原因主要是因为算法结束后，两个空间结束后会交换位置，如果 To 空间的内存太小，会影响后续的内存分配。

老生代采用了标记清除法和标记压缩法。标记清除法首先会对内存中存活的对象进行标记，标记结束后清除掉那些没有标记的对象。由于标记清除后会造成很多的内存碎片，不便于后面的内存分配。所以了解决内存碎片的问题引入了标记压缩法。

由于在进行垃圾回收的时候会暂停应用的逻辑，对于新生代方法由于内存小，每次停顿的时间不会太长，但对于老生代来说每次垃圾回收的时间长，停顿会造成很大的影响。为了解决这个问题 V8 引入了增量标记的方法，将一次停顿进行的过程分为了多步，每次执行完一小步就让运行逻辑执行一会，就这样交替运行。

哪些操作会造成内存泄漏

意外的全局变量
未定义的变量会在全局对象创建一个新变量。在浏览器中，全局对象是 window 。
1
2
3
function foo(){
bar='bar is not defined'
}
函数内部通过 this 创建全局变量。
1
2
3
function foo(){
this.bar='bar is not defined'
}
可以通过开启严格模式避免这种错误。
全局变量注意事项
如果必须使用全局变量存储大量的数据时，确保用完以后把它设置成 null。
被遗忘的计时器或回调函数
1
2
3
4
5
6
7
let someResource=getData();
setInterval(()=>{
let node=document.getElementById('node');
if(node){
node.innerHTML=JSON.stringify(someResource)
}
},1000)
如果 id 为 Node 的元素从 DOM 中移除, 该定时器仍会存在, 同时, 因为回调函数中包含对 someResource 的引用, 定时器外面的 someResource 也不会被释放.
脱离 DOM 的引用
进行 DOM 操作的时候，用变量保存 DOM 结构，这样一个 DOM 结构就存在两个引用，一个是 DOM 树，一个是变量。如果删除 DOM 树中的元素，因为还存在变量引用，内存不会释放。所以删除时，需要设置变量为 null
1
2
3
4
5
6
7
8
9
let button=document.getElementById('button');

function doStuff(){
button.click()
}

function removeButton(){
document.body.removeChild(document.getElementById('button'))
}
还要考虑 DOM 树内部或子节点的引用问题。假如你的 JavaScript 代码中保存了表格某一个的引用。将来决定删除整个表格的时候，直觉认为垃圾回收器(GC)会回收除了已保存的以外的其它节点。实际情况并非如此：此是表格的子节点，子元素与父元素是引用关系。由于代码保留了的引用，导致整个表格仍待在内存中。保存 DOM 元素引用的时候，要小心谨慎。
不合理的使用闭包，从而导致某些变量一直被留在内存当中
变量赋值 null