队列（Queue）：“先进先出”的数据结构
队列是线性表的一种，在操作数据元素时，和栈一样，有自己的规则：使用队列存取数据元素时，数据元素只能从表的一端进入队列，另一端出队列
- 队列从一端存入数据，另一端调取数据的原则称为“先进先出”原则。（
first in first out，简称“FIFO”） - 根据队列的先进先出原则，（
a1,a2,a3,…,an）中，由于 a1 最先从队尾进入队列，所以可以最先从队头出队列，对于 a2 来说，只有 a1 出队之后，a2 才能出队。
类似于日常生活中排队买票，先排队（入队列），等自己前面的人逐个买完票，逐个出队列之后，才轮到你买票。买完之后，你也出队列。先进入队列的人先买票并先出队列（不存在插队）。
队列的实际应用
队列在操作系统中应用的十分广泛，比如用它解决 CPU 资源的竞争问题。
对于一台计算机来说，CPU 通常只有 1 个，是非常重要的资源。如果在很短的时间内，有多个程序向操作系统申请使用 CPU，就会出现竞争 CPU 资源的现象。不同的操作系统，解决这一问题的方法是不一样的，有一种方法就用到了队列这种存储结构。
假设在某段时间里，有 A、B、C 三个程序向操作系统申请 CPU 资源，操作系统会根据它们的申请次序，将它们排成一个队列。
根据“先进先出”原则，最先进队列的程序出队列，并获得 CPU 的使用权。
待该程序执行完或者使用 CPU 一段时间后，操作系统会将 CPU 资源分配给下一个出队的程序，以此类推。
如果该程序在获得 CPU 资源的时间段内没有执行完，则只能重新入队，等待操作系统再次将 CPU 资源分配给它。
队列还可以用来解决一些实际问题，比如实现一个简单的停车场管理系统、实现一个推小车卡牌游戏等
队列的具体实现
和栈的实现方案一样，队列的实现也有两种方式，分别是：
这里我们还是先用 JavaScript 内置的数组顺序存储结构，来实现我们的队列
一个队列类，应有的属性和方法
interface Iqueue<T> {
items: T[]; // 顺序队列 底层一样基于数组实现！
enQueue(ele: T): T[]; // 入队
deQueue(): T; // 出队
toString(): string; // 队列字符串化
size(): number; // 队列长度
front(): T; // 排在队伍最前面的元素
}
export default class Queue<T> implements Iqueue<T> {
items: T[] = [];
enQueue(ele: T): T[] {
this.items.unshift(ele);
return this.items;
}
deQueue(): T {
return this.items.pop() as T
}
size(): number {
return this.items.length;
}
toString(): string {
return this.items.toString();
}
front(): T {
return this.items[0]
}
}
测试队列 [按照个人习惯，队伍是从右往左排队的]
import Queue from "./2.线性结构Queue 队列";
import { passGame } from "./2.线性结构Queue 队列/击鼓传花";
const q = new Queue<number>();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
console.log(q.toString()); // 3,2,1
q.deQueue(); // 最前面的 1 出队
console.log(q.toString()); // 3,2
console.log(q.size()); // 2
console.log(q.front()); // 3
约瑟夫环
约瑟夫环问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。
出列顺序依次为：
- 编号为 3 的人开始数，数到2的人被淘汰，他先数 1，然后 4 数 2，所以 4 先出列；
- 4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；
- 1 出列后，从 2 开始数 1，3 数 2，所以 3 出列；
- 3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；
- 最后只剩下 5 自己，所以 5 胜出。
import Queue from ".";
/**
*
* @param list 玩游戏的人
* @param point 数的数字
* @description 游戏规则，从第某一个人开始数数！数到某个数字的人被淘汰，最后一个人存活！
*/
export function passGame(nameList: string[], point: number): string {
// 1. 创建一个队列
const q = new Queue<string>()
// 2. 首先把所有人放到队列中
for (let i = 0; i < nameList.length; i++) {
q.enQueue(nameList[i])
}
// 3. 如果队列长度大于1 则证明游戏尚未结束
while (q.size() > 1) {
/**
* 3.1 每一次都从队列的第一个人开始，数到目标 point
* 尚未到目标值之前,也就是 point - 1 ，都把数过的元素，重新放到队列后面，继续新一轮的游戏
*/
for (let idx = 0; idx < point - 1; idx++) {
q.enQueue(q.deQueue())
}
// 3.3 数到 point 的就代表游戏结束，踢出队列
q.deQueue()
}
return q.front()
}
测试代码：
const list = ['雷神将军', "琴", "凝光", "七七", "烟绯"]
const winner = passGame(list, 3)
console.log({winner}); // { winner: '七七' }
那么这个过程就是
-
先把list排好队，
- 按照队列
入 => [ '烟绯', '七七', '凝光', '琴', '雷神将军' ] => 出
- 按照队列
-
从
雷电将军开始数，数到凝光被淘汰，刚刚数过的就继续从新排队进入队列，[ '琴', '雷神将军', '烟绯', '七七' ]
-
然后继续从
七七开始数，数到雷神将军被淘汰[ '烟绯', '七七', '琴' ] -
然后从
'琴'开始数，数到'烟绯',被淘汰[ '七七', '琴' ] -
最后 又从
琴开始 数到 琴自己被淘汰，七七获胜
评论区