JavaScript 数据结构与算法之美 - 栈内存与堆内存 、浅拷贝与深拷贝

[biaochenxuying]

前言

想写好前端，先练好内功。

栈内存与堆内存 、浅拷贝与深拷贝，可以说是前端程序员的内功，要知其然，知其所以然。

笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。

栈

定义

1. 后进者先出，先进者后出，简称 后进先出（LIFO），这就是典型的栈结构。
2. 新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。
3. 在栈里，新元素都靠近栈顶，旧元素都接近栈底。
4. 从栈的操作特性来看，是一种 操作受限的线性表，只允许在一端插入和删除数据。
5. 不包含任何元素的栈称为空栈。

栈也被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈。

堆

定义

• 堆数据结构是一种树状结构。
  它的存取数据的方式，与书架与书非常相似。我们不关心书的放置顺序是怎样的，只需知道书的名字就可以取出我们想要的书了。
  好比在 JSON 格式的数据中，我们存储的 key-value 是可以无序的，只要知道 key，就能取出这个 key 对应的 value。

堆与栈比较

• 堆是动态分配内存，内存大小不一，也不会自动释放。
• 栈是自动分配相对固定大小的内存空间，并由系统自动释放。
• 栈，线性结构，后进先出，便于管理。
• 堆，一个混沌，杂乱无章，方便存储和开辟内存空间。

栈内存与堆内存

JavaScript 中的变量分为基本类型和引用类型。

• 基本类型是保存在栈内存中的简单数据段，它们的值都有固定的大小，保存在栈空间，通过按值访问，并由系统自动分配和自动释放。
  这样带来的好处就是，内存可以及时得到回收，相对于堆来说，更加容易管理内存空间。
  JavaScript 中的 Boolean、Null、Undefined、Number、String、Symbol 都是基本类型。

• 引用类型（如对象、数组、函数等）是保存在堆内存中的对象，值大小不固定，栈内存中存放的该对象的访问地址指向堆内存中的对象，JavaScript 不允许直接访问堆内存中的位置，因此操作对象时，实际操作对象的引用。
  JavaScript 中的 Object、Array、Function、RegExp、Date 是引用类型。

结合实例说明

let a1 = 0; // 栈内存
let a2 = "this is string" // 栈内存
let a3 = null; // 栈内存
let b = { x: 10 }; // 变量 b 存在于栈中，{ x: 10 } 作为对象存在于堆中
let c = [1, 2, 3]; // 变量 c 存在于栈中，[1, 2, 3] 作为对象存在于堆中

当我们要访问堆内存中的引用数据类型时

• 1. 从栈中获取该对象的地址引用
• 2. 再从堆内存中取得我们需要的数据

基本类型发生复制

let a = 20;
let b = a;
b = 30;
console.log(a); // 20

在栈内存中的数据发生复制行为时，系统会自动为新的变量分配一个新值，最后这些变量都是 相互独立，互不影响的。

引用类型发生复制

let a = { x: 10, y: 20 }
let b = a;
b.x = 5;
console.log(a.x); // 5

• 引用类型的复制，同样为新的变量 b 分配一个新的值，保存在栈内存中，不同的是，这个值仅仅是引用类型的一个地址指针。
• 他们两个指向同一个值，也就是地址指针相同，在堆内存中访问到的具体对象实际上是同一个。
• 因此改变 b.x 时，a.x 也发生了变化，这就是引用类型的特性。

结合下图理解

总结

栈内存	堆内存
存储基础数据类型	存储引用数据类型
按值访问	按引用访问
存储的值大小固定	存储的值大小不定，可动态调整
由系统自动分配内存空间	由代码进行指定分配
空间小，运行效率高	空间大，运行效率相对较低
先进后出，后进先出	无序存储，可根据引用直接获取

浅拷贝与深拷贝

上面讲的引用类型的复制就是浅拷贝，复制得到的访问地址都指向同一个内存空间。所以修改了其中一个的值，另外一个也跟着改变了。

深拷贝：复制得到的访问地址指向不同的内存空间，互不相干。所以修改其中一个值，另外一个不会改变。

平时使用数组复制时，我们大多数会使用 =，这只是浅拷贝，存在很多问题。比如：

let arr = [1,2,3,4,5];
let arr2 = arr;
console.log(arr) //[1, 2, 3, 4, 5]
console.log(arr2) //[1, 2, 3, 4, 5]
arr[0] = 6;
console.log(arr) //[6, 2, 3, 4, 5]
console.log(arr2) //[6, 2, 3, 4, 5]
arr2[4] = 7;
console.log(arr) //[6, 2, 3, 4, 7]
console.log(arr2) //[6, 2, 3, 4, 7]

很明显，浅拷贝下，拷贝和被拷贝的数组会相互受到影响。

所以，必须要有一种不受影响的方法，那就是深拷贝。

深拷贝的的复制过程

let a = { x: 10, y: 20 }
let b = JSON.parse(JSON.stringify(a));
b.x = 5;
console.log(a.x); // 10
console.log(b.x); // 5

数组

一、for 循环

//for 循环 copy
function copy(arr) {
    let cArr = []
    for(let i = 0; i < arr.length; i++){
      cArr.push(arr[i])
    }
    return cArr;
}
let arr3 = [1,2,3,4];
let arr4 = copy(arr3) //[1,2,3,4]
console.log(arr4) //[1,2,3,4]
arr3[0] = 5;
console.log(arr3) //[5,2,3,4]
console.log(arr4) //[1,2,3,4]

二、slice 方法

//slice实现深拷贝
let arr5 = [1,2,3,4];
let arr6 = arr5.slice(0);
arr5[0] = 5;
console.log(arr5); //[5,2,3,4]
console.log(arr6); //[1,2,3,4]

三、concat 方法

//concat实现深拷贝
let arr7 = [1,2,3,4];
let arr8 = arr7.concat();
arr7[0] = 5;
console.log(arr7); //[5,2,3,4]
console.log(arr8); //[1,2,3,4]

四、es6 扩展运算

//es6 扩展运算实现深拷贝
let arr9 = [1,2,3,4];
let [...arr10] = arr9;
arr9[0] = 5;
console.log(arr9) //[5,2,3,4]
console.log(arr10) //[1,2,3,4]

五、JSON.parse 与 JSON.stringify

let arr9 = [1,2,3,4];
let arr10 = JSON.parse(JSON.stringify(arr9))
arr9[0] = 5;
console.log(arr9) //[5,2,3,4]
console.log(arr10) //[1,2,3,4]

注意：该方法在数据量比较大时，会有性能问题。

对象

一、对象的循环

//  循环 copy 对象
let obj = {
    id:'0',
    name:'king',
    sex:'man'
}
let obj2 = copy2(obj)
function copy2(obj) {
    let cObj = {};
    for(var key in obj){
      cObj[key] = obj[key]
    }
    return cObj
}
obj2.name = "king2"
console.log(obj) // {id: "0", name: "king", sex: "man"}
console.log(obj2) // {id: "0", name: "king2", sex: "man"}

二、JSON.parse 与 JSON.stringify

var obj1 = {
    x: 1, 
    y: {
        m: 1
    },
    a:undefined,
    b:function(a,b){
      return a+b
    },
    c:Symbol("foo")
};
var obj2 = JSON.parse(JSON.stringify(obj1));
console.log(obj1) //{x: 1, y: {m: 1}, a: undefined, b: ƒ, c: Symbol(foo)}
console.log(obj2) //{x: 1, y: {m: 1}}
obj2.y.m = 2; //修改obj2.y.m
console.log(obj1) //{x: 1, y: {m: 1}, a: undefined, b: ƒ, c: Symbol(foo)}
console.log(obj2) //{x: 2, y: {m: 2}}

可实现多维对象的深拷贝。

注意：进行JSON.stringify() 序列化的过程中，undefined、任意的函数以及 symbol 值，在序列化过程中会被忽略（出现在非数组对象的属性值中时）或者被转换成 null（出现在数组中时）。

三、es6 扩展运算

let obj = {
    id:'0',
    name:'king',
    sex:'man'
}
let {...obj4} = obj
obj4.name = "king4"
console.log(obj) //{id: "0", name: "king", sex: "man"}
console.log(obj4) //{id: "0", name: "king4", sex: "man"}

四、Object.assign()

Object.assign() 只能实现一维对象的深拷贝。

var obj1 = {x: 1, y: 2}, obj2 = Object.assign({}, obj1);
console.log(obj1) // {x: 1, y: 2}
console.log(obj2) // {x: 1, y: 2}

obj2.x = 2; // 修改 obj2.x
console.log(obj1) // {x: 1, y: 2}
console.log(obj2) // {x: 2, y: 2}

var obj1 = {
    x: 1, 
    y: {
        m: 1
    }
};
var obj2 = Object.assign({}, obj1);
console.log(obj1) // {x: 1, y: {m: 1}}
console.log(obj2) // {x: 1, y: {m: 1}}

obj2.y.m = 2; // 修改 obj2.y.m
console.log(obj1) // {x: 1, y: {m: 2}}
console.log(obj2) // {x: 1, y: {m: 2}}

通用深拷贝方法

简单版

let clone = function (v) {
    let o = v.constructor === Array ? [] : {};
    for(var i in v){
      o[i] = typeof v[i] === "object" ? clone(v[i]) : v[i];
    }
    return o;
}
// 测试
let obj = {
    id:'0',
    name:'king',
    sex:'man'
}
let obj2 = clone(obj)
obj2.name = "king2"
console.log(obj) // {id: "0", name: "king", sex: "man"}
console.log(obj2) // {id: "0", name: "king2", sex: "man"}

let arr3 = [1,2,3,4];
let arr4 = clone(arr3) // [1,2,3,4]
arr3[0] = 5;
console.log(arr3) // [5,2,3,4]
console.log(arr4) // [1,2,3,4]

但上面的深拷贝方法遇到循环引用，会陷入一个循环的递归过程，从而导致爆栈，所以要避免。

let obj1 = {
    x: 1, 
    y: 2
};
obj1.z = obj1;
let obj2 = clone(obj1);
console.log(obj2) 

结果如下：

总结：深刻理解 javascript 的深浅拷贝，可以灵活的运用数组与对象，并且可以避免很多 bug。

文章输出计划

JavaScript 数据结构与算法之美 的系列文章，坚持 3 - 7 天左右更新一篇，暂定计划如下表。

标题	链接
时间和空间复杂度	#29
线性表（数组、链表、栈、队列）	#34
实现一个前端路由，如何实现浏览器的前进与后退 ？	#30
栈内存与堆内存 、浅拷贝与深拷贝	#35
非线性表（树、堆）	精彩待续
递归	精彩待续
冒泡排序	精彩待续
插入排序	精彩待续
选择排序	精彩待续
归并排序	精彩待续
快速排序	精彩待续
计数排序	精彩待续
基数排序	精彩待续
桶排序	精彩待续
希尔排序	精彩待续
堆排序	精彩待续
十大经典排序汇总	精彩待续

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。

7. 最后

文章中的代码已经全部放在了我的 github 上，如果喜欢或者有所启发，欢迎 star，对作者也是一种鼓励。

关注我的公众号，第一时间接收最新的精彩博文。

文章可以转载，但须注明作者及出处，需要转载到公众号的，喊我加下白名单就行了。

参考文章：

JavaScript栈内存和堆内存
JavaScript实现浅拷贝与深拷贝的方法分析
浅拷贝与深拷贝（JavaScript）