相同,仍然遵循队列的先进先出原则。如果队列中所有元素的优先级比要添加的元素的优先级都高,则将元素添加到队列的末尾。我们将print()方法也做了一些调整,以方便查看输出结果。
let queue = new PriorityQueue();
console.log(queue.isEmpty()); // true
queue.enqueue({element: 'John', priority: 2});
queue.enqueue([{element: 'Jack', priority: 1}, {element: 'Camila', priority: 1}]);
queue.print(); // Jack,Camila,John
由于John的优先级比其它两个低,所以它被排在了最后面。虽然Jack和Camila的优先级相同,但是Jack是在Camila之前先插入到队列中的,所以Jack排在了Camila之前,这也符合了我们的预期。
循环队列
我们用一个小游戏“击鼓传花”来说明循环队列在实际中的应用。
function hotPotato(nameList, num) {
let queue = new Queue();
for (let i = 0, ci; ci = nameList[i]; i++) {
queue.enqueue(ci);
}
let eliminated = '';
while(queue.size() > 1) {
for (let i = 0; i < num; i ++) {
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();
console.log(`${eliminated} has been eliminated.`);
}
return queue.dequeue();
}
let names = ['John', 'Jack', 'Camila', 'Ingrid', "Carl"];
let winner = hotPotato(names, 7);
console.log(`The winner is: ${winner}`);
在这个游戏中,我们传入由五个名字组成的数组,用来表示参加游戏的五个人,数字7表示每一轮要传递的次数。在每一个过程中,我们从队列头部取出一个元素加到队列的尾部,当次数用完的时候,将队列头部的元素取出来,作为这一轮中被淘汰的人。让我们来看一下具体的执行过程,一开始队列中的顺序是John, Jack, Camila, Ingrid, Carl,然后传递7次:
1. Jack, Camila, Ingrid, Carl, John
2. Camila, Ingrid, Carl, John, Jack
3. Ingrid, Carl, John, Jack, Camila
4. Carl, John, Jack, Camila, Ingrid
5. John, Jack, Camila, Ingrid, Carl
6. Jack, Camila, Ingrid, Carl, John
7. Camila, Ingrid, Carl, John, Jack
之后从队列中取出的是Camila。反复执行上述过程,直到队列中的元素只剩一个,这个就是最后的赢家!
下面是完整的执行结果:
Camila has been eliminated.
Jack has been eliminated.
Carl has been eliminated.
Ingrid has been eliminated.
The winner is: John
下一章我们继续来看看如何用java script来实现链表。