队列结构

认识队列结构

队列（Queue），它是一种受限的线性表，先进先出（FIFO First In First Out）

• 受限之处在于它只允许在队列的前端（front）进行删除操作
• 而在队列的后端（rear）进行插入操作

队列

• 有五份文档需要打印，这些文档会按照次序放入到打印队列中
• 打印机会依次从队列中取出文档，优先放入的文档，优先被取出，并且对该文档进行打印
• 以此类推，直到队列中不再有新的文档

线程队列:

• 在开发中，为了让任务可以并行处理，通常会开启多个线程
• 但是，我们不能让大量的线程同时运行处理任务。（占用过多的资源）
• 这个时候，如果有需要开启线程处理任务的情况，我们就会使用线程队列
• 线程队列会依照次序来启动线程，并且处理对应的任务

当然队列还有很多其他应用，我们后续的很多算法中也会用到队列（比如二叉树的层序遍历）

队列操作

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

实现队列

队列的实现和栈一样，有两种方案：

• 基于 数组 实现
• 基于 链表 实现

import IQueue from './IQueue'

class ArrayQueue<T> implements IQueue<T> {
  // 内部是通过数组保存
  private data: T[] = []
  enqueue(element: T): void {
    this.data.push(element)
  }
  dequeue(): T | undefined {
    return this.data.shift()
  }
  peek(): T | undefined {
    return this.data[0]
  }
  isEmpty(): boolean {
    return this.data.length === 0
  }
  size(): number {
    return this.data.length
  }
}

export default ArrayQueue

泛型

interface IList<T> {
  peek(): T | undefined
  isEmpty(): boolean
  size(): number
}
interface IQueue<T> extends IList<T> {
  enqueue(element: T): void
  dequeue(): T | undefined
}

队列题型

击鼓传花

原游戏规则

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

修改游戏规则

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

封装一个基于队列的函数

• 参数：所有参与人的姓名，基于的数字口结果：最终剩下的一人的姓名

function hotPotato(names: string[], num: number) {
  if (names.length === 0) return -1
  // 1.创建队列结构
  const queue = new ArrayQueue<string>()
  // 2.将所有的name入队操作
  for (const name of names) {
    queue.enqueue(name)
  }
  // 3.淘汰规则
  while (queue.size() > 1) {
    for (let i = 1; i < num; i++) {
      const name = queue.dequeue()
      if (name) queue.enqueue(name)
    }
    queue.dequeue()
  }
  return queue.dequeue()
}

约瑟夫环问题

阿桥问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环

• 人们站在一个等待被处决的圈子里
• 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行
• 在跳过指定数量的人之后，处刑下一个人
• 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放
• 在给定数量的情况下，站在第几个位置可以避免被处决?

这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家口

• 他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中
• 他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,···,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字

例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3

import ArrayQueue from './queue'

function lastRemaining(n: number, m: number) {
  // 1.创建队列
  const queue = new ArrayQueue<number>()
  // 2.将所有的数字加入队列中
  for (let i = 0; i < n; i++) {
    queue.enqueue(i)
  }
  // 3.判断队列中是否还有数字
  while (queue.size() > 1) {
    for (let i = 1; i < m; i++) {
      queue.enqueue(queue.dequeue()!)
    }
    queue.dequeue()
  }
  return queue.dequeue()
}

console.log(lastRemaining(5, 3)) // 3
console.log(lastRemaining(10, 17)) // 2

动态规划

function lastRemaining(n: number, m: number) {
  let position = 0
  for (let i = 2; i <= n; i++) {
    position = (position + m) % i
  }
  return position
}