说一下这个基于数组实现队列 根据队列特性实现击鼓传花

实现思路

队列的核心思想是先进先出(FIFO),队列支持从前端(front)移除数据,从后端(rear)插入数据
实现一个队列需要具备以下方法
  • 将元素加入到队列
  • 删除队列前端元素
  • 查看队列前端元素
  • 查看队列是否为空
  • 查看队列大小
  • 查看队列内所有元素
  • 清空队列

实现代码

/**
 * 基于数组实现队列
 */
function Queue() {
  this.items = []
  //将元素加入到队列
  Queue.prototype.enqueue = function(elem) {
    this.items.push(elem)
  }
  //删除队列前端元素并返回
  Queue.prototype.dequeue = function() {
    return this.items.shift()
  }
  //查看队列前端元素
  Queue.prototype.front = function() {
    return this.items[0]
  }
  //查看队列是否为空
  Queue.prototype.isEmpty = function() {
    return this.items.length === 0
  }
  //查看队列大小
  Queue.prototype.size = function() {
    return this.items.length
  }
  //查看队列内所有元素
  Queue.prototype.toString = function() {
    return this.items.toString()
  }
  //清空队列
  Queue.prototype.clear = function() {
    this.items = []
  }
}

击鼓传花

给定参与游戏的人员和多少次为一轮
/**
 * 击鼓传花
 * @param nameList 参与人员列表
 * @param num 多少次为一轮
 * @returns { losers: [], winner: string }
 */
function passGame(nameList, num) {
  //实例化队列
  let queue = new Queue()
  //淘汰玩家列表
  let losers = []
  //添加人员到游戏中
  for(let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i])
  }
  //只要游戏中人数大于1就继续
  while(queue.size() > 1) {
    for(let i = 0; i < num; i++) {
      //将队首的玩家添加到队尾
      queue.enqueue(queue.dequeue())
    }
    //淘汰玩家
    losers.push(queue.dequeue())
  }
  //游戏结束
  return {
    losers,
    winner: queue.dequeue()
  }
}

正文完