《数据结构与算法之美》基础篇笔记（一）

摘要：极客时间《数据结构与算法之美》基础篇笔记，数组、链表、栈、队列、递归

数组

概念

数组是（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。数值支持随机访问，根据下表随机访问的时间复杂度为 O(1)
计算机通过地址来访问内存中的数据，数组寻址公式： a[i]_address = base_address + i * data_type_size，base_address 是内存块的首地址，data_type_size 表示数组中每个元素的大小。根据寻址公式可以看出，如果数组编号从 1 开始，那么访问地址就要变成 a[i]_address = base_address + (i - 1) * data_type_size，这样的话就多了一步减法操作。而且 Java、JavaScript 都效仿了 C 语言：从 0 开始计数数组下标。

插入与删除

假设数组长度为 n，现在将一个数据插入到数组的第 k 个位置，那么第 k~n 这部分的元素都顺序地往后挪一位。如果是在数组末尾插入，则不需要挪移数据，最好时间复杂度为 O(1)。如果是在数组开头插入，则所有的元素都要向后挪一位，最坏时间复杂度为 O(n)。插入各个位置的概率是一样的，则平均情况时间复杂度为 (1+2+…+n)/n=O(n)。有时为了避免大规模的数据搬移，可以直接将第 k 位的数据搬移到数据的末尾，然后将新元素直接放入第 k 个位置，这样的插入的时间复杂度变为 O(1)
删除元素后，为了保持内存的连续性，也要搬移数据。删除末尾数据时为最好情况时间复杂度 O(1)；删除开头数据时为最坏情况复杂度 O(n)；平均情况时间复杂度为 O(n)。有时在特殊场景下，我们一定非得追求数组中数据的连续性：可以先记录下已经删除的数据，当数组没有更多空间存储数据时再触发执行一次真正的删除操作，这样就大大减少了数据搬移的工作

链表

概念

与数组不同，链表是通过“指针”将一组零散的内存块串联起来使用，常见的有单链表、双向链表和循环链表。这些内存块被称为“结点”，记录下个结点地址的指针叫做后继指针 next

单链表

单链表的第一个结点叫做头结点，最后一个几点叫做尾结点。其中，头结点用来记录链表的基地址。尾结点的指针指向一个空地址 NULL
链表的插入和删除操作只需要考虑相邻结点的指针改变，所以对应的时间复杂度为 O(1)。但是单链表的查询只能遍历结点，需要 O(n)的时间复杂度
js 实现单链表（js 代码引用自 《学习JavaScript数据结构与算法》第五章）

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
function LinkedList() {
  // Node 辅助类：element 是要添加的值，next 是指向下一个结点的指针
  var Node = function (element) {
    this.element = element
    this.next = null
  }
  var length = 0 // 链表长度
  var head = null // 链表 head 指针
  // 向链表尾部添加元素
  this.append = function (element) {
    var node = new Node(element), current;
    if (head == null) { // 如果链表为空，将 head 指向第一个元素
      head = node
    } else { // 如果链表不为空
      current = head
      while (current.next) { // 遍历得到链表最后一个元素
        current = current.next
      }
      current.next = node // 将原来最后一个元素的 next 指针指向新元素
    }
    length++ // 更新长度
  }
  // 向链表指定位置插入元素
  this.insert = function (position, element) { // position 为指定位置的索引
    if (possion >= 0 && possion <= length) { // 判断是否越界
      var node = new Node(element),
        current = head, // 暂存当前元素
        previous, // 暂存前一个元素
        index = 0
      if (possion == 0) { // 添加到第一个位置
        // 注意复制顺序
        node.next = head
        head = node
      } else {
        while (index++ < possion) { // 遍历得到 index 索引元素及其前一个元素
          previous = current
          current = current.next
        }
        // 插入元素
        node.next = current
        previous.next = node
      }
      length++
      return true
    } else {
      return false
    }
  }
  // 从链表指定位置移除元素
  this.removeAt = function (position) {
    var current = head,
      previous,
      index = 0
    if (position > -1 && position < length) { // 判断是否越界
      if (position == 0) {
        head = current.next
      } else {
        while (index++ < position) {
          previou = current
          current = current.next
        }
        // 跳过 current 元素达到移除的目的
        previou.next = current.next
      }
      length--
      return current.element
    } else {
      return null
    }
  }
  // 返回元素在链表中的索引
  this.indexOf = function (element) {
    var current = head,
      index = 0
    while (current) {
      if (element == current.element) {
        return index
      }
      index++
      current = current.next
    }
    return -1
  }
  // 从链表中移除元素
  this.remove = function (element) {
    var index = this.indexOf(element)
    return this.removeAt(index)
  }
  // 返回链表是否为空
  this.isEmpty = function () {
    return length === 0
  }
  // 返回链表包含元素个数
  this.size = function () {
    return length
  }
  // 获取第一个元素
  this.getHead = function () {
    return head
  }
  // 将链表转换成字符串返回
  this.toString = function () {
    var current = head,
      string = ''
    while (current) {
      string += "," + current.element
      current = current.next
    }
    return string.slice(1)
  }
}

SinglyLinkedList

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
199
200
201
202
203
204
205
206
207
208
class Node {
  // 存储的是字符串
  constructor(element) {
    this.element = element
    this.next = null
  }
}
class LinkedList {
  constructor() {
    // head 是哨兵结点
    this.head = new Node('head')
  }
  // 根据 value 查找节点
  findByValue(item) {
    let currentNode = this.head.next
    while (currentNode !== null && currentNode.element !== item) {
      currentNode = currentNode.next
    }
    return currentNode === null ? -1 : currentNode
  }

  // 根据 index 查找节点，下标从0开始
  findByIndex(index) {
    let currentNode = this.head.next
    let pos = 0
    while (currentNode !== null && pos !== index) {
      currentNode = currentNode.next
      pos++
    }
    return currentNode === null ? -1 : currentNode
  }

  // 向链表末尾追加节点
  append(newElement) {
    const newNode = new Node(newElement)
    let currentNode = this.head
    while (currentNode.next) {
      currentNode = currentNode.next
    }
    currentNode.next = newNode
  }

  // 指定元素向后插入
  insert(newElement, element) {
    const currentNode = this.findByValue(element)
    if (currentNode === -1) {
      console.log('未找到插入位置')
      return
    }
    const newNode = new Node(newElement)
    newNode.next = currentNode.next
    currentNode.next = newNode
  }

  // 查找前一个
  findPrev(item) {
    let currentNode = this.head
    while (currentNode.next !== null && currentNode.next.element !== item) {
      currentNode = currentNode.next
    }
    if (currentNode.next === null) {
      return -1
    }
    return currentNode
  }

  // 根据值删除
  remove(item) {
    const prevNode = this.findPrev(item)
    if (prevNode === -1) {
      console.log('未找到元素')
      return
    }
    prevNode.next = prevNode.next.next
  }

  // 遍历显示所有节点
  display() {
    let currentNode = this.head.next // 忽略头指针的值
    while (currentNode !== null) {
      console.log(currentNode.element)
      currentNode = currentNode.next
    }
  }

  // 尾插法 反转单链表
  reverseList() {
    // 先设置新的哨兵结点
    const root = new Node('head')
    // 第一个结点为原链表的第一个结点
    let currentNode = this.head.next
    // 依次遍历原链表，每次都是将结点插入到新哨兵结点之后，注意赋值顺序
    while (currentNode !== null) {
      const next = currentNode.next
      currentNode.next = root.next
      root.next = currentNode
      currentNode = next
    }
    this.head = root
  }

  // 求中间节点，使用快慢指针，快指针一次两步，慢指针一次一步，起始指向第一个结点并同时开走，当快指针指向最后一个结点（奇数个结点）或者倒数第二个结点时，慢指针指向中间结点
  findMiddleNode() {
    let fast = this.head.next
    let slow = this.head.next
    while (fast.next !== null && fast.next.next !== null) {
      fast = fast.next.next
      slow = slow.next
    }
    return slow
  }

  // 环验证
  checkCircle() {
    let fast = this.head.next
    let slow = this.head
    // 快慢指针，快指针一次两步，慢指针一次一步，同时开走，如果相遇（引用相同）说明有环
    while (fast !== null && fast.next !== null) {
      fast = fast.next.next
      slow = slow.next
      if (slow === fast) return true
    }
    return false
  }

  // 删除倒数第 k 个节点，反转单链表删除第 k 个结点后再反转
  removeByIndexFromEnd1(index) {
    //务必先判断是否是 环链表
    if (this.checkCircle()) return false
    let pos = 1
    this.reverseList()
    let currentNode = this.head.next
    while (currentNode !== null && pos < index) {
      currentNode = currentNode.next
      pos++
    }
    if (currentNode === null) {
      console.log('该节点不存在')
      return false
    }
    this.remove(currentNode.element)
    this.reverseList()
  }

  // 删除倒数第 k 个结点，使用双指针，第一个指针先行走 k 步指向第 k 个结点，然后两个指针一起遍历，直到第一个指针的 next 指向 null，此时第二个指针的 next 就指向要删除的结点
  removeByIndexFromEnd2(index) {
    if (this.checkCircle()) return false
    let fast = 1
    let fastNode = this.head.next
    while (fastNode.next !== null && fast < index) {
      fastNode = fastNode.next
      fast++
    }
    if (fast !== index) {
      console.log('该节点不存在')
      return false
    }
    let currentNode = this.head.next
    // 也可以直接获取倒数第 k-1 个结点，然后跳过下一个结点即可删除
    // let currentNode = this.head
    while (fastNode.next !== null) {
      fastNode = fastNode.next
      currentNode = currentNode.next
    }
    this.remove(currentNode.element)
    // currentNode.next = currentNode.next.next
  }

  // 合并两个有序链表
  mergeSortedLists(linkA, linkB) {
    // 如果其中一个没有，则直接返回另一个
    if (!linkA) {
      return linkB
    }
    if (!linkB) {
      return linkA
    }
    let a = linkA
    let b = linkB
    let resultLink = null
    // 设置新链表的第一个结点
    if (a.element < b.element) {
      resultLink = a
      a = a.next
    } else {
      resultLink = b
      b = b.next
    }
    // 遍历对比大小为新链表按顺序添加结点
    wile(a !== null && b !== null) {
      if (a.element < b.element) {
        resultLink.next = a
        a = a.next
      } else {
        resultLink.next = b
        b = b.next
      }
      resultLink = resultLink.next
    }
    // 剩余的部分都比另一条链大，则全部添加到末尾
    if (a != null) {
      resultLink.next = a
    } else {
      resultLink.next = b
    }
    return resultLink
  }
}

双向链表

双向链表的每个结点不知有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。这样使双向链表需要比单链表更多的空间来存储后继结点的地址，同时也带来了更多的灵活性。双向链表可以支持 O(1) 时间复杂度的情况下找到前去结点，而不需要遍历所有结点。
双向链表中的删除：
1、删除结点中“值等于某个给定值”的结点
2、删除给定指针指向的结点
第1种情况，无论单双链表都需要遍历找到对应的结点后再删除。遍历的时间复杂度为 O(n)，纯删除操作为 O(1)，结合加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)
第2种情况，已知要删除的结点，那么就知道其前驱结点的指针，不需要遍历获得前驱结点，则时间复杂度为 O(1)
插入：如果在链表的某个指定结点前面插入一个结点，双向链表可以获得节点的前驱结点，时间复杂度为 O(1)
如果双向链表和循环列表整合则成为双向循环链表
js 实现双向链表（js 代码引用自 《学习JavaScript数据结构与算法》第五章）

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
function DoublyLinkedList() {
  var Node = fucntion(element) {
    this.element = element
    this.next = null
    this.prev = null // 指向前面结点的指针
  }
  var length = 0
  var head = null
  var tail = null // 指向最后一个节点
  // 插入新元素
  this.insert = function (position, element) {
    // 判断边界
    if (position >= 0 && position <= length) {
      var node = new Node(element),
        current = head,
        previous,
        index = 0
      // 三种情况：在头部插入，尾部插入，中间插入
      if (position === 0) {
        if (!head) {
          head = node
          tail = node
        } else {
          node.next = head
          current.prev = node
          head = node
        }
      } else if (position === length) {
        current = tail
        current.next = node
        node.prev = current
        tail = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        node.next = current
        current.previous = node
        previous.next = node
        node.previous = previous
      }
      length++
      return true
    } else {
      return false
    }
  }
  this.removeAt = function (position) {
    // 判断边界
    if (position > -1 && position < length) {
      var current = head,
        previous,
        index = 0;
      // 三种情况：头部删除，尾部删除，中间删除
      if (position === 0) {
        head = current.next
        if (length === 1) {
          tail = null
        } else {
          head.prev = null
        }
      } else if (position === length - 1) {
        current = tail
        tail = current.prev
        tail.next = null
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
        current.next.prev = previous
      }
      length--
      return current.element
    } else {
      return null
    }
  }
}

循环链表

循环链表是一种特殊的单链表，其尾结点的指针(tail.next)指向链表的头结点(head)。双向循环列表则是尾结点后继指针(tail.next)指向头结点(head)，头结点前驱指针(head.prev)指向尾结点(tail)。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。

数组与链表对比

数组是使用的连续内存空间，如果声明的空间过大，则可能导致“内存不足”，过小则可能会不够用。不够用时会申请一块更大的内存空间，把原数组拷贝进去，十分费时。
链表本身没有大小限制，天然支持动态扩容

基于链表实现 LRU 缓存淘汰算法

思路：维护一个有序单链表，越靠近链表尾部的结点是越早访问的。当有一个新数据被访问时，从头开始顺序遍历链表。
如果链表中已缓存该数据，遍历得到该数据对应的结点，将其从原有位置上删除，然后在添加到链表头部。
如果链表中没有该数据，同时缓存未满，则直接将新数据结点插入到链表头部；如果缓存已满，则将链表尾结点删除后将新数据结点插入链表头部

链表编写技巧

技巧一：理解指针或引用的含义

存储所指对象的内存地址。将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针。指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量

技巧二：警惕指针丢失和内存泄漏

插入结点时，一定要注意操作的顺序。删除链表结点时，也一定要记得手动释放内存空间，自动管理内存的编程语言除外（例如：java、js）

技巧三：利用哨兵简化实现难度

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。使用哨兵解决“便捷问题”，不直接参与业务逻辑。引入哨兵结点后，在任何时候，不管链表是不是空，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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// 在数组a中，查找key，返回key所在的位置
// 其中，n表示数组a的长度
// 普通代码
int find(char* a, int n, char key) {
  // 边界条件处理，如果a为空，或者n<=0，说明数组中没有数据，就不用while循环比较了
  if(a == null || n <= 0) {
    return -1;
  }
  int i = 0;
  // 这里有两个比较操作：i<n和a[i]==key.
  while (i < n) {
    if (a[i] == key) {
      return i;
    }
    ++i;
  }
  return -1;
}

// 利用哨兵
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return -1;
  }
  // 这里因为要将 a[n-1] 的值替换成 key，所以要特殊处理这个值
  if (a[n-1] == key) {
    return n-1;
  }
  // 把 a[n-1] 的值临时保存在变量 tmp 中，以便之后恢复。tmp=6。
  // 之所以这样做的目的是：希望 find() 代码不要改变a数组中的内容
  char tmp = a[n-1];
  // 把key的值放到 a[n-1] 中
  a[n-1] = key;
  int i = 0;
  // while 循环比起代码一，少了i<n这个比较操作
  while (a[i] != key) {
    ++i;
  }
  // 恢复 a[n-1] 原来的值
  a[n-1] = tmp;
  if (i == n-1) {
    // 如果 i == n-1 说明，在 0...n-2 之间都没有key，所以返回 -1
    return -1;
  } else {
    // 否则，返回 i，就是等于 key 值的元素的下标
    return i;
  }
}

// js
// 普通代码
function find(arr, key) { // 在数组 arr 中返回与 key 相等的元素的索引
  if (arr == null || arr.lenght <= 0) { // 判断数组是否存在元素
    return -1
  }
  var i = 0, n = arr.lenght
  while (i < n) {
    if (arr[i] == key) { // 循环判断是否相等
      return i
    }
    ++i
  }
}

// 利用哨兵
function find(arr, key) {
  if (arr == null || arr.lenght <= 0) { // 判断数组是否存在元素
    return -1
  }
  var n = arr.length
  if (arr[n - 1] == key) { // 先判断数组最后一个元素是否为要找的
    return n - 1
  }
  var tmp = arr[n - 1] // 暂时保存最后一个元素的值，便于后面数组的恢复
  arr[n - 1] = key // 将指定的值赋给数组最后一个元素
  var i = 0
  while (arr[i] != key) { // 循环判断数组元素是否与指定值相等，数组越长，遍历耗时越久
    ++i // 代码少了 arr[i] == key 这个判断，数组越长，节省时间越多
  }
  arr[n - 1] = tmp // 循环后恢复原来的数组
  if (i == n - 1) { // 返回索引，如果 i = n - 1，说明整个数组前面的 n - 1 个元素都不匹配，前面已经判断数组最后一个元素也不是，说明数组中不包含指定的元素
    return -1
  } else {
    return i
  }
}

利用哨兵可以减少执行时间，但是这样可读性太差，一般不需要如此追求极致的性能

技巧四：重点留意边界条件处理

经常用来检查链表代码是否正确的边界条件有4个：
1、如果链表为空时，代码是否能正常工作？
2、如果链表只包含一个结点时，代码是否能正常工作？
3、如果链表只包含两个结点时，代码是否能正常工作？
4、代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
就是链表在结点个数为0、1、2时能否工作，代码在头尾结点能否正确执行

技巧五：举例画图，辅助思考

画在纸上可以更清晰

技巧六：多写多练，没有捷径

练习 5 个常见的链表操作（详细见”单链表”一节代码）：
1、单链表反转
2、链表中环的检测
3、两个有序的链表合并
4、删除链表倒数第 n 个结点
5、求链表的中间结点

用空间换时间

用空间换时间的设计思想：当内存空间充足，追求代码执行速度，可以选择空间复杂的相对较高但时间复杂度相对较低的算法或者数据结构。反之，在手机或单片机上则选择用时间换空间的思想

栈

概念

栈：限定仅在表尾进行插入和删除操作的线性表，有先进后出，后进先出的特性（迟到早退），是一种操作受限制的线性表。
站只有两个基本操作：入栈 push()、出栈 pop()
用数组实现的栈叫顺序栈，用链表实现的栈叫链式栈。入栈和出栈的空间复杂度都为 O(1)，这里的空间复杂度是指除了原本的数据存储空间外，算法运行还需要额外的存储空间
实现一个栈（js 代码引用自 《学习JavaScript数据结构与算法》第三章）

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
// java 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           //栈的大小

  // 初始化数组，申请一个大小为n的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了，直接返回false，入栈失败。
    if (count == n) return false;
    // 将item放到下标为count的位置，并且count加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素，并且栈中元素个数count减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

// js 基于数组实现的顺序栈
function Stack() {
  var items = []
  // 添加新元素到栈顶
  this.push = function(element) {
    items.push(element)
  }
  // 移除栈顶的元素并返回
  this.pop = function(element) {
    return items.pop()
  }
  // 返回栈顶的元素
  this.peek = function() {
    return items[items.length -1]
  }
  // 栈是否为空
  this.isEmpty = function() {
    return items.length == 0
  }
  // 返回栈里的元素个数
  this.size = function() {
    return items.length
  }
  // 移除栈里的所有元素
  this.clear = function() {
    items = []
  }
  // 辅助方法：将栈里的元素输出到控制台
  this.print = function() {
    console.log(items.toString())
  }
}

基于链表实现的栈StackBasedOnLinkedList：

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
class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}
// 链表头部即栈顶
class StackBasedLinkedList {
  constructor() {
    this.top = null
  }

  // 入栈
  push(value) {
    const node = new Node(value)
    if (this.top === null) {
      this.top = node
    } else {
      node.next = this.top
      this.top = node
    }
  }
  // 出栈
  pop() {
    if (this.top === null) {
      return -1
    }
    const value = this.top.element
    this.top = this.top.next
    return value
  }
  // 清空栈
  clear() {
    this.top = null
  }
  // 显示栈所有元素内容
  display() {
    if (this.top !== null) {
      let temp = this.top
      while (temp !== null) {
        console.log(temp.element)
        temp = temp.next
      }
    }
  }
}

支持动态扩容的顺序栈

当栈不满的时候，入栈操作时间复杂度为 O(1)；栈空间不够时，需要重新申请空间并迁移数据，时间复杂度为 O(n)。即入栈最好情况时间复杂度为 O(1)，最坏情况时间复杂度为 O(n)。
现在假设条件：
1、栈空间不够时，我们重新申请一个是原来大小两倍的数组
2、仅分析入栈操作，忽略出栈操作
3、不涉及内存搬移的入栈操作为 simple-push 操作，时间复杂度为 O(1)
在这些条件下，一个大小为 K 的空栈，前 K 次入栈的时间复杂度为 O(1)。第 K+1 次入栈需要申请 2K 空间并迁移前 K 个元素和执行 K+1 次入栈操作，其时间复杂度为 O(n)。之后又是 K-1 次 simple-push 入栈操作，时间复杂度为 O(1)。使用摊还分析法，入栈的均摊时间复杂度为 O(1)

栈常见应用

1、函数调用栈。比如调用 A 函数时就将 A 函数压入栈顶，如果 A 函数中调用另一个函数 B，就将 B 函数再压入栈顶，执行完后 B 函数后 B 函数出栈，然后再继续执行 A 函数
2、表达式求值。编译器通过两个栈来实现求值功能：一个栈保存操作的数，另一个保存运算符。从左向右遍历表达式，如果是数字，直接压入操作数栈。如果是运算符，就与运算符栈的栈顶元素进行比较。如果比栈顶元素优先级高，就把当前运算符压入栈顶；如果比栈顶元素优先级低或者相等，从运算符栈中取出一个运算符（一次出栈），从操作数栈的栈顶取出两个数（两次出栈），然后进行运算，再将运算的结果存入操作数栈，继续遍历操作
3、括号匹配。假设现有表达式中有三种括号：圆括号()、方括号[]、花括号{}，三者可以随意嵌套，怎样判断这个表达式中括号都是成对出现合法的呢？用栈来保存未匹配的左括号，从左向右扫描表达式：遇到左括号时，将其压入栈顶，遇到右括号并且能与当前栈顶的左括号匹配，则继续扫描；如果右括号不能与栈顶的左括号匹配，或者栈顶没有数据，说明字符串非法。如果扫描完后栈为空，说明合法；否则，有未匹配的左括号，字符串格式非法
4、浏览器的前进、后退功能。使用两个栈，X 和 Y，把首次访问的页面依次压入 X 的栈顶，点击后退时，再依次从 X 中出栈，再依次放入 Y 栈。当点击前进时，则依次从 Y 中取出，再依次放入 X 栈。当 X 或 Y 没有数据，说明没有前进或后退的页面了SampleBrowser

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
class SampleBrowser {
  constructor() {
    // 上面使用链表实现的栈 StackBasedLinkedList
    this.normalStack = new StackBasedLinkedList() // X 栈
    this.backStack = new StackBasedLinkedList() // Y 栈
  }
  // 正常浏览页面， X 正常入栈，Y 清空
  pushNormal(name) {
    this.normalStack.push(name)
    this.backStack.clear()
    this.displayAllStack()
  }
  // 后退，X 出栈， Y 入栈
  back() {
    const value = this.normalStack.pop()
    if (value !== -1) {
      this.backStack.push(value)
      this.displayAllStack()
    } else {
      console.log('无法后退')
    }
  }
  // 前进，Y 出栈，X 入栈
  front() {
    const value = this.backStack.pop()
    if (value !== -1) {
      this.normalStack.push(value)
      this.displayAllStack()
    } else {
      console.log('无法前进')
    }
  }
  // 打印栈内数据
  displayAllStack() {
    console.log('---后退页面---')
    this.backStack.display()
    console.log('---浏览页面---')
    this.normalStack.display()
  }
}

队列

概念

队列：只允许在表的前端进行删除操作，在表的后端进行插入操作，有先进先出的特性，也是一种操作受限制的线性表
队列也只有两种基本操作：入队 enqueue()，放一个数据到队尾，出队 dequeue()，从队头取出一个元素。队列需要两个指针：head 指针指向队头，tail 指针指向队尾
用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列
实现一个顺序队列（js 代码引用自 《学习JavaScript数据结构与算法》第四章）

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
// java
public class ArrayQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;
  // 申请一个大小为capacity的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }
  // 入队方法1  
  public boolean enqueue(String item) {
    // 如果tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }
  // 入队方法2
  public boolean enqueue(String item) {
    // tail == n 表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0，表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后更新 head 和 tail
      tail -= head;
      head = 0;
    }
    items[tail] = item;
    ++tail;
    return true;
  }
  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    ++head;
    return ret;
  }
}

// js 数组实现
function Queue() {
  var items = []
  // 向队尾添加新项
  this.enqueue = function(element) {
    items.push(element)
  }
  // 移除队列第一项并返回
  this.dequeue = function() {
    return items.shift()
  }
  // 返回队列第一个元素
  this.front = function() {
    return items[0]
  }
  // 是否为空队列
  this.isEmpty = function() {
    return items.length == 0
  }
  // 清空队列
  this.clear = function() {
    items = []
  }
  // 返回队列包含的元素个数
  this.size = function() {
    return items.length
  }
  // 辅助方法：将队列里的元素输出到控制台
  this.print = function() {
    console.log(items.toString())
  }
}

入队时，如果没有空闲空间了才集中触发一次数据搬移（入队方法2），这样使入队的时间复杂度为 O(1)
链式队列QueueBasedOnLinkedList.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
class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}

class QueueBasedOnLinkedList {
  constructor() {
    this.head = null
    this.tail = null
  }
  // 入队
  enqueue(value) {
    if (this.head === null) {
      this.head = new Node(value)
      this.tail = this.head
    } else {
      this.tail.next = new Node(value)
      this.tail = this.tail.next
    }
  }
  // 出队
  dequeue() {
    if (this.head !== null) {
      const value = this.head.element
      this.head = this.head.next
      return value
    } else {
      return -1
    }
  }
}

循环队列

循环队列可以避免数据搬移，但要确定好队空和队满的条件。数组实现的非循环队列中，tail == n 时队满，head == tail 时队空。循环队列 head == tail 时队空，满足 (tail+1)%n=head 时队满。当队满时 tail 指向的位置没有保存数据，也就是说循环队列会浪费一个数组的存储空间

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
public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

CircularQueueBasedOnLinkedList.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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}

class CircularQueue {
  constructor() {
    this.head = null
    this.tail = null
  }

  // 入队
  enqueue(element) {
    // 头指针指向 null 时是空队列
    if(this.head === null ) {
      // 头指针指向入队的新元素
      this.head = new Node(element)
      // 首尾相连构成循环队列
      this.head.next = this.head
      // 头指针和尾指针指向同一个元素
      this.tail = this.head
    } else {
      // 队列只有一个元素时 this.head 需要处理
      const flag = this.head === this.tail
      // 将新入队的元素添加到队尾
      this.tail.next = new Node(element)
      // 新元素的 next 后继指针指向头指针构成循环
      this.tail.next.next = this.head
      // 尾指针指向新元素
      this.tail = this.tail.next
      // 如果队列之前仅有一个元素，那么 this.head 由原来指向第一个元素自身改为指向新添加到队尾的第二个元素 this.tail
      if(flag){
        this.head.next = this.tail
      }
    }
  }

  // 出队
  dequeue() {
    // 空队列返回 -1
    if(this.head == null) return -1
    // 仅有一个元素，返回数值，清除头尾指针
    if(this.head === this.tail) {
      const value = this.head.element
      this.head = null
      this.tail = null
      return value
    } else {
      // 多个元素，返回数值，更新头尾指针
      const value = this.head.element
      this.head = this.head.next
      this.tail.next = this.head
      return value
    }
  }

  // 打印并清空队内元素
  display() {
    let res = 0
    while (res !== -1) {
      res = this.dequeue()
      console.log(res)
    }
  }
}

阻塞队列

阻塞队列是在队列的基础上增加了阻塞操作：在队列为空的时候，从队列头部获取数据会被阻塞，指导队列中有了数据才能返回；如果队列已满，那么插入操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。可以使用阻塞队列轻松实现一个“生产者-消费者模型”。当资源有限的情况下，比如线程池，线程池没有空闲线程时，新的任务请求线程资源一般有两种处理方式：第一种是非阻塞的处理方式，直接拒绝任务；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时取出进行处理。基于数组或链表可以实现两种队列，基于链表的队列，可以无线排队。但排队太多会导致响应时间过长，对于对响应时间敏感的系统不适合。基于数组实现的有限队列，队列大小有限，如果队列已满，新的请求会被直接拒绝，这样对响应时间敏感的系统相对合理

并发队列

在多线程的情况下，会有多个线程同时操作队列，这时候就会有线程安全问题。线程安全的队列叫做并发队列。最简单的实现方式是直接在 enqueue()、dequeue() 方法上加锁，同一时刻只允许一个存或者取操作。

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

持续学习