常见数据结构

 1class Stack {
 2  constructor() {
 3    this.stack = []
 4  }
 5  push(item) {
 6    this.stack.push(item)
 7  }
 8  pop() {
 9    this.stack.pop()
10  }
11  peek() {
12    return this.stack[this.getCount() - 1]
13  }
14  getCount() {
15    return this.stack.length
16  }
17  isEmpty() {
18    return this.getCount() === 0
19  }
20}

1this.stack.push(item)
2
3this.stack.shift()   //移除数组中的第一个项并返回该项

 1class Node {
 2  constructor(v, next) {
 3    this.value = v
 4    this.next = next
 5  }
 6}
 7class LinkList {
 8  constructor() {
 9    // 链表长度
10    this.size = 0
11    // 虚拟头部
12    this.dummyNode = new Node(null, null)
13  }
14  find(header, index, currentIndex) {
15    if (index === currentIndex) return header
16    return this.find(header.next, index, currentIndex + 1)
17  }
18  addNode(v, index) {
19    this.checkIndex(index)
20    // 当往链表末尾插入时，prev.next 为空
21    // 其他情况时，因为要插入节点，所以插入的节点
22    // 的 next 应该是 prev.next
23    // 然后设置 prev.next 为插入的节点
24    let prev = this.find(this.dummyNode, index, 0)
25    prev.next = new Node(v, prev.next)
26    this.size++
27    return prev.next
28  }
29  insertNode(v, index) {
30    return this.addNode(v, index)
31  }
32  addToFirst(v) {
33    return this.addNode(v, 0)
34  }
35  addToLast(v) {
36    return this.addNode(v, this.size)
37  }
38  removeNode(index, isLast) {
39    this.checkIndex(index)
40    index = isLast ? index - 1 : index
41    let prev = this.find(this.dummyNode, index, 0)
42    let node = prev.next
43    prev.next = node.next
44    node.next = null
45    this.size--
46    return node
47  }
48  removeFirstNode() {
49    return this.removeNode(0)
50  }
51  removeLastNode() {
52    return this.removeNode(this.size, true)
53  }
54  checkIndex(index) {
55    if (index < 0 || index > this.size) throw Error('Index error')
56  }
57  getNode(index) {
58    this.checkIndex(index)
59    if (this.isEmpty()) return
60    return this.find(this.dummyNode, index, 0).next
61  }
62  isEmpty() {
63    return this.size === 0
64  }
65  getSize() {
66    return this.size
67  }
68}

 1class Node {
 2  constructor(value) {
 3    this.value = value
 4    this.left = null
 5    this.right = null
 6  }
 7}
 8class BST {
 9  constructor() {
10    this.root = null
11    this.size = 0
12  }
13  getSize() {
14    return this.size
15  }
16  isEmpty() {
17    return this.size === 0
18  }
19  addNode(v) {
20    this.root = this._addChild(this.root, v)
21  }
22  // 添加节点时，需要比较添加的节点值和当前
23  // 节点值的大小
24  _addChild(node, v) {
25    if (!node) {
26      this.size++
27      return new Node(v)
28    }
29    if (node.value > v) {
30      node.left = this._addChild(node.left, v)
31    } else if (node.value < v) {
32      node.right = this._addChild(node.right, v)
33    }
34    return node
35  }
36}