队列结构
普通队列
特点
队列结构是一种在头部进行删除、尾部进行插入的数据结构，其特点是“先进先出(FIFO)”。
javaScript 实现
class Queue {
constructor() {
this.container = [];
}
// 入队
enter(element) {
return this.container.push(element);
}
// 出队
leave() {
return this.container.shift();
}
// 获取长度
size() {
return this.container.length;
}
// 获取的内容
value() {
return this.container;
}
}普通队列应用场景
击鼓传花
n 个小朋友排成一个圆圈，序号从数字 1 开始，每次从这个圆圈里淘汰第 m 个小朋友。求出最后获胜的小朋友。
思路
利用队列的特性，将每个小朋友的序号存入队列，每一次循环时取出队列头部的数字，如果不是第 m 次取出数字则将取出的数字插入到队列尾部，知道最后只剩下一个数字为止；
代码
// [1,2,3,4,5]
// 第1次淘汰3之后： [4,5,1,2]
// 第2次淘汰1之后： [2,4,5]
// 第3次淘汰4之后： [2,4]
// 第4次淘汰2之后： [4]
// 最终结果为：4
function game(n, m) {
// n：多少人来玩
// m：数到m的人移除掉
let queue = new Queue();
for (let i = 1; i <= n; i++) {
queue.enter(i);
}
while (queue.size() > 1) {
for (let i = 1; i < m; i++) {
queue.enter(queue.leave());
}
queue.leave();
}
return queue.value().toString();
}
console.log(game(5, 3)); // 4优先级队列
特点
优先级队列和普通队列的区别在于：普通队列插入一个元素，数据会被放在队列末尾，并且需要前面所有的元素都处理完成之后才会处理后面插入的数据。但是优先级队列在插入元素的时候还会考虑该数据的优先级，会将待插入数据的优先级和队列中其他数据的优先级进行比较，找到待插入元素在队列中正确的位置再进行插入。
现实应用场景
机场的登机顺序
- 头等舱和商务舱的优先级要高于经济舱乘客；
- 有些国家，老年人和孕妇(或者带小孩的妇女)登机时也享有比普通乘客更高的优先级；
医院急诊科候诊室
一般情况下是按照排号顺序就诊，但是如果有病情紧急的患者会优先处理
计算机操作系统通过优先级来进行任务的调度
比如，每个线程处理的任务重要性不通，可以通过优先级的大小来决定线程在任务队列中被处理的顺序
实现优先级队列
实现优先级队列相对于普通队列来说有两个需要注意的方面：
- 优先级队列的元素除了有本身的数据之外，应该还有一个表示优先级的属性；
- 添加元素时不能直接在队尾 push 元素，而是需要与队列中已经存在的元素的优先级进行比较，将元素插入正确的位置；
JavaScript 实现
class PriorityQueueElement {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.container = [];
}
// 插入元素
enter(element, priority) {
// 1.创建PriorityQueueElement对象
const queueElement = new PriorityQueueElement(element, priority);
// 2.如何插入元素？
if (this.isEmpty) {
// 如果当前队列为空，就直接push
this.container.push(queueElement);
} else {
// 如果当前队列中有元素，则找到元素该插入的位置
for (let i = 0; i < this.size; i++) {
if (this.container[i].priority <= queueElement.priority) {
this.container.splice(i, 0, queueElement);
break;
}
}
}
}
leave() {
return this.container.shift();
}
// 获取长度
size() {
return this.container.length;
}
// 获取的内容
value() {
return this.container;
}
// 判断队列是否为空
isEmpty() {
return this.size === 0;
}
}
