首页 » 学习JavaScript数据结构与算法(第2版) » 学习JavaScript数据结构与算法(第2版)全文在线阅读

《学习JavaScript数据结构与算法(第2版)》4.5 循环队列击鼓传花

关灯直达底部

还有另一个修改版的队列实现,就是循环队列。循环队列的一个例子就是击鼓传花游戏(Hot Potato)。在这个游戏中,孩子们围成一个圆圈,把花尽快地传递给旁边的人。某一时刻传花停止,这个时候花在谁手里,谁就退出圆圈结束游戏。重复这个过程,直到只剩一个孩子(胜者)。

在下面这个示例中,我们要实现一个模拟的击鼓传花游戏:

function hotPotato (nameList, num){  let queue = new Queue; // {1}  for (let i=0; i<nameList.length; i++){    queue.enqueue(nameList[i]); // {2}  }  let eliminated = '';  while (queue.size > 1){    for (let i=0; i<num; i++){      queue.enqueue(queue.dequeue); // {3}    }    eliminated = queue.dequeue;// {4}    console.log(eliminated + '在击鼓传花游戏中被淘汰。');  }  return queue.dequeue;// {5}}let names = ['John','Jack','Camila','Ingrid','Carl'];let winner =hotPotato(names, 7);console.log('The winner is: ' + winner);  

实现一个模拟的击鼓传花游戏,要用到这一章开头实现的Queue类(行{1})。我们会得到一份名单,把里面的名字全都加入队列(行{2})。给定一个数字,然后迭代队列。从队列开头移除一项,再将其添加到队列末尾(行{3}),模拟击鼓传花(如果你把花传给了旁边的人,你被淘汰的威胁立刻就解除了)。一旦传递次数达到给定的数字,拿着花的那个人就被淘汰了(从队列中移除——行{4})。最后只剩下一个人的时候,这个人就是胜者(行{5})。

以上算法的输出如下:

Camila在击鼓传花游戏中被淘汰。Jack在击鼓传花游戏中被淘汰。Carl在击鼓传花游戏中被淘汰。Ingrid在击鼓传花游戏中被淘汰。胜利者:John  

下图模拟了这个输出过程:

你可以改变传入hotPotato函数的数字,模拟不同的场景。