队列

概念

一个 队列(queue) 是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。（受限的线性表，先进先出）

队列基本操作有两种：入队和出队。

从队列的后端位置添加实体，称为入队；

从队列的前端位置移除实体，称为出队。

队列中元素先进先出 FIFO (first in, first out)的示意

生活中的例子：打印队列、上厕所队列、买票队列、线程队列

基于数组实现队列

队列常见操作

• enqueue(element): 向队列尾部添加一个（多个）元素
• dequeue(): 移除队列的第一个（即排在最前面的）项，并返回被移除的元素
• front(): 返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与 Stack 类的 peek 方法非常类似）
• isEmpty(): 如果队列中不包含任何元素，返回 true，否则返回 false
• size(): 返回队列包含的元素个数，与数组的 length 属性类似
• toString(): 将队列中的内容，转成字符串形式

class Queue {
	constructor() {
		this.items = []
	}
	// 1.将元素加入到队列中
	enqueue(element) {
		this.items.push(element)
	}
	// 2.从队列中删除前端的元素
	dequeue() {
		return this.items.shift() // 从前删
	}
	// 3.查看队列前端的元素
	front() {
		return this.items[0]
	}
	// 4.查看队列是否为空
	isEmpty () {
		return this.items.length === 0
	}
	// 5.查看队列中元素的个数
	size () {
		return this.items.length
	}
	// 6.toString 方法
	toString () {
		let resultString = ''
		for (let i = 0; i < this.items.length; i++) {
			resultString += this.items[i] + ''
		}
		return resultString
	}
}

// 使用队列
let queue = new Queue()
queue.enqueue('abc')
queue.enqueue('abc1')
queue.enqueue('abc2')
queue.dequeue()
console.log(queue.front())

代码实现

击鼓传花

原游戏规则：

班级中玩儿一个游戏，所有学生围成一圈，从某位同学手里开始向旁边的同学传一束花，这个时候某个人（比如班长），在击鼓，鼓声停下的一刻，花落在谁手里，谁就出来表演节目。

修改游戏规则：

几个朋友一起玩一个游戏，围成一圈，开始数数，数到某个数字的人自动淘汰，最后剩下的这个人会获得胜利，请问最后剩下的是原来在哪一个位置上的人？

  function passGame (nameList, num) {
    // 1.创建一个队列结构

    let queue = new Queue()

    // 2.将所有人依次加入到队列中
    for (let i = 0; i < nameList.length; i++) {
      queue.enqueue(nameList[i])
    }

    // 3.开始数数
    while(queue.size() > 1) {
      // 不是 num 的时候，重新加入到队列的末尾，是 num 这个数字的时候，将其从队列中删除
      for (let i = 0; i < num - 1; i++) {
        // 3.1 num 数字之前的人重新放到队列末尾
        queue.enqueue(queue.dequeue())
      }
      // 3.2 num 对应的人，直接从队列中删除
      // num 对应这个人，直接从队列中删除
      // 由于队列没有像数组一样的下标值不能直接取到某一元素，
      // 所以采用，把 num 前面的 num - 1 个元素先删除后添加到队列末尾，
      // 这样第 num 个元素就排到了队列的最前面，可以直接使用 dequeue 方法进行删除
      queue.dequeue()
    }

    // 4.获取剩下的人
    let endName = queue.front()
    console.log('最后剩下的人', endName)
    return nameList.indexOf(endName)

  }

  console.log(passGame (['lili', 'lucy', 'tom', 'lilei', 'why'], 3), '最后的下标值')