Stack 栈

  • 线性结构, 仅能够在栈顶进行操作
  • 先进后出 First In Last Out
  • 实现方式: 数组、链表
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
class Stack {
  constructor() {
    this.stack = []
  }
  // 进栈
  push(item) {
    this.stack.push(item)
  }
  // 出栈
  pop() {
    return this.stack.pop()
  }
  // 栈顶元素
  top() {
    return this.stack[this.size() - 1]
  }
  // 栈尾元素
  end() {
    return this.stack[0]
  }
  // 栈的大小
  size() {
    return this.stack.length
  }
  // 清空栈
  clear() {
    this.stack = []
  }
  // 栈是否为空
  isEmpty() {
    return this.size() === 0
  }
}

括号合法性

编辑器代码检测 Vue模板解析

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
function isLegalBracket(str) {
  let stack = new Stack()
  for (const item of str) {
    if (item === '(') {
      stack.push(item)
    } else if (item === ')') {
      if (stack.isEmpty()) {
        return '不合法'
      }
      stack.pop()
    }
  }
  return stack.isEmpty() ? '合法' : '不合法'
}

function isLegalBrackets(str) {
  const map = {
    '(': -1,
    ')': 1,
    '[': -2,
    ']': 2,
    '{': -3,
    '}': 3
  }
  let stack = new Stack()
  for (const item of str) {
    if (map[item] < 0) {
      stack.push(item)
    } else {
      if (stack.pop() + map[item] !== 0) return false
    }
  }
  return stack.isEmpty()
}

两个队列实现一个栈

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
class QueueStack {

  constructor() {
    this.dataQueue = new Queue()
    this.emptyQueue = new Queue()
  }

  push(item) {
    this.dataQueue.enqueue(item)
  }

  pop() {
    while (this.dataQueue.size() > 1) {
      this.emptyQueue.enqueue(this.dataQueue.dequeue())
    }
    let item = this.dataQueue.dequeue()
    [this.dataQueue, this.emptyQueue] = [this.emptyQueue, this.dataQueue]
    return item
  }

  top() {
    return this.dataQueue.tail()
  }

  end() {
    return this.dataQueue.head()
  }
}

Queue 队列

  • 线性结构, 队头删除元素, 队尾添加元素
  • 先进先出 First In First Out
  • 实现方式: 数组、链表
  • 常应用于: Kafka RabbitMQ Socket

单链队列

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
class Queue {
  constructor() {
    this.queue = []
  }
  // 队尾添加元素
  enqueue(item) {
    this.queue.push(item)
  }
  // 队头删除元素
  dequeue() {
    return this.queue.shift()
  }
  // 头部元素
  head() {
    return this.queue[0]
  }
  // 尾部元素
  tail() {
    return this.queue[this.size() - 1]
  }
  // 队列大小
  size() {
    return this.queue.length
  }
  // 清空队列
  clear() {
    this.queue = []
  }
  // 队列是否为空
  isEmpty() {
    return this.size() === 0
  }
}

斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function fibonacci(n) {
  if (n === 1 || n === 2) return 1
  let queue = new Queue()

  let index = 2
  queue.enqueue(1)
  queue.enqueue(1)
  while (index < n) {
    let delItem = queue.dequeue()
    let headItem = queue.head()

    queue.enqueue(delItem + headItem)

    ++index
  }
  queue.dequeue()
  return queue.head()
}

两个栈实现一个队列

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
function StackQueue() {

  constructor() {
    this.dataStack = new Stack()
    this.emptyStack = new Stack()
  }

  enqueue(item) {
    this.dataStack.push(item)
  }

  dequeue() {
    while (this.dataStack.size() > 1) {
      this.emptyStack.push(this.dataStack.pop())
    }
    let item = this.dataStack.pop()
    while (!this.emptyStack.isEmpty()) {
      this.dataStack.push(this.emptyStack.pop())
    }
    return item
  }

  head() {
    return this.dataStack.end()
  }

  tail() {
    return this.dataStack.top()
  }
}

function StackQueueOptimize() {

  constructor() {
    this.enqueueStack = new Stack()
    this.dequeueStack = new Stack()
  }

  initStack() {
    if (this.dequeueStack.isEmpty()) {
      while (!this.enqueueStack.isEmpty()) {
        this.dequeueStack.push(this.enqueueStack.pop())
      }
    }
  }

  enqueue(item) {
    this.enqueueStack.push(item)
  }

  dequeue() {
    this.initStack()
    return this.dequeueStack.pop()
  }

  head() {
    this.initStack()
    return this.dequeueStack.top()
  }

  tail() {
    if (this.enqueueStack.isEmpty()) {
      while (!this.dequeueStack.isEmpty()) {
        this.enqueueStack.push(this.dequeueStack.pop())
      }
    }
    return this.enqueueStack.top()
  }
}

循环队列

1
2
3
4
5
6
class SqQueue {
  constructor(length) {
    this.queue = new Array(length + 1)
  }
  ...
}

出队 时间复杂度 O(1)

  • 线性结构 单链表、双向链表、循环链表
  • 递归结构

单向链表

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
class Node {
  constructor(data, next = null) {
    this.data = data
    this.next = next
  }
}

class LinkList {
  constructor() {
    this.length = 0
    this.head = null
    this.tail = null
  }

  append(data) {
    let newNode = new Node(data)
    if (this.head === null ) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length += 1
    return newNode
  }

  print() {
    let currNode = this.head
    while (currNode) {
      console.log(currNode.data)
      currNode = currNode.next
    }
  }

  get(index) {
    let node = this.getNode(index)
    return node && node.data
  }

  getNode(index) {
    if (index < 0 || index >= length) return null
    let currNode = this.head
    while (index-- > 0) {
      currNode = currNode.next
    }
    return currNode
  }

  insert(index, data) {
    if (index < 0 || index > length) return null
    if (index === this.length) {
      return this.append(data)
    } else {
      let newNode = new Node(data)
      if (index === 0) {
        newNode.next = this.head
        this.head = newNode
      } else {
        let prevNode = this.getNode(index - 1)
        newNode.next = prevNode.next
        prevNode.next = newNode
      }
      this.length += 1
      return newNode
    }
  }

  remove(index) {
    if (index < 0 || index >= length) return null
    let delNode = null
    if (index === 0) {
      delNode = this.head
      this.head = this.head.next
      if (this.head === null) {
        this.tail = null
      }
    } else {
      let prevNode = this.getNode(index - 1)
      delNode = prevNode.next
      if (delNode.next === null) {
        tail = prevNode
      } else {
        prevNode.next = prevNode.next.next
      }
    }
    this.length -= 1
    delNode.next = null
    return delNode.data
  }

  indexOf(data) {
    let index = -1
    let currNode = this.head
    while (currNode) {
      index += 1
      if (currNode.data === data) {
        return index
      } else {
        currNode = currNode.next
      }
    }
    return -1
  }

  clear() {
    this.length = 0
    this.head = null
    this.tail = null
  }

  isEmpty() {
    return this.length === 0
  }
}

function createLinkList(arr) {
  let head = null
  const length = arr.length
  for (let i = length - 1; i >= 0; i--) {
    const node = new Node(arr[i])
    node.next = head
    head = node
  }
  return head
}

反转链表

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
function reverseLinkList(linkNode) {
  let head = linkNode
  let nextNode = linkNode.next

  head.next = null

  while (nextNode) {
    let temp = nextNode.next
    nextNode.next = head
    head = nextNode
    nextNode = temp
  }
  return head
}

function reverseLinkList(linkNode) {
  let prevNode = null
  let currNode = null
  let nextNode = linkNode

  while (nextNode) {
    if (currNode && !prevNode) {
      currNode.next = null
    }

    if (prevNode && currNode) {
      currNode.next = prevNode
    }
    prevNode = currNode
    currNode = nextNode
    nextNode = nextNode.next
  }

  currNode.next = prevNode
  return currNode
}

const arr = [100, 200, 300, 400, 500]
const linkList = createLinkList(arr)
console.log((JSON.stringify(linkList), reverseLinkList(linkList))

双向链表

1
2
3
4
5
6
7
class Node {
  constructor({data, prev = null, next = null}) {
    this.data = data
    this.prev = prev
    this.next = next
  }
}

Tree 树

  • 递归结构

二叉树

  • 完全二叉树
  • 满二叉树
  • 在二叉树的第 i(i >=1 ) 层, 最多有 2^(i - 1) 个节点
  • 深度为 k(k >= 0) 的二叉树, 最少有 k 个节点
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
class BinTreeNode {
  constructor(data) {
    this.data = data
    this.leftChild = null
    this.rightChild = null
    this.parentNode = null
  }
}

class BinaryTree {
  constructor(str) {
    this.root = null
  }

  initTree(str) { /* 二叉树的广义表 */
    let stack = new Stack()
    let k = 0
    let newNode = null
    for (const item of str) {
      if (item === '#') {
        break
      }
      switch (item) {
        case '(':
          stack.push(newNode)
          k = 1
          break
        case ',':
          k = 2
          break
        case ')':
          stack.pop()
          break
        default:
          newNode = new BinTreeNode(item)
          if (this.root === null) {
            this.root = newNode
          } else {
            let topItem = stack.top()
            if (k === 1) {
              topItem.leftChild = newNode
            } else if (k === 2) {
              topItem.rightChild = newNode
            }
            newNode.parentNode = topItem
          }
          break
      }
    }
  }

  /* 递归 */
  prevOrderRecursion(node = this.root) {
    if (node === null) return
    console.log(node.data)
    this.prevOrderRecursion(node.leftChild)
    this.prevOrderRecursion(node.rightChild)
  }
  // 前序遍历
  preOrder(node = this.root) {
    let stack = new Stack()
    let currNode = node
    while (currNode) {
      console.log(currNode.data)
      if (currNode.rightChild) {
        stack.push(currNode.rightChild)
      }
      if (currNode.leftChild) {
        currNode = currNode.leftChild
      } else {
        currNode = stack.pop()
      }
    }
  }

  /* 递归 */
  inOrderRecursion(node = this.root) {
    if (node === null) return
    this.inOrderRecursion(node.leftChild)
    console.log(node.data)
    this.inOrderRecursion(node.rightChild)
  }
  // 中序遍历
  inOrder(node = this.root) {
    let stack = new Stack()
    let currNode = node
    while (true) {
      while (currNode) {
        stack.push(currNode)
        currNode = currNode.leftChild
      }
      let popItem = stack.pop()
      console.log(popItem.data)
      currNode = popItem.rightChild
      if (!currNode && stack.isEmpty()) break
    }
  }

  /* 递归 */
  postOrderRecursion(node = this.root) {
    if (node === null) return
    this.postOrderRecursion(node.leftChild)
    this.postOrderRecursion(node.rightChild)
    console.log(node.data)
  }
  // 后序遍历
  postOrder(node = this.root) {
    const Tag = function(node, state) {
      this.node = node
      this.state = state
    }
    let stack = new Stack()
    let currNode = node
    while (true) {
      while (currNode) {
        let tag = new Tag(currNode, 0)
        stack.push(tag)
        currNode = currNode.leftChild
      }
      let popItem = stack.pop()
      if (popItem.node.rightChild && popItem.state === 0) {
        popItem.state = 1
        stack.push(popItem)
        currNode = popItem.node.rightChild
      } else {
        console.log(popItem.node.data)
      }
      if (!currNode && stack.isEmpty()) break
    }
  }

  // 树的节点数量
  treeNodeCount(node) {
    if (node === null) return 0
    let leftNodeCount = this.treeNodeCount(node.leftChild)
    let rightNodeCount = this.treeNodeCount(node.rightChild)
    return leftNodeCount + rightNodeCount + 1
  }
  size() {
    return this.treeNodeCount(this.root)
  }

  // 树的高度
  treeHeight(node) {
    if (node === null) return 0
    let leftChildHeight = this.treeHeight(node.leftChild)
    let rightChildHeight = this.treeHeight(node.rightChild)
    return Math.max(leftChildHeight, rightChildHeight) + 1
  }
  height() {
    return this.treeHeight(this.root)
  }

  // 查找节点
  findNode(node, data) {
    if (node === null) return null
    if (node.data === data) return node
    return this.findNode(node.leftChild, data) || this.findNode(node.rightChild, data)
  }
  find(data) {
    this.findNode(this.root, data)
  }

  // 树的镜像
  mirror(node = this.root) {
    this.mirror1(node)
    // this.mirror2(node)
  }
  mirror1(node) {
    if (node === null) return
    [node.leftChild, node.rightChild] = [node.rightChild, node.leftChild]
    this.mirror1(node.leftChild)
    this.mirror1(node.rightChild)
  }
  mirror2(node) {
    if (node === null) return null
    let left = this.mirror2(node.leftChild)
    let right = this.mirror2(node.rightChild)
    node.leftChild = right
    node.rightChild = left
    return node
  }
}
//           A
//        /     \
//       B       C
//     /   \    /   \
//    D     E  F     G
//         / \  \   /
//        H   I  J K

// 前序遍历 A B D E H I C F J G K
// 中序遍历 D B H E I A F J C K G
// 后序遍历 D H I E B J F K G C A
let bt = new BinaryTree()
bt.initTree('A(B(D,E(H,I)),C(F(,J),G(K)))#')
bt.mirror()
bt.inOrder()

BST 二叉搜索树

  • 左 < 根 < 右

寻找 BST 第 K 小值问题，使用中序遍历，二分算法，正好是按照从小到大排序的

AVL 树

平衡二叉树 BBST
避免二叉树变成链表, 降低效率

  • 左单旋转: 不平衡节点平衡因子为2, 其右孩子平衡因子为1
  • 右单旋转: 不平衡节点平衡因子为-2, 其左孩子平衡因子为-1
  • 先左后右双旋转: 不平衡节点平衡因子为-2, 左孩子平衡因子为1
  • 先右后左双旋转: 不平衡节点平衡因子为2, 右孩子平衡因子为-1

红黑树

一种自动平衡的二叉树

B 树

物理上是多叉树，但逻辑上是一个 BST
用于高效 I/O，关系型数据库

Heap 堆

  • 时间复杂度 O(logn)
  • 节点的值，总是不大于（或不小于）父节点的值
  • 逻辑结构是一颗完全二叉树
  • 物理结构是一个数组 (连续存储 节省空间)
  • 查找比BST慢，增删比BST快

最大堆

最小堆

UFSets 并查集