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函數的數字，模擬不同的場景。