目录

认识队列

生活中的队列

开发中队列的应用

队列类的创建

队列的常见操作

击鼓传花

import ArrayQueue from "./01_实现队列结构Queue";

function hotPotato(names: string[], num: number): 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) {
    // 1/2不淘汰
    for (let i = 1; i < num; i++) {
      const name = queue.dequeue();
      if (name) queue.enqueue(name);
    }
    // 3淘汰
    queue.dequeue();
  }

  // 4.取出最后一个人的索引  !类型断言，确保是有值的，不是undefined
  const leftName = queue.dequeue()!;
  const index = names.indexOf(leftName);

  return index;
}

const leftIndex = hotPotato(
  ["why", "james", "kobe", "curry", "abc", "cba", "nba", "mba"],
  4
);
console.log(leftIndex);

什么是约瑟夫环问题（历史）？

import ArrayQueue from "./01_实现队列结构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++) {
      // 下面代码执行逻辑是先出队，再入队 类型断言 告诉代码有返回值，不为undefined
      queue.enqueue(queue.dequeue()!);
    }
    queue.dequeue();
  }

  return queue.dequeue()!;
}

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