队列简介
队列是是一种受限的线性表，特点为先进先出（FIFO：first in first out）。
- 受限之处在于它只允许在表的前端（front）进行删除操作；
- 在表的后端（rear）进行插入操作；
相当于排队买票，先来的先买票，后来的后买票。
队列的应用：
- 打印队列：计算机打印多个文件的时候，需要排队打印；
- 线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待 CPU 处理；
队列类的实现：
队列的实现和栈一样，有两种方案：
队列的常见操作：
enqueue(element)：向队列尾部添加一个（或多个）新的项。
dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。
isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。
size()：返回队列包含的元素个数，与数组的length属性类似。
封装队列类
使用 ES5 实现
测试代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
let queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
console.log(queue)
queue.dequeue()
console.log(queue)
queue.dequeue()
console.log(queue)
console.log(queue.front())
console.log(queue.isEmpty())
console.log(queue.size())
console.log(queue.toString())
|
测试结果：
使用 ES6 实现
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
| export class Queue {
constructor() {
this.items = []
}
enqueue(element) {
this.items.push(element)
}
dequeue() {
return this.items.shift()
}
front() {
if (this.items.length === 0) return null
return this.items[0]
}
isEmpty() {
return this.items.length === 0
}
size() {
return this.items.length
}
}
|
优先级队列
优先级队列的特点
- 我们知道, 普通的队列插入一个元素, 数据会被放在后端. 并且需要前面所有的元素都处理完成后才会处理前面的数据.
- 但是优先级队列, 在插入一个元素的时候会考虑该数据的优先级.(和其他数据优先级进行比较)
- 比较完成后, 可以得出这个元素正确的队列中的位置. 其他处理方式, 和队列的处理方式一样.
- 也就是说, 如果我们要实现优先级队列, 最主要是要修改添加方法. (当然, 还需要以某种方式来保存元素的优先级)
优先级队列应用
- 一个现实的例子就是机场登机的顺序
- 头等舱和商务舱乘客的优先级要高于经济舱乘客。
- 在有些国家，老年人和孕妇（或带小孩的妇女）登机时也享有高于其他乘客的优先级。
- 另一个现实中的例子是医院的（急诊科）候诊室。
- 医生会优先处理病情比较严重的患者。
- 通常，护士会鉴别分类，根据患者病情的严重程度放号。
- 计算机中, 我们也可以通过优先级队列来重新排序队列中任务的顺序
- 比如每个线程处理的任务重要性不同, 我们可以通过优先级的大小, 来决定该线程在队列中被处理的次序.
实现优先级队列主要考虑的问题
- 封装元素和优先级放在一起(可以封装一个新的构造函数)
- 添加元素时, 将当前的优先级和队列中已经存在的元素优先级进行比较, 以获得自己正确的位置.
使用 ES5 实现
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
|
function PriorityQueue() {
function QueueElement(element, priority) {
this.element = element
this.priority = priority
}
this.items = []
PriorityQueue.prototype.enqueue = (element, priority) => {
let queueElement = new QueueElement(element, priority)
if (this.items.length == 0) {
this.items.push(queueElement)
} else {
let added = false
for (let i of this.items) {
if (queueElement.priority < i.priority) {
this.items.splice(i, 0, queueElement)
added = true
break
}
}
if (!added) {
this.items.push(queueElement)
}
}
}
PriorityQueue.prototype.dequeue = () => {
return this.items.shift()
}
PriorityQueue.prototype.front = () => {
return this.items[0]
}
PriorityQueue.prototype.isEmpty = () => {
return this.items.length == 0
}
PriorityQueue.prototype.size = () => {
return this.items.length
}
PriorityQueue.prototype.toString = () => {
let resultString = ''
for (let i of this.items) {
resultString += i.element + '-' + i.priority + ' '
}
return resultString
}
}
|
测试代码：
1
2
3
4
5
6
7
8
|
let pq = new PriorityQueue()
pq.enqueue('Tom', 111)
pq.enqueue('Hellen', 200)
pq.enqueue('Mary', 30)
pq.enqueue('Gogo', 27)
console.log(pq)
|
测试结果：
使用 ES6 实现
继承自上面的队列即可，部分方法重新封装
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 QueueElement {
constructor(element, priority) {
this.element = element
this.priority = priority
}
}
export class PriorityQueue extends Queue {
enqueue(element, priority) {
const queueElement = new QueueElement(element, priority)
if (this.items.length === 0) {
this.items.push(queueElement)
} else {
let added = false
for (let i = 0; i < this.items.length; i++) {
const element = this.items[i]
if (element.priority > queueElement.priority) {
this.items.splice(i, 0, queueElement)
added = false
break
}
}
if (!added) {
this.items.push(queueElement)
}
}
}
}
|
代码解析
- 封装了一个 QueueElement, 将 element 和 priority 封装在一起.
- 在插入新的元素时, 有如下情况下考虑:
- 根据新的元素先创建一个新的 QueueElement 对象.
- 如果元素是第一个被加进来的, 那么不需要考虑太多, 直接加入数组中即可.
- 如果是后面加进来的元素, 需要和前面加进来的元素依次对比优先级.
- 一旦优先级, 大于某个元素, 就将该元素插入到元素这个元素的位置. 其他元素会依次向后移动.
- 如果遍历了所有的元素, 没有找到某个元素被这个新元素的优先级低, 直接放在最后即可.
队列的应用(击鼓传花)
使用队列实现小游戏：击鼓传花，传入一组数据和设定的数字 num，循环遍历数组内元素，遍历到的元素为指定数字 num 时将该元素删除，直至数组剩下一个元素。
击鼓传花的规则
- 原游戏规则:
- 班级中玩一个游戏, 所有学生围成一圈, 从某位同学手里开始向旁边的同学传一束花.
- 这个时候某个人(比如班长), 在击鼓, 鼓声停下的一颗, 花落在谁手里, 谁就出来表演节目.
- 修改游戏规则:
- 我们来修改一下这个游戏规则.
- 几个朋友一起玩一个游戏, 围成一圈, 开始数数, 数到某个数字的人自动淘汰.
- 最后剩下的这个人会获得胜利, 请问最后剩下的是原来在哪一个位置上的人?
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function passGame(nameList, num) {
const queue = new Queue()
for (let i = 0; i < nameList.length; i++) {
const element = nameList[i]
queue.enqueue(element)
}
while (queue.size() > 1) {
for (let i = 1; i < num - 1; i++) {
queue.enqueue(queue.dequeue())
}
queue.dequeue()
}
return queue.front()
}
|
详解：
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
|
let passGame = (nameList, num) => {
let queue = new Queue()
for (let i of nameList) {
queue.enqueue(i)
}
while (queue.size() > 1) {
for (let i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue())
}
queue.dequeue()
}
console.log(queue.size())
let endName = queue.front()
console.log('最终剩下的人：' + endName)
return nameList.indexOf(endName)
}
let names = ['lily', 'lucy', 'Tom', 'Lilei', 'Tony']
console.log(passGame(names, 3))
|
图解
注意点
关于数组方法 splice 用法：
- splice（1，0，’Tom’）：表示在索引为 1 的元素前面插入元素’Tom‘（也可以理解为从索引为 1 的元素开始删除，删除 0 个元素，再在索引为 1 的元素前面添加元素’Tom’）；
- splice（1，1，’Tom’）：表示从索引为 1 的元素开始删除（包括索引为 1 的元素），共删除 1 个元素，并添加元素’Tom’。即把索引为 1 的元素替换为元素’Tom’。
数组的 push 方法在数组、栈和队列中的形式：
- 数组：在数组[0，1，2]中，pop(3)，结果为[0，1，2，3]；
- 栈：执行 pop(0)，pop(1)，pop(2)，pop(3)，从栈底到栈顶的元素分别为：0，1，2，3；如果看成数组，可写为[0，1，2，3]，但是索引为 3 的元素 3 其实是栈顶元素；所以说栈的 push 方法是向栈顶添加元素（但在数组的视角下为向数组尾部添加元素）；
- 队列：enqueue 方法可以由数组的 push 方法实现，与数组相同，相当于在数组尾部添加元素。
可以这样想：栈结构是头朝下（索引值由下往上增大）的数组结构。
