学习《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()); /* 3 */
console.log(queue.isEmpty()); /* false */
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}`);
}
};
/* 其他方法和默认的Queue实现相同 */
}

使用 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