学习JavaScript数据结构与算法 2015.10.pdf
《学习JavaScript数据结构与算法第3版》高清中文PDF.pdf
《Learning JavaScript Data Structures and Algorithms3rd》英文PDF.pdf
源码.zip: https://github.com/loiane/javascript-datastructures-algorithms

环境

launch.json

  1. {
  2.     // Use IntelliSense to learn about possible attributes.
  3.     // Hover to view descriptions of existing attributes.
  4.     // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
  5.     "version": "0.2.0",
  6.     "configurations": [
  7.       {
  8.         "type": "chrome",
  9.         "request": "launch",
  10.         "name": "Chrome",
  11.         "url": "http://localhost:8092/",
  12.         "webRoot": "${workspaceRoot}"
  13.       },
  14.       {
  15.         "type": "node",
  16.         "request": "launch",
  17.         "name": "Mocha JS",
  18.         "program": "${workspaceRoot}/node_modules/mocha/bin/_mocha",
  19.         "args": [
  20.           "-u",
  21.           "tdd",
  22.           "--timeout",
  23.           "999999",
  24.           "--compilers",
  25.           "js:babel-core/register",
  26.           "--colors",
  27.           "${workspaceRoot}/test/js/**/*.spec.js"
  28.         ],
  29.         "internalConsoleOptions": "openOnSessionStart"
  30.       },
  31.       {
  32.         "type": "node",
  33.         "request": "launch",
  34.         "name": "Mocha TS",
  35.         "program": "${workspaceRoot}/node_modules/mocha/bin/_mocha",
  36.         "args": [
  37.           "-u",
  38.           "tdd",
  39.           "--timeout",
  40.           "999999",
  41.           "-r",
  42.           "ts-node/register",
  43.           "--colors",
  44.           "${workspaceRoot}/test/ts/**/**/*.spec.ts"
  45.         ],
  46.         "protocol": "auto",
  47.         "internalConsoleOptions": "openOnSessionStart"
  48.       }
  49.     ]
  50. }

settings.json

  1. {
  2.     "typescript.tsdk": "node_modules/typescript/lib"
  3. }

tasks.json

  1. {
  2.     // See https://go.microsoft.com/fwlink/?LinkId=733558
  3.     // for the documentation about the tasks.json format
  4.     "version": "2.0.0",
  5.     "tasks": [
  6.         {
  7.             "type": "npm",
  8.             "script": "go",
  9.             "group": {
  10.                 "kind": "build",
  11.                 "isDefault": true
  12.             }
  13.         },
  14.         {
  15.           "type": "npm",
  16.           "script": "dev",
  17.           "group": {
  18.               "kind": "test",
  19.               "isDefault": true
  20.           }
  21.       }
  22.     ]
  23. }

检查在各个浏览器中哪些 JS 特性可用

ES2015(ES6):http://kangax.github.io/compat-table/es6/
ES2016+:http://kangax.github.io/compat-table/es2016plus/

Chrome 开发开启支持ESnext：chrome://flags/#enable-javascript-harmony

ESM：http://caniuse.com/#feat=es6-module

  1. <script type="module" src="17-ES2015-ES6-Modules.js"></script> // 在浏览器中使用 import 关键字
  2. <script nomodule src="./lib/17-ES2015-ES6-Modules-bundle.js"></script> // 保证不支持ESM的浏览器向后兼容

TS

文档：https://www.typescriptlang.org/docs/handbook/release-notes/typescript-3-8.html
在线编辑器：https://www.typescriptlang.org/play/index.html
js 文件对代码进行错误及类型检测

  1. // @ts-check

数组

delete numbers[0] 等同于 numbers[0] = undefined


类型数组则用于存储单一类型的数据
为了保证元素排列有序，会占用更多的内存空间

栈

后进先出（LIFO），新元素都靠近栈顶，旧元素都接近栈底

栈也被用在编程语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录 (浏览器的返回按钮)

  • 用数组来保存栈里的元素
  • 对元素的插入和删除功能进行限制，使其遵循LIFO
  • 实现以下方法
    • push(element(s)): 添加一个(或几个)新元素到栈顶
  • pop(): 移除栈顶的元素，同时返回被移除的元素
  • peek(): 返回栈顶的元素，不对栈做任何修改(该方法不会移除栈顶的元素，仅仅返回它)
  • isEmpty(): 如果栈里没有任何元素就返回 true，否则返回 false
  • clear(): 移除栈里的所有元素

  • size(): 返回栈里的元素个数。该方法和数组的 length 属性很类似。

    1.                                   <br />                                           <br />                                           
    1. class Stack {
    2. constructor() {
    3. this.items = []
    4. }
    5. push = element => (
    6.  this.items.push(element)
    7. )
    8. pop = element => (
    9.  this.items.pop(element)
    10. )
    11. peek = element => (
    12.  this.items[this.items.length - 1]
    13. )
    14. isEmpty = () => (
    15.  this.items.length === 0
    16. )
    17. size = () => (
    18.  this.items.length
    19. )
    20. clear = () => {
    21.  this.items = []
    22. }
    23. toString = () => (
    24.  this.items.toString()
    25. )
    26. }
  1. const stack = new Stack();
  2. stack.push(5)
  3. stack.push(8)
  4. console.log(stack.peek())
  5. stack.push(12)
  6. console.log(stack.size())
  7. console.log(stack.isEmpty())
  8. stack.pop()
  9. console.log(stack.size())

以对象形式实现：除了 toString 方法，我们创建的其他方法的复杂度均为 O(1)，代表我们可以 直接找到目标元素并对其进行操作(push、pop 或 peek)。

  1. class Stack {
  2.   constructor() {
  3.     this.count = 0;
  4.     this.items = {};
  5.   }
  6.   push= element => {
  7.     this.items[this.count] = element;
  8.     this.count++;
  9.     return element;
  10.   }
  11.   size = () => this.count
  12.     isEmpty = () => this.count === 0
  13.     pop = () => {
  14.     if(this.isEmpty()) return undefined;
  15.     this.count--;
  16.         const result = this.items[this.count]
  17.       delete this.items[this.count]
  18.         return result;
  19.   }
  20.   peek = () => {
  21.     if(this.isEmpty()) return undefined;
  22.     return this.items[this.count - 1];
  23.   }
  24.   clear = () => {
  25.     this.items = {};
  26.     this.count = 0;
  27.   }
  28.   toString = () => {
  29.     if(this.isEmpty()) return '';
  30.     let objString = this.items[0];
  31.     for(let i = 1; i < this.count; i ++) {
  32.       objString = `${objString}, ${this.items[i]}`;
  33.     }
  34.     return objString;
  35.   }
  36. }

ES2015 类是基于原型的。尽管基于原型 的类能节省内存空间并在扩展方面优于基于函数的类，但这种方式不能声明私有属性(变量)或 方法。

JavaScript 实现私有属性

  • 在属性名称之前加上一个下划线(_)
  • 限定作用域 Symbol 实现类: Symbol是不可变的，可用作对象的属性
  • WeakMap 实现类
  • 添加#作为前缀来声明私有属性的类属性提案

Symbol 实现类

  1. const items = Symbol('stackItems')
  2. class Stack {
  3.   constructor() {
  4.     this[_items] = []
  5.   }
  6.   // 栈的方法
  7.   push = element => (
  8.     this[_items].push(element)
  9.   )
  10. }
  1.                                        <br />                                           <br />                                           
  1. const stack = new Stack()
  2. stack.push(0)
  3. stack.push(1)
  4. let objectSymbols = Object.getOwnPropertySymbols(stack)
  5. console.log(objectSymbols.length)
  6. console.log(objectSymbols[0])
  7. stack[objectSymbols[0]].push(1)
  8. stack.print()

WeakMap 实现类

  1. const items = new WeakMap(); // WeakMap 可以存储键值对，其中键是对象
  2. class Stack {
  3.   constructor() {
  4.     _items.set(this, [])
  5.   }
  6.   push = element => {
  7.     const s = items.get(this)
  8.     return s.push(element)
  9.   }
  10.   pop = () => {
  11.     const s = items.get(this)
  12.     return s.pop()
  13.   }
  14. }

类属性提案

  1. class Stack {
  2.   #count = 0
  3.   #items = 0
  4. }

十进制转二进制

  1. function decimaToBinary(decNumber) {
  2.   const remStack = new Stack()
  3.   let number = decNumber
  4.   let rem;
  5.   let binaryString = ''
  6.   while(number > 0) {
  7.     rem = Math.floor(number % 2)
  8.     remStack.push(rem)
  9.     number = Math.floor(number / 2)
  10.   }
  11.   while(number === 0) {
  12.     binaryString += remStack.pop().toString
  13.   }
  14.   return binaryString
  15. }
  1. console.log(decimaToBinary(233))
  2. console.log(decimaToBinary(19))
  3. console.log(decimaToBinary(1000))

进制转换
十进制转二进制：余数是0或1
十进制转八进制：余数是0-7
十进制转十六进制：余数是0-9，A-F
十进制转三十六进制：余数是0-9，A-Z

  1. function decimaToBinary(decNumber, base) {
  2.   const remStack = new Stack()
  3.   const digits = ‘0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ’；
  4.   let number = decNumber
  5.   let rem;
  6.   let binaryString = ''
  7.   if (!(base>2 || base < 36)) return '';
  8.   while(number > 0) {
  9.     rem = Math.floor(number % base)
  10.     remStack.push(rem)
  11.     number = Math.floor(number / 2)
  12.   }
  13.   while(number === 0) {
  14.     binaryString += digits[remStack.pop()].toString
  15.   }
  16.   return binaryString
  17. }

队列

先进先出

  1. class Queue {
  2.   constructor() {
  3.     this.count = 0;
  4.     this.lowestCount = 0;
  5.     this.items = {};
  6.   }
  7.   enqueue = element => {
  8.     this.items[this.count] = element;
  9.     this.count++;
  10.     return element;
  11.   }
  12.   dequeue = () => {
  13.     if (!this.items[this.lowestCount]) 
  14.       return;
  15.     const result = this.items[this.lowestCount];
  16.     delete this.items[this.lowestCount];
  17.     this.lowestCount++;
  18.     return result;
  19.   }
  20.   peek = () => {
  21.     if (this.isEmpty) 
  22.       return void 0;
  23.     return this.items[this.lowestCount];
  24.   }
  25.   isEmpty = () => this.count === this.lowestCount
  26.   size = () => this.count - this.lowestCount
  27.   clear = () => {
  28.     this.count = 0;
  29.     this.lowestCount = 0;
  30.     this.items = {};
  31.   }
  32.   toString = () => {
  33.     if (this.isEmpty()) 
  34.       return '';
  35.     let objString = `${this.items[this.lowestCount]}`;
  36.     for (let i = this.lowestCount + 1; i < this.count; i++) {
  37.       objString = `${objString},${this.items[i]}`;
  38.     }
  39.     return objString;
  40.   }
  41. }
  1. const queue = new Queue()
  2. console.log(queue.isEmpty())
  3. queue.enqueue('John')
  4. queue.enqueue('Jack')
  5. console.log(queue.toString())
  6. queue.enqueue('Camila')
  7. console.log(queue.toString())
  8. console.log(queue.size())
  9. console.log(queue.isEmpty())
  10. queue.dequeue()
  11. queue.dequeue()
  12. console.log(queue.toString())

双端队列

是一种允许从前端和后端添加和移除元素的特殊队列

  1. class Deque {
  2.   constructor() {
  3.     this.count = 0;
  4.     this.lowestCount = 0;
  5.     this.items = {};
  6.   }
  7.   addFront = element => {
  8.     if(this.isEmpty()){
  9.       this.addBack(element)
  10.     } else (this.lowestCount > 0) {
  11.       this.lowestCount--;
  12.       this.items[this.lowestCount] = element
  13.     } else {
  14.       // this.lowestCount === 0
  15.       for(let i=count;i>0;i--) {
  16.         this.items[i]= this.items[i-1]
  17.       }
  18.       this.lowestCount = 0;
  19.       this.items[0] = element;
  20.       this.count++;
  21.     }
  22.   }
  23.   addBack = element => {
  24.     this.items[this.count] = element;
  25.     this.count++;
  26.     return element;
  27.   }
  28.   removeFront = () => {
  29.     if (!this.items[this.lowestCount]) 
  30.       return;
  31.     const result = this.items[this.lowestCount];
  32.     delete this.items[this.lowestCount];
  33.     this.lowestCount++;
  34.     return result;
  35.   }
  36.   removeBack = () => {
  37.   }
  38.   peekFront = () => {
  39.     if (this.isEmpty) return void 0;
  40.     return this.items[this.lowestCount];
  41.   }
  42.   peekBack = () => {
  43.     if (this.isEmpty) return void 0;
  44.     return this.items[this.count - 1];
  45.   }
  46.   isEmpty = () => this.count === this.lowestCount
  47.   size = () => this.count - this.lowestCount
  48.   clear = () => {
  49.     this.count = 0;
  50.     this.lowestCount = 0;
  51.     this.items = {};
  52.   }
  53.   toString = () => {
  54.     if (this.isEmpty()) 
  55.       return '';
  56.     let objString = `${this.items[this.lowestCount]}`;
  57.     for (let i = this.lowestCount + 1; i < this.count; i++) {
  58.       objString = `${objString},${this.items[i]}`;
  59.     }
  60.     return objString;
  61.   }
  62. }

击鼓传花

  1. function hotPotato(list, num){
  2.   const queue = new Queue();
  3.   const elimitatedList = [];
  4.   for (let i = 0; i < list.length; i++) {
  5.     queue.enqueue(list[i])
  6.   }
  7.   while(queue.size > 1){
  8.     for (let i = 0; i < num; i++) {
  9.             queue.enqueue(queue.dequeue());
  10.     }
  11.     elimitatedList(queue.dequeue());      
  12.   }
  13.   return {
  14.     elimitated: elimitatedList,
  15.     winner: queue.dequeue()
  16.   }
  17. }

回文检查器

回文是正反都能读通的单词、词组。
方法一：将字符串反向排列并检查它和原字符串是否相同。
方法二：双端队列的两端字符相同

  1. function palindromeChecker(str){
  2.   if (!str || str.length === 0) return false;
  3.   const deque = new Deque();
  4.   const lowerStr = str.toLocaleLowerCase().split(' ').join('');// 去掉所有的空格
  5.   let isEqual = true;
  6.   let firstChar;
  7.   let lastChar;
  8.   for(let i = 0; i<lowerStr.length; i++){
  9.     deque.addBack(lowerStr.charAt(i))
  10.   }
  11.   while(deque.size() > 1 && isEqual) {
  12.     firstChar=deque.removeFront();
  13.     lastChar=deque.removeBack();
  14.     isEqual= firstChar === lastChar
  15.   }
  16.   return isEqual;
  17. }

链表

动态数据结构，可以随意添加或移除项，它会按需扩容。有序的元素集合，不同于数组，链表中的元素在内存中并不是连续放置的，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。

  1. class Node {
  2.   constructor(element){
  3.     this.element = element;
  4.     this.next = undefined;
  5.   }
  6. }
  7. function defaultEquals(a, b) {
  8.   return a === b;
  9. }
  1. class LinkedList {
  2.   constructor(equalsFn = defaultEquals){
  3.     this.count = 0;
  4.     this.head = undefined;
  5.     this.equalsFn = equalsFn
  6.   }
  7.   push = element => {
  8.     const node = new Node(element);
  9.     let current;
  10.     if (this.head == null) {
  11.       // 向链表添加第一个元素
  12.       this.head = node;
  13.     } else {
  14.       // 向链表追加一个元素
  15.       current = this.head; 
  16.       // 链表只有第一个元素的引用，因此需要循环访问链表，直到找到最后一项
  17.       while (current.next !== null) { // 链表的最后一个节点的下一个元素始终是 undefined 或 null
  18.         current = current.next; // 向前移动指针
  19.       }
  20.       // 将其next赋为新元素，建立链接
  21.       current = current.next;
  22.     }
  23.     this.count++;
  24.   }
  25.   insert = (element, position) => {}
  26.   // 迭代列表直到到达目标索引
  27.   getElementAt = index => {
  29.   }
  30.   // 根据元素的值移除元素
  31.   remove = element => {}
  32.   indexOf = element => {}
  33.   // 从特定位置移除元素
  34.   removeAt = index => {
  35.     // 检查越界值
  36.     if(index >= 0 && index < this.count) {
  37.       let current = this.head;
  38.       if () {
  39.         // 移除第一项
  40.         this.head = current.next;
  41.       } else {
  42.         // 移除其它项
  43.         let previous;
  44.         // 迭代链表的节点，直到到达目标位置
  45.         for (let i = 0; i < index; i++) {
  46.           previous = current;
  47.           current = current.next;
  48.         }
  49.         //将previous 与 current 的下一项链接起来，跳过 current，从而移除它
  50.         previous.next = current.next;
  51.       }
  52.       this.count--;
  53.       return current.element;
  54.     } else {
  55.       return undefined;
  56.     }
  57.   }
  58.   isEmpty = () => {}
  59.   size = () => {}
  60.   toString = () => {}
  61. }

树

二叉搜索树（BinarySearchTree)

只允许你在左侧节点存储比父节点小的值，在右侧节点存储比父节点大的值。

  1. export class Node {
  2.   constructor(key) {
  3.     this.key = key // 键是树对节点的称呼
  4.     this.left = null
  5.     this.right = null
  6.   }
  7. }
  1. class BST {
  2.   constructor () {
  3.     this.root = null
  4.   }
  5.   insert (key) {
  6.     if (this.root === null) {
  7.       this.root = new Node(key)
  8.     } else {
  9.       this.insertNode(this.root, key)
  10.     }
  11.   }
  12.   insertNode (node, key) {
  13.     if (node.key > key) {
  14.       if (node.left == null) {
  15.         node.left = new Node(key)
  16.       } else {
  17.         this.insertNode(node.left, key)
  18.       }
  19.     } else {
  20.       if (node.right == null) {
  21.         node.right = new Node(key)
  22.       } else {
  23.         this.insertNode(node.right, key)
  24.       }
  25.     }
  26.   }
  27.   inOrder (cb) {
  28.     this.inOrderNode(this.root, cb)
  29.   }
  30.   inOrderNode (node, cb) {
  31.     if (node !== null) {
  32.       this.inOrderNode(node.left, cb)
  33.       cb(node.key)
  34.       this.inOrderNode(node.right, cb)
  35.     }
  36.   }
  37.   search (key) {
  38.     return this.searchNode(this.root, key)
  39.   }
  40.   min () {
  41.     return this.minNode(this.root)
  42.   }
  43.   minNode (node) {
  44.     if (node.left === null) {
  45.       return node.key
  46.     }
  47.     while (node.left !== null) {
  48.       return this.minNode(node.left)
  49.     }
  50.   }
  51.   searchNode (node, key) {
  52.     if (node === null) {
  53.       return false
  54.     }
  55.     if (node.key > key) {
  56.       return this.searchNode(node.left, key)
  57.     } else if (node.key < key) {
  58.       return this.searchNode(node.right, key)
  59.     } else {
  60.       return true
  61.     }
  62.   }
  63. }
  64. const tree = new BST()
  65. tree.insert(6)
  66. tree.insert(7)
  67. tree.insert(2)
  68. tree.insert(16)
  69. tree.insert(1)
  70. console.log(tree, tree.inOrder((key) => console.log(key)), tree.min())

中序遍历：以上行顺序访问BST所有节点的遍历方式，也就是