学习《JavaScript 数据结构与算法》读书笔记
4 队列
4.1 队列数据结构
队列是遵循FIFO（First In First Out，先进先出，也称先来先服务）原则的一组有序的想。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。
4.2 创建队列
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
| function Queue() {
let 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.size = function() {
return items.length;
};
this.print = function() {
console.log(items.toString());
};
}
|
使用 Queue 类
1
2
3
4
5
6
7
8
9
10
11
12
| let queue = new Queue();
console.log(queue.isEmpty());
queue.enqueue('John');
queue.enqueue('Jack');
queue.enqueue('Camila');
queue.print();
console.log(queue.size());
console.log(queue.isEmpty());
queue.dequeue();
queue.dequeue();
queue.print();
|
4.3 用 ECMAScript 6 语法实现的 Queue 类
在这种方法中，我们要用一个 WeakMap 来保存私有属性 items ，并用外层函数（闭包）来封装 Queue 类。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| let Queue2 = (function() {
const items = new WeakMap();
class Queue2 {
constructor() {
items.set(this, []);
}
enqueue(element) {
let q = items.get(this);
q.push(element);
}
dequeue() {
let q = items.get(this);
let r = q.shift();
return r;
}
}
return Queue2;
})()
|
4.4 优先队列
优先队列的元素的添加和移除是基于优先级的。一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。在有些国家，老年人和孕妇（或带小孩的妇女）登机时也享有高于其他乘客的优先级。
实现一个优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除它们。在这个示例中，我们将会在正确的位置添加元素，因此可以对它们使用默认的出列操作。
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
| function PriorityQueue() {
let items = [];
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
this.enqueue = function(element, priority) {
let queueElement = new QueueElement(element, priority);
let added = false;
for(let i = 0; i < items.length; i++) {
if(queueElement.priority < items[i].priority) {
items.splice(i, 0, queueElement);
added = true;
break;
}
}
if(!added) {
items.push(queueElement);
}
};
this.print = function() {
for(let i = 0; i > items.length; i++) {
console.log(`${items[i].element} -
${items[i].priority}`);
}
};
}
|
使用 PriorityQueue 类的示例
1
2
3
4
5
| let priorityQueue = new PriorityQueue();
priorityQueue.enqueue('John', 2);
priorityQueue.enqueue('Jack', 1);
priorityQueue.enqueue('Camila', 1);
priorityQueue.print();
|
我们在这里实现的优先队列称为最小优先队列，因为优先级的值较小的元素被放置在队列最前面（1代表更高的优先级）。最大有限队列则与之相反，把优先级的值较大的元素放置在队列最前面。
4.5 循环队列 击鼓传花（Hot Potato）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function hotPotato(nameList, num) {
let queue = new Queue();
for(let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i]);
}
let eliminated = '';
while(queue.size() > 1) {
for(let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();
console.log(eliminated + '在击鼓传花游戏中被淘汰。');
}
return queue.dequeue();
}
|
1
2
3
| let names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
let winner = hotPotato(names, 7);
console.log('The winner is: ' + winner);
|
实现一个模拟击鼓传花游戏，要用到这一章开头实现的 Queue 类。
以上算法的输出如下：
Camila在击鼓传花游戏中被淘汰。
Jack在击鼓传花游戏中被淘汰。
Carl在击鼓传花游戏中被淘汰。
Ingrid在击鼓传花游戏中被淘汰。
胜利者：John
The winner is: John