Home 数据结构与算法 data structure

# 队列结构（Queue）

  • 队列是一个简单的数据结构，它是一个 允许在一端进行插入操作，而在另一端进行删除操作的线性表 。队列遵循先进先出（FIFO, First-In-First-Out）的特征，和栈（LIFO, Last In First Out）刚好相反。

  • 队列，它是一种受限的线性表

    • 受限之处在于它只允许在表的前端 (front) 进行删除操作
    • 而在表的后端 (rear) 进行插入操作

  • 生活中类似的队列结构

    • 比如电影院、商城、奶茶店排队
    • 优先排队的人，优先处理

# 实现队列

  • 封装一个队列实现下面的击鼓传花
// 封装队列类
function Queue() {
  // 属性
  this.items = []
  // 方法
  // 1. 将元素加入到队列中
  Queue.prototype.enqueue = function (...args) {
    this.items.push(...args)
  }
  // 2. 从队列中删除前端元素
  Queue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 3. 查看前端的元素
  Queue.prototype.front = function () {
    return this.items[0]
  }
  // 4. 查看队列是否为空
  Queue.prototype.isEmpty = function () {
    return this.items.length === 0
  }
  // 5. 查看队列中元素个数
  Queue.prototype.size = function () {
    return this.items.length
  }
  // 6.toString 方法
  Queue.prototype.toString = function () {
    let resStr = ''
    for (key of this.items) {
      resStr+= key
    }
    return resStr
  }
}
# Example


    

  • 原游戏击鼓传花规则是，例如班级的学生围城一圈，从某位学生手里向旁边的同学传一束花。这个时候某个人在击鼓， 鼓声停下的一刻，花落在谁手里，谁就出来表演节目
    • 

  • 修改游戏规则

      

    • 学生们围成一圈， 开始数数， 数到某个数的人自动淘汰，最后剩下的人获得游戏胜利，并获得胜利者的位置。
      • 

    

    • 



Example 1:


输入：['樱岛麻衣', '小鸟游六花', '入间同学'], 6
输出：el: 入间同学  index: 2
    

  • 解释：从 0 开始数到 6 是樱岛麻衣，那么樱岛麻衣被淘汰此时数组剩下两个元素 [' 小鸟游六花 ', ' 入间同学 '],
    • 

  • 接着被淘汰的元素往下从 0 数到 6，是小鸟游六花，那么小鸟游六花被淘汰
    • 

  • 此时数组只剩下入间同学，并获取原来的下标值，那么就是 2
    • 



Example 2:


输入：['Saber', 'Lain', 'Nico'], 8
输出：el: Lain  index: 1
# Solving Ideas


    

  • 我们使用上面封装的队列方法实现击鼓传花
    • 



function passGame(nameList, num) {
  // 1. 创建一个队列
  const queue = new Queue()
  // 2. 将所有人依次加入到队列中
  for (let i = 0; i < nameList.length; i++){
    queue.enqueue(nameList[i])
  }
  // 3. 开始数数字
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue())
    }
    queue.dequeue()
  }
  return `index: ${nameList.indexOf(queue.front())} : el: ${queue}`
}
const res = passGame(['Saber', 'Lain', 'Nico', 'Nekoaimer'], 10)
console.log(res) // el: Nekoaimer  index: 3