JS数据结构-队列

// 不用数组是因为数组删除第一个元素,后面所有元素都会前移,效率很低
class Queue{
  // 一个对象来存储数据
  items = {}
  // 记录队头元素的指针
  head = 0
  // 记录队尾元素的指针
  last = 0
  
  enqueue(item){
    this.items[this.last]=item
    this.last++
  }
  
  dequeue(){    //判断队列为空则无法出队
    if(this.isEmpty()){
      return;
    }
    let res = this.items[this.head]
    delete this.items[this.head]
    this.head++
    return res
  }
  
  size(){
    return this.last - this.head
  }
  
  isEmpty(){
    return this.size()===0
  }
}

// 实现击鼓传花游戏
function game(arr,times){
    let queue = new Queue()
    
    arr.map((item)=>{
      queue.enqueue(item)
    })
  
    //判定
    while(queue.size()>1){
      for(let i = 0;i<times;i++){
        queue.enqueue(queue.dequeue())
      }
      console.log(`第${arr.length+1-queue.size()}轮,${queue.dequeue()} 出局了`)
    }
  
  console.log(`获胜者是${queue.dequeue()}`)
}

//参赛人员
const arr = ['肖斌','杜凯','吴磊','伍敏','黄诚']
game(arr,4) 
/*
"第1轮,黄诚 出局了"
"第2轮,肖斌 出局了"
"第3轮,吴磊 出局了"
"第4轮,伍敏 出局了"
"获胜者是杜凯"
*/