我们之前已经学习过了一种受限的线性结构：栈结构，并且我们已经知道这种受限的数据结构对于解决某些特定问题，会有特别的效果，下面我们来学习另外一种受限的数据结构：队列
之前说过的栈结构是一种遵循先进后出规则的数据结构，它只允许在栈顶插入或删除元素，而队列则是遵循先进先出规则的数据结构，类似于现实生活中人们排队买火车票，先排队的先买票，先到先得，也就是它只允许在队列前端进行删除操作（买票），而在队列的后端进行插入操作（排队）
队列结构
生活中队列
- 打印队列：有五份文档需要打印，这些文档会按照次序放入到打印队列中，打印机会依次从队列中取出文档，优先放入的文档，优先会被取出并打印，依次类推直到队列中没有文档为止
- 线程队列：在开发中，为了让任务可以并行处理，通常会开启多个线程，但是，我们不能让大量的线程，同时运行处理任务（占用过多的资源）这个时候，如果有需要开启线程处理任务的情况，我们就会使用线程队列。线程队列会依照次序来启动线程，并且处理对应的任务，
队列结构的实现以及应用
下面代码中我们创建了一个队列类，并实现了队列常用的相关的方法。其实也比较简单，主要也是基于数组进行实现
// 简单的队列实现（基于数组，其实最好的方式是基于链表实现，性能会高一些）
let Queue = (function(){
let items = [];
return class {
// 向队列尾部添加一项
// 存
enqueue(element) {
items.push(element);
}
// 移除队列的第一项，并返回被移除项
// 取
dequeue() {
return items.shift();
}
// 返回队列中的第一个元素
// 查看
front() {
return items[0];
}
// 查看队列是否为空
isEmpty() {
return items.length === 0;
}
// 查看大小
size() {
return items.length;
}
// 将队列中的内容转换为字符串，并返回
toString() {
let resultString = "";
for (let i in items) {
resultString += items[i];
}
return resultString;
}
}
})()
下面介绍一个关于队列面试题：击鼓传花
游戏规则：随意人数的同学围成一圈，由某个人开始数数，比如从班长（随机的）开始，班长数1，然后旁边的人就数2，依次往后，当数到某个人数到特定数字之后(事先约定好这个数字),那么这个人将会被淘汰，此时下一个人从头开始数1。依次类推，当所有人被淘汰只留一个人的时候，即游戏结束这个人为胜者
// 击鼓传花游戏应用
function passGame(nameList, num) {
// 定义一个队列
let queue = new Queue();
// 循环角色
// 以此添加到队列中
for (let i in nameList) {
queue.enqueue(nameList[i]);
}
// 队列人数为1之前一直循环
while (queue.size() > 1) {
// 根据数字进行循环
for (let i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue());
}
// 移除数到的人
queue.dequeue();
}
return queue.front()
}
console.log(passGame(["小明","小红","小吕","张三","李四","十五"],7))
优先级队列
优先级队列的特点，我们知道普通的队列插入一个元素，数据会直接被放在队尾，但是优先级队列在插入一个新元素前会考虑该数据的优先级，就是即将插入的数据会和队列中其他数据的优先级进行比较，比较完成后，才可以得出这个元素在队列中的正确位置，除此之外其他处理方式和普通队列的处理方式一样，那么我们该如何实现，其实要实现优先级队列主要就是需要修改 enqueue 方法就可以实现
let PriorityQueue = (function() {
// 基于数组
let items = [];
// 内部类,用于创建元素节点
let _createQueuElement = class {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
};
return class {
// 向队列尾部添加一项
// 存
enqueue(element, priority) {
// 创建
let queuelement = new _createQueuElement(element, priority);
// 如果为空
if (items.length === 0) {
// 直接添加
items.push(queuelement);
return;
} else {
// 如果插入元素，
if (queuelement.priority <= items[0].priority) {
items.unshift(queuelement);
return;
} else if (
queuelement.priority > items[items.length - 1].priority
) {
items.push(queuelement);
return;
}
// 预先定义 index 值
let index;
items.forEach((v, i) => {
if (
queuelement.priority > items[i].priority &&
queuelement.priority <= items[i + 1].priority
) {
index = i + 1;
}
});
items.splice(index, 0, queuelement);
return index;
}
}
// 移除队列的第一项，并返回被移除项
// 取
dequeue() {
return items.shift();
}
// 返回队列中的第一个元素
// 查看
front() {
return items[0];
}
// 查看队列是否为空
isEmpty() {
return items.length === 0;
}
// 查看大小
size() {
return items.length;
}
// 将队列中的内容转换为字符串，并返回
toString() {
let resultString = "";
for (let i in items) {
resultString += JSON.stringify(items[i]);
}
return resultString;
}
};
})();
let pq = new PriorityQueue();
pq.enqueue("哥哥", 30);
pq.enqueue("小红", 10);
pq.enqueue("小吕", 20);
pq.enqueue("银时", 40);
pq.enqueue("神乐", 50);
pq.enqueue("神乐2号", 15);
pq.enqueue("神乐3号", 15);
pq.enqueue("神乐2号", 16);
pq.enqueue("神乐2号", 17);
console.log(pq.toString());
