前言
队列相信大家都不陌生，它是属于数据结构等一种，不同种类的数据结构适合不同种类的应用，部分数据结构甚至是为了解决特定问题而设计出来的。而对于我们前端技术人员来说，理解数据结构都非常重要。在我们解决一些问题的时候，使用不同的数据结构会带来不同性能，因此数据结构是这些问题的解决方案中不可或缺的一部分。
使用场景
之前在做IM相关产品的时候，会经常用到队列，比如说之前有遇到一个场景，进入到多人聊天室时会将未读消息批量加载，然后通过消息获取到对应信息后，为了保证消息顺序的正确，需要一条一条按序存入IndexDB中。这里就会使用到队列，最先存进来的获取数据的消息会被最先放入到IndexDb当中。
还有一个场景大家肯定不陌生，那就是事件循环Event Loop。先将执行栈中的宏任务和微任务分别放入队列中，再从队列中取出来依次执行。
定义
队列是遵循FIFO(First In First Out，先进先出，也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。跟它相反的是栈，遵循先入后出(LIFO，last-in-first-out) 的原则。
举个简单例子，我们做核酸排队，其实就是一个简单的队列。最先来的人最先捅嗓子眼，后面来的人需要在我后面排队，等我捅完之后再捅。我简单的画了张图，理解一下相关的定义。
简单版
利用数组的shift、push方法，实现一个简单版的队列。
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
| class Queue {
constructor() {
this.queueList = []
}
dequeue(el) {
this.queueList.push(el)
}
enqueue() {
return this.queueList.shift()
}
size() {
return this.queueList.length
}
clear() {
this.queueList = []
}
isEmpty() {
return this.queueList.length === 0
}
}
const queue = new Queue()
queue.dequeue(1)
queue.dequeue(2)
queue.dequeue(false)
console.log(queue.enqueue(), queue.isEmpty())
|
链式队列
理解
链式队列相对于上一版就要复杂些，它的结构就像一个链条一样，一环扣一环。在队列中，每一个元素通过next指向下一个元素，下一个元素又会有next指向它后面的，这样各元素就通过next连接起来，形成一条链子。
同时还会有两个指针，一个指针指向队头元素，另外一个指针指向队尾元素。当元素位置发生变动时，这两个指针也会随之改变。这里我们用head表示队头，tail表示队尾，next为当前元素的下一个元素，看一下整个流程。
执行enqueue入队操作，此时A4的next指向空，tail指向A[3]。当A5执行enqueue入队操作时，A4的next就会指向A5, 同时tail也会指向，A5的next就会为null
执行dequeue出队操作，首先A0的next不会指向A1，因为A0已经出去了，不在当前队列中。然后head会指向A1，成为新的队头。
Node节点
理解完上面一张图，我们来先来实现一下enqueue入队操作。在入队前，我们需要先定义一个Node节点，用来表示每一个元素。
1
2
3
4
5
6
| class Node {
constructor(element) {
this.element = element
this.next = null
}
}
|
这个代码很简单，就是实现一个Node节点的时候，将元素放入element，同时给它添加一个next属性，用来指向下一个节点。
创建队列
接下来创建队列，先声明一下类，定义属性。
1
2
3
4
5
6
7
8
9
10
| class MyQueue {
constructor() {
this.size = 0
this.head = null
this.tail = null
}
}
|
enqueue
然后按照上面的思路，实现一下enqueue操作，需要进行以下几个操作。
- 创建节点
Node - 添加元素
- 如果当前队列为空，添加到
head - 如果当前队列不为空，添加到
tail
- 修改
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
|
enqueue(value) {
if (!value) return false
const node = new Node(value)
if (this.isEmpty()) {
this.head = node
} else {
const currentNode = this.tail
currentNode.next = node
}
this.tail = node
this.size++
console.log('enqueue element', value)
}
|
测试代码
1
2
3
4
| const testQueue = new MyQueue();
testQueue.enqueue('vue')
testQueue.enqueue('react')
testQueue.enqueue('angular')
|
dequeue
接下来是出队，主要是以下几个步骤。
- 判断是否为空
- 队列为不为空，获取头部
head元素返回。 - 队列为空，不执行。
- 修改队列长度
- 将头部指针指向
next中的元素 - 清空队尾
tail - 返回队头
head元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
dequeue(){
if (this.isEmpty()) {
return
}
const currentHead = this.head
this.head = currentHead.next
this.size--
this.tail = null
return currentHead.element
}
|
测试代码
1
2
3
4
5
6
7
8
| const testQueue = new MyQueue();
testQueue.enqueue('vue')
testQueue.enqueue('react')
console.log(testQueue.dequeue(), '---dequeue1')
console.log(testQueue.dequeue(), '---dequeue2')
console.log(testQueue.dequeue(), '---dequeue3')
testQueue.enqueue('angular')
console.log(testQueue.dequeue(), '---dequeue4')
|
其他方法
主要的功能已经实现了，剩下的几个简单方法，对应注释我都写上了。
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
|
clear() {
this.size = 0
this.head = null
this.tail = null
}
getSize(){
return this.size
}
isEmpty() {
return this.size === 0 && this.head === null
}
print() {
let queueStr = ''
if (!this.isEmpty()) {
let tempNode = this.head
while(tempNode) {
queueStr += tempNode.element +( tempNode.next ? '--->' :'')
tempNode = tempNode.next
}
}
return queueStr
}
|
完整代码
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
| class Node {
constructor(element) {
this.element = element
this.next = null
}
}
class MyQueue {
constructor() {
this.size = 0
this.head = null
this.tail = null
}
enqueue(value) {
if (!value) return false
const node = new Node(value)
if (this.isEmpty()) {
this.head = node
} else {
const currentNode = this.tail
currentNode.next = node
}
this.tail = node
this.size++
console.log('enqueue element', value)
}
dequeue(){
if (this.isEmpty()) {
return
}
const currentHead = this.head
this.head = currentHead.next
this.size--
this.tail = null
return currentHead.element
}
clear() {
this.size = 0
this.head = null
this.tail = null
}
getSize(){
return this.size
}
isEmpty() {
return this.size === 0 && this.head === null
}
print() {
let queueStr = ''
if (!this.isEmpty()) {
let tempNode = this.head
while(tempNode) {
queueStr += tempNode.element +( tempNode.next ? '--->' :'')
tempNode = tempNode.next
}
}
return queueStr
}
}
const testQueue = new MyQueue();
testQueue.enqueue('vue')
testQueue.enqueue('react')
console.log(testQueue.dequeue(), '---dequeue1')
console.log(testQueue.dequeue(), '---dequeue2')
console.log(testQueue.dequeue(), '---dequeue3')
testQueue.enqueue('angular')
console.log(testQueue.dequeue(), '---dequeue4')
|
yocto-queue源码
看一下yocto-queue的实现逻辑，大体逻辑上是差不多，但多了几个知识点。
自定义迭代器
在print打印队列函数，这里是用了是用了Symbol.iterator自定义了一个迭代器，可以遍历整个队列，提供外界使用。
Class getter setter
在size函数前面有一个 get关键字，可以直接获取到return返回的值，。同理，如果前面是set，就可以直接修改数据。
私有属性#
我们都知道，class类的属性默认都是公有的，在实现类的后，可以访问到类里面的属性。但可以使用增加哈希前缀 # 的方法来定义私有类字段
1
2
3
4
5
6
7
8
9
| class Add {
[[count]] = 0;
value() {
return this.#count;
}
increment() {
this.#count++;
}
}
|
上面代码中，#count就是私有属性，只能在类的内部使用（this.#count）。如果在类的外部使用，就会报错，这个就很好理解。
1
2
3
| const counter = new Add();
counter.#count
counter.#count = 42
|
总结
看完yocto-queue的实现后不由感慨，原来队列实现还可以这么优雅简洁，迭代器的使用也是很巧妙，这个思路可以收藏✅。写完后发现，数组版本和链式版本有啥区别？明明链式版本更简单易懂，为什么还要实现链式版本？后来刷题的时候才想通。数组的特点是查询数据快，插入数据慢，查询的时间复杂度是O(1)，插入的时间复杂度是O(n)。它插入元素时，移动的是整个数组。而链式结构刚好和它相反，在查询时的复杂度是O(n)，插入的是O(1)。插入元素只需要修改next指向就可以，比数组快上不少，这就是数据结构的魅力。
