写这篇是因为之前在群里看到小伙伴在讨论算法相关知识，对于前端来说，这块也是很重要嘛，正好把之前没看完的那本电子书，《学习JavaScript数据结构与算法》复习下~

栈数据结构

栈是一种遵从后进先出(LIFO, Last in First out)原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端叫作栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

我们只是用ES6的简化语法把Stack函数转换成类。但变量items却是公共的，ES6的类是基于原型的，虽然基于原型的类比基于函数的类更节省内存，也更适合创建多个实例，却不能够声明私有属性或方法，而且，在这种情况下，我们希望Stack类的用户只能访问暴露给类的方法，否则就有可能从栈的中间移除元素（因为我们用数组来存储其值）

以下是ES6方法，创建私有属性的方式：

  • 用ES6的限定作用域Symbol实现类
1
2
3
4
5
6
7
8
let _items = Symbol();

class Stack {
  constructor() {
    this[_items] = [];
  }
  // stack方法
}

这种方法创建了一个假的私有属性，因为 Object.getOwnPropertySymbols能够取到类里面声明的所有Symbols属性

下面是一个破坏Stack类的例子：

1
2
3
4
5
6
7
8
9
let stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1);
stack.print(); // 5, 8, 1

访问stack[objectSymbols[0]]是可以得到_items的，并且_items属性是一个数组，可以进行任意的数组操作，于是还有下面的方案：

用ES6的WeakMap实现类

有一种数据类型可以确保属性是私有的，这就是WeakMap，现在只需要知道WeakMap可以存储键值对，其中键是对象，值可以是任意数据类型。

如果用WeakMap类存储items变量，Stack类就是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const items = new WeakMap();

class Stack {
  constructor() {
    items.set(this, [])
  }
  push(element) {
    let s = items.get(this);
    s.push(element);
  }
  pop() {
    let s = items.get(this);
    r = s.pop();
    return r;
  }
  // ...其他方法
}

现在我们知道items在Stack类里是真正的私有属性了，但还有一件事要做。items现在仍然是在Stack类以外声明的，因此谁都可以改动它。我们要用一个闭包（外层函数）把Stack类包起来，这样就只能在这个函数里访问WeakMap：

1
2
3
4
5
6
7
8
9
10
let Stack = (function() {
  const items = new WeakMap();
  class Stack {
    constructor() {
      items.set(this, []);
    }
    // 其他方法
  }
  return Stack;
})();

完整代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 声明类
class Stack {
  constructor() {
    this.items = [];
  }
  // 向栈添加元素
  push(element) {
    this.items.push(element);
  }
  // 从栈移除元素
  pop() {
    return this.items.pop();
  }
  // 查看栈顶元素
  peek() {
    return this.items[this.items.length - 1];
  }
  // 检查栈是否为空
  isEmpty() {
    console.log(`当前栈是否为空：${this.items.length === 0}`)
  }
  // 清空栈元素
  clear() {
    this.items = [];
  }
  size() {
    console.log(`当前栈的元素有${this.items.length}个`)
  }
  // 打印栈元素
  print() {
    console.log(this.items.toString())
  }
}
let stack = new Stack();
// console.log(stack.isEmpty())
stack.push(5)
stack.push(8)
console.log(stack.peek())
stack.push(11)
stack.size()
stack.isEmpty()
stack.pop();
stack.pop();
stack.size()

队列数据结构

队列是遵循FIFO(First In First Out，先进先出)原则的一组有序的项。
队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

JS任务队列

当我们在浏览器中打开新标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，它被称为事件循环。
浏览器要负责多个任务，如渲染HTML，执行JS代码，处理用户交互（输入、点击等），执行和处理异步请求。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 创建队列
let Queue = (function() {
  const items = new WeakMap();
  class Queue {
    constructor() {
      items.set(this, []);
    }

    // 向队列添加元素
    enqueue(elem) {
      items.push(elem);
    }

    // 向队列移除元素
    dequeue() {
      return items.shift();
    }

    // 查看队列头元素
    front() {
      console.log(items[0])
      return items[0];
    }

    // 检查队列是否为空
    isEmpty() {
      console.log(`是否为空：${items.length === 0}`)
      return items.length === 0;
    }

    size() {
      console.log(`队列长度为：${items.length}`);
      return items.length;
    }

    // 打印队列元素
    print() {
      console.log(items.valueOf());
    }
  }
})();
// 使用Queue类
let queue = new Queue();
queue.isEmpty();
queue.enqueue('John');
queue.enqueue('Jack');
queue.enqueue('Camila');
queue.print();

链表

链表是种动态的数据结构，这意味着我们可以从中任意添加或移除项，它会按需进行扩充。

要存储多个元素，数组（或列表）可能是最常用的数据结构。每种语言都实现了数组，它提供了一个便利的[]语法来访问其元素。然而这种数据结构有一种缺点，其数组大小是固定的。
从数组的起点或中间插入或移除项的成本很高，因为它需要移动元素（尽管我们知道JS的Array类可以帮我们做这类事，但情况还是相同）
链表存储有序的元素集合，但不同于数组，链表的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称为指针或链接）组成。
相对于传统的数组，链表的好处在于，添加或移除元素时不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素。而想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需元素。

完整代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
function LinkedList() {
  let Node = function(element) {
    this.element = element
    this.next = null
  }
  let length = 0
  let head = null
  // 向列表尾部添加一个新的项
  this.append = function(element) {
    let node = new Node(element)
    let current
    // 列表中第一个节点
    if (head === null) {
      head = node
    } else {
      current = node
      // 循环列表，直到找到最后一项
      while (current.next) {
        current = current.next
      }
      // 找到最后一项，将其next赋为node，建立连接
      current.next = node
    }
    // 更新列表长度
    length++
  }
  // 向列表的特定位置插入一个新的项
  this.insert = function(position, element) {
    // 检查越界值
    if (position >= 0 && position <= length) {
      let node = new Node(element)
      let current = head
      let previous
      let index = 0
      // 在第一个位置添加
      if (position === 0) {
        node.next = current
        head = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        node.next = current
        previous.next = node
      }
      // 更新列表长度
      length++
      return true
    } else {
      return false
    }
  }
  // 从列表的特定位置移除一项
  this.removeAt = function(position) {
    // 检查越界值
    if (position > -1 && position < length) {
      let current = head
      let previous
      let index = 0
      // 移除第一项
      if (position === 0) {
        head = current.next
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        // 将previous与current的下一项连接起来；跳过current，从而移除它
        previous.next = current.next
      }
      length--
      return current.element
    } else {
      return null
    }
  }
  // 从列表中移除一项
  this.remove = function(element) {
    let index = this.indexOf(element)
    return this.removeAt(index)
  }
  // 返回元素在列表中的索引，若列表中没有该元素则返回-1
  this.indexOf = function(element) {
    let current = head
    let index = -1
    while (current) {
      if (element === current.element) {
        return index
      }
      index++
      current = current.next
    }
    return -1
  }
  this.isEmpty = function() {
    return length === 0
  }
  // 返回链表包含的元素个数，与数组的length属性类似
  this.size = function() {
    return length
  }
  this.getHead = function() {
    return head
  }
  // 由于列表项使用了Node类，就需要重写继承自JS默认的toString方法，让其只输出元素值
  this.toString = function() {
    // 首先要访问列表中的所有元素，就需要有一个起点，也就是head。我们会把current变量当作索引，控制循环访问列表
    // 我们还需要初始化用于拼接元素值的变量，接下来就是循环访问列表中的每个元素
    // 我们要用current来检查元素是否存在，然后得到元素内容进行拼接
    // 最后迭代下一个元素，最终返回列表内容的字符串
    let current = head
    let string = ''
    while (current) {
      string += current.element + (current.next ? 'n' : '')
      current = current.next
    }
    return string
  }
  this.print = function() {}
}
var md1 = `
  LinkedList数据结构还需要一个Node辅助类。Node类表示要加入列表的项，它包含一个element属性，即要添加到列表的值，以及一个next属性，即指向列表中下一个节点项的指针。
  LinkedList类也有存储列表项的数组的length属性（是一个私有变量）
  另一个重要点是，我们还需要存储第一个节点的引用。为此，可以把这个引用存储在称为head的变量中
  然后就是LinkedList类的方法
`

链表优点

  1. 使用链表数据结构可以克服数组链表需要预先知道数据大小的缺点，链表数据结构可以充分内存空间，实现灵活的内存动态管理

  2. 数据的存取往往要在不同的排列顺序中转换，而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的指针。链表允许插入和移除链表上任意位置上的节点，但是不允许随机存取

链表缺点

链表失去了数组随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大

先到这里，后面再补充吧~~