用js来实现那些数据结构06（队列）
其实队列跟栈有很多相似的地方，包括其中的一些方法和使用方式，只是队列使用了与栈完全不同的原则，栈是后进先出原则，而队列是先进先出（First In First Out）。
一、队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
我们对队列有了基本的了解，那么我们来看看如何实现队列。其实跟栈的实现极为类似，只是入队和出队的方法稍有不同，那么我们来看看一个完整的队列需要哪些方法：
1、enqueue(element(s))，入队，向队列尾部添加一个或者多个元素。
2、dequeue()，出队，移除队列中的第一个元素，也就是队列最前面的元素，并返回该元素。
3、front()，获取队列最前面的元素，返回队列中第一个元素（最先被添加，也是最先被移除的元素）。队列并不移除该元素。
4、isEmpty()，判断队列是否不包含任何元素。
5、size()，返回队列的元素总数。
//声明Queue类
function Queue() {
//声明并初始化一个用来存放队列元素的数组。
let items = [];
//添加队列元素
this.enqueue = function (element) {
items.push(element)
};
//移除并返回该队列元素
this.dequeue = function () {
return items.shift();
};
//获取队列头部元素
this.front = function () {
return items[0];
};
//判断队列元素是否为空
this.isEmpty = function () {
return items.length == 0;
};
//获取队列元素个数
this.size = function () {
return items.length;
};
//打印该队列
this.print = function () {
console.log(items.toString())
};
}
const queue = new Queue();
console.log(queue.isEmpty()); // outputs true
queue.enqueue('John');
queue.enqueue('Jack');
queue.print(); // John,Jack
queue.enqueue('Camila');
queue.print(); // John,Jack,Camila
console.log(queue.size()); // outputs 3
console.log(queue.isEmpty()); // outputs false
queue.dequeue(); // remove John
queue.dequeue(); // remove Jack
queue.print(); // Camila
上面我们就已经实现了队列这种数据结构，同样的，我们是否可以稍微改造一下，让队列的实现看起来更加优美一点。
let Queue = (function () {
const items = new WeakMap();
class Queue {
constructor () {
//强调一下，这里items是WeakMap类型的数据，而WeakMap是键值对，有专属的set和get方法来获取和设置值，
//所以这里给this设置了[]，即以this为键名，[]为值，所以该方法形成的队列仍旧是对数组的操作
items.set(this,[]);
}
enqueue(element) {
let q = items.get(this);//这里的q就相当于是[]
q.push(element);
}
dequeue() {
let q = items.get(this);
let r = q.shift();
return r;
}
front() {
return items.get(this)[0];
}
isEmpty() {
return items.get(this).length == 0;
}
size() {
return items.get(this).length;
}
print() {
console.log(items.get(this));
}
}
return Queue;
})()
其实到这里队列就基本介绍完了，但是感觉实在有点糊弄人啊。所以就把剩下的内容都在这一篇文章写完吧。
二、优先队列
我们说完了队列，那么我们看看什么是优先队列。普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。就像是我们在窗口买票，机场排队，正常来说我们都是依照排队的顺序从队列的最前面开始依次进入，但是有规定老人孩子军人等优先，那么就赋予了该老人（孩子军人）插队的权利。而优先队列，同样就是给特定元素赋予插队（优先级）的权利。我想要入队，并不一定是直接到尾部。而是根据我设定的优先级来插入队列。
其实优先队列在实现上不同的地方是队列元素的设定和入队方法的不同（这里其实有两种实现方式，一个是按照优先级入列，一个是按照优先级出列，这里我们只用第一种方式实现）。下面我们就看看如何实现优先队列吧。
//声明Queue类
function PriorityQueue() {
//声明并初始化一个用来存放队列元素的数组。
let items = [];
//创建一个拥有优先级的元素类
function QueueElement(element,priority) {
this.element = element;
this.priority = priority;
}
//添加队列元素
this.enqueue = function (element,priority) {
let queueElement = new QueueElement(element,priority);
let added = false;
//遍历队列元素，1的优先级最高，一次类推，如果当前元素优先级大于items[i]，那么就把该元素放在items[i]前面。
//splice方法的第二的参数如果为0，那么则把第三个参数添加到i前面。
for(let i = 0; i < items.length; i++) {
if(queueElement.priority < items[i].priority) {
items.splice(i,0,queueElement);
added = true;break;
}
}
// 通过added判断是否可以直接把元素入列。
if(!added) {
items.push(queueElement);
}
};
//移除并返回该队列元素
this.dequeue = function () {
return items.shift();
};
//获取队列头部元素
this.front = function () {
return items[0];
};
//判断队列元素是否为空
this.isEmpty = function () {
return items.length == 0;
};
//获取队列元素个数
this.size = function () {
return items.length;
};
//循环打印元素及其优先级“``”是ES6的模板字符串
this.print = function () {
for(let i = 0; i < items.length; i++) {
console.log(`${items[i].element} - ${items[i].priority}`);
}
};
}
const queue = new PriorityQueue();
console.log(queue.isEmpty()); // outputs true
queue.enqueue('zaking',2);
queue.enqueue('linbo',6);
queue.enqueue('queue',5);
queue.enqueue('ada',3);
queue.enqueue('John',1);
queue.enqueue('Jack',2);
queue.enqueue('Camila',3);
queue.enqueue('zak',3);
queue.print();
主要的更改在于队列元素的设置和enqueue方法，由于需要为每一个循环队列的元素设置优先级，所以这里稍微更改了一下队列的元素，使其带有两个参数（元素自身和优先级），那么既然要根据不同的优先级来插入队列，所以循环队列的enqueue方法也就需要循环整个队列去判断要插入到哪里。
其实这个优先队列的实现并不是很好，比如我不传第二优先级参数，那么队列打印的时候该参数就是undefined，而且在不传参数的时候应该默认为最末优先级。大家可以试着去修改一下代码，使其看起来更符合实际。
三、循环队列
除了优先队列以外还有循环队列，循环队列的一个比较容易想象的例子就是击鼓传花游戏，游戏规则就不说了大家小时候都玩过，我们看看如何实现击鼓传花游戏。
function hotPotato(nameList, num) {
const queue = new Queue();
//把所有的名单（nameList）依次入列
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i]);
}
//声明当前被淘汰的人员名称
let eliminated = '';
//如果队列中的元素大于一个，说明还没有最后的赢家，如果只剩下一个，就出列该最后赢家
while (queue.size() > 1) {
//循环当前队列num次，把队列头部的“出列元素”再入列。
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
//循环结束后，出列当前队列的元素，也就是淘汰者。
eliminated = queue.dequeue();
queue.print();
console.log(eliminated + "被淘汰");
}
return queue.dequeue();
}
let names = ["zak","zaking","james","lili","bole","londo","fali"]
console.log(hotPotato(names,7))
上面的方法，每次循环都会依次把头部元素放入到尾部，就实现了一个圈，然后我们以循环结束后，队列最前端的元素视为淘汰，直到最后只剩下一个元素，也就真实的模拟了击鼓传花游戏。
最后，由于本人水平有限，能力与大神仍相差甚远，若有错误或不明之处，还望大家不吝赐教指正。非常感谢！
版权声明：本文为zaking原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。