JS中的堆栈-内存的分配和使用

• 堆是动态分配内存，内存大小不一，也不会自动释放
• 栈是自动分配相对固定大小的内存空间，并由系统自动释放

JS的数据类型分为基本数据类型（也称为原始数据类型）和复杂数据类型（引用数据类型）
原始数据类型又分为string、number、boolean、undefined和null（ES6中新增Symbol），这些都是直接按值存储在栈中的，每种类型数据占用的内存空间大小是确定的，并有系统自动分配和释放，这样带来的好处是内存可以及时得到回收，相对于堆来说，更加容易管理内存空间

引用数据类型又分为对象、数组和函数等，这些是通过拷贝和new出来的，这样的数据存储于堆中，其实是引用类型的数据的地址指针是存储在栈中的，当我们想要访问值时，需要先从栈中获取对象的地址指针，然后通过地址指针找到堆中的所需要的数据

栈，线性结构，后进先出，便于管理；堆，一个混乱、杂乱五章，方面存储和开辟空间

深拷贝和浅拷贝

赋值

定义：将某一数值或对象赋给某个变量的过程，分为下面两个部分：

• 基本数据类型：赋值，赋值后两个变量互不影响
• 引用数据类型：赋址：两个变量具有相同的引用，指向同一个对象，相互之间有影响

浅拷贝

1. 定义：创建一个新对象，这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型，拷贝的是就是基本类型的值；如果属性是引用类型，拷贝的就是内存地址，所有如果其中一个对象改变了这个地址，就会影响到另外一个对象

2. 使用场景：

    	- `Object.assign()`：该方法用于将所有可枚举属性的值从一个或多个源对象复制到目标对象，返回目标对象- 展开语法`Spread`：扩展运算符...和`Object.assign()`效果是一样的- `Array.prototype.slice()`：返回一个新的数组对象，由一个`begin`和`end`（不包括`end`）决定的原数组的浅拷贝，原始数组不会改变
   

深拷贝

1. 定义：会拷贝所有的属性，并拷贝属性指向的动态分配的内存。当对象和它所引用的对象一起拷贝时即发生深拷贝，深拷贝相比于浅拷贝速度较慢并且花销较大，拷贝前后两个对象互不影响

2. 使用场景：

    	`JSON.parse(JSON.stringify(object))`：完全改变变量1对变量2的影响，但是该方法会有一下几个问题。- 会忽略`undefined` - 会忽略`symbol`- 不能序列化函数- 不能解决循环引用的对象- 不能正确处理`new Date()`- 不能处理正则
   

- -	和原数据是否指向同一对象	第一层数据为基本数据类型	原数据中包含子对象
赋值	是	改变会使原数据一同改变	改变会使原数据一同改变
浅拷贝	否	改变不会使原数据一同改变	改变会使原数据一同改变
深拷贝	否	改变不会使原数据一同改变	改变不会使原数据一同改变

数据结构

经典的数据结构就那么几种，list、stack、queue、linkedList、dictionary、hash、set、tree、graph等等

数组是基础，然后为数组封装好一个List构造函数，增加长度、插入、删除、索引、遍历等工具接口，这样就构造了一个列表

列表（List），是计算机中一种常见的数据结构，是一组有序的数据，每个列表中的数据项称为元素，其中元素可以是任意数据类型

栈（Stack），又叫堆栈，是和列表类似的一种数据结构，但是更高效，因为栈内的元素只能通过列表的一端访问，称为栈顶，数据只能在栈顶添加和删除，具有后进先出的特点（LIFO，last in first out）

队列（Queue），与栈不同，它也是一种特殊的列表，队列只能在队尾插入元素，在队首删除元素，具有先进先出（FIFO，first in first out）的特点

链表（Linked-list），前面说到的栈和队列其实都是列表的一种，底层存储的数据结构都是数组，除了其外，还有链表这种数据结构，链表是一组节点组成的集合，每个节点都使用一个对象的引用来指向它的后一个节点。指向另一节点的引用讲做链如下图，链表又分为单向链表、双向链表和循环链表（单双向）

字典（Dictionary），是一种以键-值对形式存储数据的数据结构，其实，JavaScript 中的 Object 类就是以字典的形式设计的

集合（set），是由一组无序但彼此之间又有一定关系性的成员构成，每个成员在集合中只能出现一次，不同于我们之前说的字典，链表之类的，它是一种包含了不同元素的数据结构(集合中的元素称为成员)，从其定义中我们可以看出它具有两个很重要的特征：首先，集合中的成员是无序的；其次，集合中的成员是不相同的，即集合中不存在相同的成员

排序搜索算法

排序算法

• 冒泡排序：比较任何两个相邻的项，如果第一个比第二个大，则交换它们；元素项向上移动至正确的顺序，好似气泡上升至表面一般，因此得名
• 选择排序：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，以此循环，直至排序完毕
• 插入排序：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，此算法适用于少量数据的排序，时间复杂度为 O(n^2)
• 归并排序：将原始序列切分成较小的序列，只到每个小序列无法再切分，然后执行合并，即将小序列归并成大的序列，合并过程进行比较排序，只到最后只有一个排序完毕的大序列，时间复杂度为 O(n log n)
• 快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行上述递归排序，以此达到整个数据变成有序序列，时间复杂度为 O(n log n)

搜索算法

• 顺序搜索：让目标元素与列表中的每一个元素逐个比较，直到找出与给定元素相同的元素为止，缺点是效率低下
• 二分搜索：在一个有序列表，以中间值为基准拆分为两个子列表，拿目标元素与中间值作比较从而再在目标的子列表中递归此方法，直至找到目标元素

其他

• 贪心算法：在对问题求解时，不考虑全局，总是做出局部最优解的方法
• 动态规划：在对问题求解时，由以求出的局部最优解来推导全局最优解
• 复杂度概念：一个方法在执行的整个生命周期，所需要占用的资源，主要包括：时间资源、空间资源