提起算法很多CS毕业的人都不会陌生，但是不管你是在学校理论知识学的如何扎实还是在学校中有参加比赛的经历(ACM等)，但是到了工作中因为没有实际的应用场景或者说应用场景很少，导致一些原本顺手拈来的知识点和操作都感到很生疏。
同时，由于本人现在专职于前端工作（原来是前后端都做），很多的应用场景都没有涉及算法的身影。这也是前端在技术鄙视链的顶端。其实前端也是有很多顶级的算法思路和实现。只是别人帮你实现了，你直接就用。
所以我始终相信一个信条：
实践出真知，温故而知新
所以，接下来的文档，将一起汇总一下我跟着极客时间的数据结构与算法之美的课程来一起回顾和总结一下(内容大部分是极客时间的，但是有一些也是我查询相关资料来进行比对和校验的)。
该课程只是个人的学习文档和见解，如有不对和理解有偏差的地方，请不吝赐教。
复杂度
渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低
从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )
数组
说到数组大家想必在开发中，是接触最多的一类数量类型，也是最常见的一类线性表。
线性表的分类
静态类型语言（java,c++）
一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
动态类型语言(javaScript)
As JavaScript arrays are implemented as hash-maps（哈希表） or dictionaries(字典) and not contiguous.（非连续）
链表
它并不需要一块连续的内存空间，它通过指针将一组零散的内存块串联起来使用
内存分配
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的结点
单链表
其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
循环链表
循环链表的尾结点指针是指向链表的头结点
双向链表
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
链表 VS 数组性能大比拼
数组中随机访问，指的是按下标的随机访问
js实现一个链表(满足CRUD)
大致的结构如下：
size和head为LinkedList构造函数私有属性，size记录链表中有多少个节点，head指向链表的头结点
单向链表的代码实现
/** * 自定义链表：对外公开的方法有 * append(element) 在链表最后追加节点 * insert(index, element) 根据索引index, 在索引位置插入节点 * remove(element) 删除节点 * removeAt(index) 删除指定索引节点 * removeAll(element) 删除所有匹配的节点 * set(index, element) 根据索引，修改对应索引的节点值 * get(index) 根据索引获取节点信息 * indexOf(element) 获取某个节点的索引位置 * clear() 清空所有节点 * length() 返回节点长度 * print() 打印所有节点信息 * toString() 打印所有节点信息，同print * */ const LinkedList = function(){ let head = null; let size = 0; //记录链表元素个数 //Node模型 function LinkNode(element, next){ this.element = element; this.next = next; } //元素越界检查, 越界抛出异常 function outOfBounds(index){ if (index < 0 || index >= size){ throw("抱歉，目标位置不存在！"); } } //根据索引，获取目标对象 function node(index){ outOfBounds(index); let obj = head; for (let i = 0; i < index; i++){ obj = obj.next; } return obj; } //新增一个元素 function append(element){ if (size == 0){ head = new LinkNode(element, null); } else{ let obj = node(size-1); obj.next = new LinkNode(element, null); } size++; } //插入一个元素 function insert(index, element){ if (index == 0){ head = new LinkNode(element, head); } else{ let obj = node(index-1); obj.next = new LinkNode(element, obj.next); } size++; } //修改元素 function set(index, element){ let obj = node(index); obj.element = element; } //根据值移除节点元素 function remove(element){ if (size < 1) return null; if (head.element == element){ head = head.next; size--; return element; } else{ let temp = head; while(temp.next){ if (temp.next.element == element){ temp.next = temp.next.next; size--; return element; } else{ temp = temp.next; } } } return null; } //根据索引移除节点 function removeAt(index){ outOfBounds(index); let element = null; if (index == 0){ element = head.element; head = head.next; } else{ let prev = node(index-1); element = prev.next.element; prev.next = prev.next.next; } size--; return element; } //移除链表里面的所有匹配值element的元素 function removeAll(element){ let virHead = new LinkNode(null, head); //创建一个虚拟头结点，head为次节点 let tempNode = virHead, ele = null; while(tempNode.next){ if (tempNode.next.element == element){ tempNode.next = tempNode.next.next; size--; ele = element; } else{ tempNode = tempNode.next; } } //重新赋值 head = virHead.next; return ele; } //获取某个元素 function get(index){ return node(index).element; } //获取元素索引 function indexOf(element){ let obj = head, index = -1; for (let i = 0; i < size; i++){ if (obj.element == element){ index = i; break; } obj = obj.next; } return index; } //清除所有元素 function clear(){ head = null; size = 0; } //属性转字符串 function getObjString(obj){ let str = ""; if (obj instanceof Array){ str += "["; for (let i = 0; i < obj.length; i++){ str += getObjString(obj[i]); } str = str.substring(0, str.length - 2); str += "], " } else if (obj instanceof Object){ str += "{"; for (var key in obj){ let item = obj[key]; str += "\"" + key + "\": " + getObjString(item); } str = str.substring(0, str.length-2); str += "}, " } else if (typeof obj == "string"){ str += "\"" + obj + "\"" + ", "; } else{ str += obj + ", "; } return str; } function toString(){ let str = "", obj = head; for (let i = 0; i < size; i++){ str += getObjString(obj.element); obj = obj.next; } if (str.length > 0) str = str.substring(0, str.length -2); return str; } //打印所有元素 function print(){ console.log(this.toString()) } //对外公开方法 this.append = append; this.insert = insert; this.remove = remove; this.removeAt = removeAt; this.removeAll = removeAll; this.set = set; this.get = get; this.indexOf = indexOf; this.length = function(){ return size; } this.clear = clear; this.print = print; this.toString = toString; } ////测试 // let obj = new LinkedList(); // let obj1 = { title: "全明星比赛", stores: [{name: "张飞vs岳飞", store: "2:3"}, { name: "关羽vs秦琼", store: "5:5"}]}; // // obj.append(99); // obj.append("hello") // obj.append(true) // obj.insert(3, obj1); // obj.insert(0, [12, false, "Good", 81]); // obj.print(); // console.log("obj1.index: ", obj.indexOf(obj1)); // obj.remove(0); // obj.removeAll(obj1); // obj.print(); ////测试2 console.log("\n\n......test2.....") var obj2 = new LinkedList(); obj2.append(8); obj2.insert(1,99); obj2.append('abc'); obj2.append(8); obj2.append(false); obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8); obj2.print(); obj2.removeAll(8); //删除所有8 obj2.print(); 复制代码
链表的简单算法(反转单向链表)
/** * * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let prev = null; let curr = head;//定义"哨兵" while (curr != null) { let nextTemp = curr.next;//暂存剩余链表 curr.next = prev;//与剩余链表断开连接，并将指向变更 prev = curr;//两个节点交互位置 curr = nextTemp;//指针下移 } return prev; }; 复制代码
栈
关于栈，有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。
从栈的操作特性上来看
栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。（这也仅仅针对的是C,C++,JAVA等静态类型语言）
函数调用栈
操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
function main() { let a = 1; let ret = 0; let res = 0; ret = add(3, 5); res = a + ret; console.log(`处理结果为 ${res}`); reuturn 0; } function add( x, y) { let sum = 0; sum = x + y; return sum; } 复制代码
图中显示的是，在执行到 add() 函数时，函数调用栈的情况。
栈在表达式求值中的应用
实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
将 3+5*8-6 这个表达式的计算过程画成了一张图,如下：
实现浏览器的前进、后退功能
使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。
入栈操作
- 比如顺序查看了 a，b，c 三个页面，依次把 a，b，c 压入栈，这个时候，两个栈的数据就是这个样子：
2.当你通过浏览器的后退按钮，从页面 c 后退到页面 a 之后，依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y。这个时候，两个栈的数据就是这个样子：
如此反复如上操作，就可以简单解释浏览器回退和前进的操作步骤。
内存中的堆栈vs数据结构堆栈
内存中的堆栈和数据结构堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。
内存空间
内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。
- 代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。
- 静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。
- 栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
- 堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。
队列
队列跟栈一样，也是一种操作受限的线性表数据结构。
顺序队列和链式队列
队列跟栈一样，也是一种抽象的数据结构。它具有先进先出的特性，支持在队尾插入元素，在队头删除元素。
队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
代码实现一个顺序队列
// 用数组实现的队列 const ArrayQueue=function(){ // 数组：items，数组大小：n let items =[]; let n = 0; // head 表示队头下标，tail 表示队尾下标 let head = 0; let tail = 0; // 申请一个大小为 capacity 的数组 function createArrayQueue(capacity) { items = new Array(capacity); n = capacity; } // 入队操作，将 item 放入队尾 function enqueue(item) { // tail == n 表示队列末尾没有空间了 if (tail == n) { // tail ==n && head==0，表示整个队列都占满了 if (head == 0) return false; // 数据搬移 for (int i = head; i < tail; ++i) { items[i-head] = items[i]; } // 搬移完之后重新更新 head 和 tail tail -= head; head = 0; } items[tail] = item; ++tail; return true; } // 出队 function dequeue() { // 如果 head == tail 表示队列为空 if (head == tail) return null; // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了 let ret = items[head]; ++head; return ret; } this.createArrayQueue = createArrayQueue; this.enqueue = enqueue; this.dequeue = dequeue; } 复制代码
循环队列
用数组实现的队列，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。
想要避免数据搬移，可以用循环队列来处理。
我们可以看到，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：
通过这样的方法，我们成功避免了数据搬移操作。
代码实现一个循环队列
const CircularQueue = function { // 数组：items，数组大小：n let items; let n = 0; // head 表示队头下标，tail 表示队尾下标 let head = 0; let tail = 0; // 申请一个大小为 capacity 的数组 function createCircularQueuee(capacity) { items = new Array(capacity); n = capacity; } // 入队 function enqueue(item) { // 队列满了 if ((tail + 1) % n == head) return false; items[tail] = item; tail = (tail + 1) % n; return true; } // 出队 function dequeue() { // 如果 head == tail 表示队列为空 if (head == tail) return null; String ret = items[head]; head = (head + 1) % n; return ret; } this.createCircularQueuee = createCircularQueuee; this.enqueue = enqueue; this.dequeue = dequeue; } 复制代码
未完待续 续集：
