队列示例

## 目录 - 队列和栈 - 链表 - 哈希表 - 树 --- > 目前用过的数据结构 - 数组 - 可分为队列和栈等 - 哈希表 - 用来存储`key-value`键值对 ## 队列和栈 ### 队列`Queue` > 「先进先出FIFO」的数组 #### 题目 > 请实现一个餐厅叫号网页 > > - 点击「取号」按钮生成一个号码 > - 点击「叫号」按钮显示请X号就餐 #### 手写队列`Queue` - 首先选择队列`Queue`作为数据结构 - `queue.push()`为入队，`queue.shift()`为出队 - 用`call()来调用` ```JavaScript const divScreen = document.querySelector('#screen') const btnCreateNumber = document.querySelector('#createNumber') const btnCallNumber = document.querySelector('#callNumber') /* 取到当前号码对应的span */ const spanNewNumber = document.querySelector('#newNumber') const spanQueue = document.querySelector('#queue') // 取到当前队列 /* 监听用户取号 ** 声明一个号 n = 0 默认无人排队 ** 声明队列数组 queue */ let n = 0 let queue = [] /* 点击取号时显示当前号码 */ btnCreateNumber.onclick = () => { n += 1 queue.push.call(queue, n) // 将取得的好记录下来 // queue.push(n) spanNewNumber.innerHTML = n // spanQueue.innerText = queue.toString() // spanQueue.innerText = queue.toString() 只能显示字符串，会用逗号连接不美观 1,2,3,4,5 变为字符串格式的[] /* JSON.stringify 将对象变为带有原对象格式的字符串 */ spanQueue.innerText = JSON.stringify(queue) } /* 点击叫号时出队 */ btnCallNumber.onclick = () => { /* 排除叫完号出现 m === undefined */ if (queue.length === 0) { divScreen.innerText = `取号完毕` return; } //const m = queue.shift() const m = queue.shift.call(queue) divScreen.innerText = `请 ${m} 号就餐` spanQueue.innerText = JSON.stringify(queue) // 队列更新，再次打印到span里放到span里 } ``` ```HTML 队列示例

当前号码

当前队列

``` 样式 ```CSS * { box-sizing: border-box; margin: 0; padding: 0; } #screen { border: 1px solid #000; width: 200px; height: 200px; } ``` > 队列：类似数组的结构，只提供入队queue.push(n)，和出队queue.shift()两个操作 [实现示例的仓库](https://github.com/FrankFang/data-structure-1) --- ### 栈`Stack` > 「后进先出LIFO」的数组 #### 栈的例子 - 坐电梯 - JS函数的调用栈`call stack`就是一个栈 - 假设`f1`调用了`f2`，`f2`又调用了`f3` - 那么`f3`结束后应该回到`f2`，`f2`结束后应该回到`f1` #### 栈的代码 ```JavaScript function f1(){let a = 1; return a + f2()} function f2(){let b = 2; return b + f3()} function f3(){let c = 3; return c} f1() ``` #### 画压栈、出栈的过程 > 栈：类似数组的结构，只提供入队queue.push(n)，和出队queue.pop()两个操作 > > 思考：内存图里的栈内存和此处调用栈的关系、是否占据同一块内存 --- ## 链表`Linked List` > 一个链一个，X体蜈蚣 ### 手写链表`Linked List` ```JavaScript let array = [1, 2, 3] array.__proto__ === Array.prototype Array.prototype.__proto__ === Object.prototype // JS原型链是一种链表，JS的每一个对象都是属于链表 /* 可以跳链即将原型重新指向 */ array.__proto__ = Object.prototype array.push // undefined ``` > 实例 ```JavaScript const createList = (value)=>{ return { data: value, next: null } } /* 增加节点 */ const appendList(list, value)=>{ const node = { data: value, nestL null } list.next = node return node } /* 在控制台看数据结构 */ console.log("node") console.log(node) console.log("list") console.log(list) ``` > 合并，缩减代码 ```JavaScript const createList = (value)=>{ return createNode(value) } const appendList(list, value)=>{ const node = createNode(value) list.next = node return node } /* 优化去掉重复代码抽像 */ const createNode = (value)=>{ return { data: value, next: null } } const node2 = appendList(list, 20) const node3 = appendList(list, 30) ``` > 修改`appendList`，使增加的node加到最后一个节点上 ```JavaScript const appendList = (list, value) => { const node = createNode(value); /* 使 x 是最后一个节点 */ let x = list; while (x.next) { // x 非空即不是最后一个节点 x = x.next; } // x.next === null; // x 是最后一个节点 x.next = node; return node; }; ``` > 删除节点的思路 ```JavaScript const createList = (value)=>{ return createNode(value) } const appendList = (list, value) => { const node = createNode(value); /* 使 x 是最后一个节点 */ let x = list; while (x.next) { // x 非空即不是最后一个节点 x = x.next; } // x.next === null; // x 是最后一个节点 x.next = node; return node; }; /* 节点跳链 */ const removeFromList = (list, node)=>{ // 遍历 if(list === node){ // 如果删除的是第1个节点 list = node.next // 第一个节点自动被回收 }else{ // 如果删除的是第2个节点 // 就让第1个节点.next = 第2个节点.next if(list.next === node){ list.next = node.next // 第2个节点自动被回收 }else{ // 开始递归了 // 如果删除的是第3个节点 // 就让第2个节点.next = 第3个节点.next if(list.next.next === node){ (list.next).next = node.next } } } } /* 优化去掉重复代码抽像 */ const createNode = (value)=>{ return { data: value, next: null } } const list = createList(10) const node2 = appendList(list, 20) const node3 = appendList(list, 30) ``` > 用递归或循环来删除节点 ```JavaScript const createNode = (value)=>{ return { data: value, next: null } } const createList = (value)=>{ return createNode(value) } const appendList = (list, value) => { const node = createNode(value); /* 使 x 是最后一个节点 */ let x = list; while (x.next) { // x 非空即不是最后一个节点 x = x.next; } // x.next === null; // x 是最后一个节点 x.next = node; return node; }; /* 用循环实现删除节点 */ const removeFromList = (list, node) => { let x = list; let p = null; // 上一个节点默认是空 while (x !== node) { // x 不等于 node，先记下 x 给 p，让下一个节点赋值给 x p = x; // 先记下 x 给 p x = x.next } // console.log(p === null || p /* x 的上一个节点 */); // console.log(x === node || x === null); p.next = x.next; if (list === node) { // 如果删除的是第一个节点 // list 指向第二个节点 list = node.next //即删除传入的节点 } }; const list = createList(0); const node1 = appendList(list, 10); const node2 = appendList(list, 20); const node3 = appendList(list, 30); const node4 = appendList(list, 40); removeFromList(list, node3); console.log("list"); console.log(list); ``` ### 控制台打断点，debugger > Sources里一步步运行步进代码 ```JavaScript const createNode = (value)=>{ return { data: value, next: null } } const createList = (value)=>{ return createNode(value) } const appendList = (list, value) => { const node = createNode(value); let x = list; while (x.next) { x = x.next; } x.next = node; return node; }; const removeFromList = (list, node) => { debugger; let x = list; let p = null; while (x !== node) { p = x; x = x.next } p.next = x.next; if (list === node) { list = node.next } }; const list = createList(0); const node1 = appendList(list, 10); const node2 = appendList(list, 20); const node3 = appendList(list, 30); const node4 = appendList(list, 40); removeFromList(list, node3); console.log("list"); console.log(list); ``` > 遍历操作节点 `travel` ```JavaScript /* 遍历操作节点 `travel` */ const travelList = (list,fn) => { let x = list; while (x !== null) { fn(x); // 操作节点 x = x.next } }; travelList(list, node => { console.log(node.data); }); ``` > 查找第几个节点 ```JavaScript node = get(index) // 遍历 1 次记个1； // 遍历 index 次返回节点 ``` > `removeFromList` 存在 bug > > 那就是无法删除第一个节点，示例如下 ```JavaScript const list = createList(10); const node = list // node 就是 list 的第一个节点了现在 removeFromList(list, node) // 你会发现 list 没有任何变化 const newList = removeFromList(list, node) // 就算获取返回值也没有用，因为根本就没返回新 list /* Uncaught TypeError: Cannot set property 'next' of null * at removeFromList (:71:12) * at :1:1 * removeFromList @ VM343:71 * (anonymous) @ VM658:1 * null 不存在任何属性也不能添加任何属性 */ ``` > 正确的实现方法为： > > - （P.S. 当然还有其他更优雅的实现方法，比如将头指针改为头结点，不过有点超纲，就不说了） ```JavaScript //list.js const removeFromList = (list, node) => { let x = list; let p = node; // 课堂里将 p 初始化为 null，这里改为 node while (x !== node && x !== null) { // 课堂里忘了对 null 进行处理，如果 node 不在 list 中，x 就可能为 null p = x; x = x.next; } if(x === null){ // 若 x 为 null，则不需要删除，直接 return， false 表示无法删除不在list里的节点 return false }else if(x === p){ // 这说明要删除的节点是第一个节点 p = x.next return p // 如果删除的是第一个节点，那么就要把新 list 的头节点 p 返回给外面，即 newList = removeFromList(list, list) }else{ p.next = x.next; return list // 如果删除的不是第一个节点，返回原来的 list 即可 } }; // 使用方法为 const list = createList(10); const node = list // node 就是 list 的第一个节点了现在 const newList = removeFromList(list, node) // 必须用 newList 获取返回值才能拿到删除了第一个节点的新 list ``` ### 链表代码小结 ```JavaScript /* 创建链表增删改查 */ list = create(value) node = get(index) append(node, value) remove(node) travel(list, fn) ``` ### 链表的变形 #### 双向链表 > 每个节点有一个`previous`指向上一个节点 #### 循环链表 > 最后一个节点的`next`指向头节点 [链表的代码，注意看代码里的注释](https://github.com/FrankFang/data-structure-1/tree/master/src) --- ## 哈希表`key-value pairs` [「哈希表」是什么？有哪些常用的解决冲突（碰撞）的方法？](https://note.youdao.com/) [程序员必须掌握哪些算法？](https://www.zhihu.com/question/23148377) ### 哈希表的难点 - 存的越多，读得越慢 #### 场景 > 假设哈希表 `hash` 里有一万对`key-value`，比如`name:'xxx', age:'18', p1:'property1'...` > > - 如何使得读取`hash['xxx']`速度最快 #### 解决办法 - 不作任何优化，`hash['xxx']`需要遍历所有`key`，复杂度`O(n)`，成本太大 - 对`key`排序，使用二分查找，复杂度`O(log2 n)` - 用字符串对应的`ASCII`码数字做索引，存入数组，复杂度`O(1)` - 项目多的时候，数组下标太大 - 对索引做除法去余数（除以1000，长度为1000的数组）.复杂度`O(1)` - 冲突了就顺延（或叠在一起，“立体”，开链表法） ### 手写哈希表`key-value pairs` ```JavaScript hashTable["yyy"] ``` --- ## 树`tree` > 一个链多个，链表的扩充 ### 画图 ### 实际使用场景 - 省市区 - 层级结构 - 网页节点`DOM` > 控制台`Elements`里按`Alt`收缩所有节点 ### 代码手写 ```JavaScript const createTree = value => { return { data: value, children: null } }; /* 增加节点 */ const addChild = (node, value) => { // 每次在一个节点上加一个孩子（值） const newNode = { data: value, children: null }; /* 父节点有可能是空也有可能是数组保底值 */ node.children = node.children || []; node.children.push(newNode); /* 将加了子节点的新节点返回 */ return newNode }; const tree = createTree(10); const node2 = addChild(tree, 20); const node3 = addChild(tree, 30); addChild(tree, 40); addChild(tree, 50); addChild(node2, 201); addChild(node2, 202); addChild(node2, 203); addChild(node2, 204); console.log(tree); ``` > 遍历树的一种实现 ```JavaScript // 紧接前面的代码 /* 删除节点的过程中，必须先遍历节点，先确保要删除的节点存在于当前父节点中 */ const travelTree = (tree, fn) => { // 所谓遍历，就是把每一个节点的值打出来 // debugger; /* 首先打印 tree上的每一个值，先遍历根节点 */ fn(tree); /* 其次再打印 tree上的每一个节点的值，可用 forEach遍历数组 children * // children 如果为空就不应该被遍历所以要加判断 * */ if (!tree.children) { return; } for (let i = 0; i < tree.children.length; i++) { travelTree(tree.children[i], fn)// 把子节点作为一个树，再遍历一下 } }; /* 为打断点 */ const fn = node => { // debugger; console.log(node.data); }; travelTree(tree, fn); ``` - 先打出根，再把左边打出来，再打出右边 - 即先根遍历 > 删除节点思路 - 先找到被要删除`children`的属性所在的数组 - 从保存属性的数组那里删除节点 - 哪个节点保存了要删除节点的属性 - 找到这个节点的父亲（找子节点容易找父节点难） - 用类似双向链表，在属性中记录父节点`parent: node;` ```JavaScript const createTree = value => { return { data: value, children: null, /* 用类似双向链表，在属性中记录父节点 */ parent: null }; }; /* 增加节点 */ const addChild = (node, value) => { // 每次在一个节点上加一个孩子（值） const newNode = { data: value, children: null, /* 用类似双向链表，在属性中记录父节点 */ parent: node }; /* 父节点有可能是空也有可能是数组保底值 */ node.children = node.children || []; node.children.push(newNode); /* 将加了子节点的新节点返回 */ return newNode }; ``` 实现查找节点 ```JavaScript /* 抽象一个查找函数 find() * 判断一棵树里是否有要查找的节点 * 即查找这棵树的子树里是否存在要查找的节点 * 当前节点是否匹配子节点里遍历查找 * */ const find = (tree, node) => { if (tree === node) { // 找到当前节点即为所查找的 return tree; } else if (tree.children) { // 如果存在子树遍历子树节点 for (let i = 0; i < tree.children.length; i++) { const result = find(tree.children[i], node); if (result) { // 返回子树中查找到的节点 return result } } return undefined // 未找到 } else { return undefined // 未找到 } }; console.log('找到了'); console.log(find(tree, node2)); ``` 实现删除节点（需要遍历） ```JavaScript /* 删除节点 */ const removeNode = (tree, node) => { /* 找到下标找到兄弟节点 * 要知道删除的节点在兄弟节点里的下标 * 数组仅支持按下标删除 * */ const siblings = node.parent.children; let index = 0; for (let i = 1; i < siblings.length; i++) { if (siblings[i] === node) { index = i } } // 得到要删除节点的下标index siblings.splice(index, 1) }; console.log(tree); removeNode(tree, node5); console.log(tree); ``` - 注意chrome控制台点开刷新对象的bug - 删除一个节点的本质就是删除这个节在树里的地址 - 不能把`sibling[i] = null`，树中还存在地址，任然占位 --- 树的小结 ```JavaScript let tree = createTree(value) let node = createNode(value) addChild(tree, node) removeChild(node1, node2) travel(tree) ``` > 遍历一棵树，简单的递归 --- ·未完待续· --- #### 参考链接 [2020版前端体系课【方方】之【算法与数据结构】数据结构(上)](https://xiedaimala.com/tasks/23258d07-cb35-4f79-95ad-9d3abdaf6b1e) [数据结构（上）.pdf](https://static.xiedaimala.com/xdml/file/3ac7c224-c23d-491f-84b5-4fabfbeab9b8/2019-10-9-22-25-26.pdf) #### 相关文章 - 无 --- - 作者： Joel - 文章链接： - [版权声明](http://xmasuhai.xyz/posts/版权声明链接/) - 非自由转载-非商用-非衍生-保持署名 --- ---

【算法与数据结构03】数据结构（上）