本文共 6518 字，大约阅读时间需要 21 分钟。
有两种结构类似于数组，但在添加和删除元素时更加可控，它们就是栈和队列。
第四章 队列
队列数据结构
队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。
现实中，很常见的例子就是排队。在计算机科学里面是打印队列。
创建队列
我们需要创建自己的类来表示一个队列，先从最基本的声明开始：
function Queue(){ // 这里是属性和方法} 首先需要一个用于存储队列中元素的数据结构。我们可以使用数组，就像上一章 Stack 类中那样使用（你会发现其实两者很相似，只是添加和移除元素不一样而已。）
let items = []
接下来需要声明一些队列可用的方法。
- enqueue（element（s））:向队列尾部添加一个（或多个）新的项。
- dequeue（）：移除队列中的第一个（排列在队伍最前面的）项，并返回被移除的元素
- front（）：返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与 Stack 类的 peek 方法非常相似）
- isEmpty（）：如果队列中不包含任何元素，返回 ture，否则返回 false
- size（）:返回队列包含的元素个数，与数组的 length 属性类似。
向队列添加元素
首先要实现的是 enqueue 方法。这个方法负责向队列中添加新元素，还有一个非常重要的细节，新的项目只能添加到队列末尾：
this.enqueue = function(element){ return items.push(element);}; 从队列中移除元素
接下来就是 dequeue 方法，这个方法负责从队列中移除项。由于队列遵循先进先出原则，最先添加的项也是要最先被移除的。数组中的 shift 方法会从数组中移除存储在索引0（第一个位置）的元素。
this.dequeue = function(element){ return items.shift();} 只有 enqueue 方法和 dequeue 方法可以添加和移除元素，这样就确保了 Queue 类遵循先进先出的原则。
查看队列头元素
为我们类实现一些额外的辅助方法。我们想知道队列最前面是什么，可以使用 front 方法查看
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());} 实例
function Queue(){ let items = []; this.enqueue = function(element){ return 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.clear = function(){ items = []; } this.print = function(){ console.log(items.toString()); } } let queue = new Queue(); // 新建 类 Queue 的实例 queue console.log(queue.isEmpty()); // 队列没有元素，返回 true queue.enqueue(5); // 先队列中加 5 queue.enqueue(8); // 先队列中加 8 queue.dequeue(); // 减去队列的开头 console.log(queue.front()); // 8 queue.enqueue(11); // 先队列中加 11 console.log(queue.size()); // 队列的长度 2 console.log(queue.isEmpty()); // 队列有元素，返回 false queue.enqueue(15); // 先队列中加 15 queue.print(); // 输出队列中的元素 8,11,15 使用ES6 语法实现的 Queue 类
我们使用一个 WeakMap 来保存私有属性items，并用外层函数（闭包）来封装 Queue 类。
let Queue = (function(){const items = new WeakMap(); // 声明了一个 WeakMap 类型的变量 itemsclass Queue{ constructor(){ items.set(this, []) // 在 constructor 中，以this（Stack类自己引用）为键，把代表栈的数组存入 items } enqueue(element){ let q = items.get(this); q.push(element); } dequeue (){ let q = items.get(this); let r = q.shift(); return r; } front (){ let q = items.get(this); return q[0]; } isEmpty (){ let q = items.get(this); return q.length == 0; } size (){ let q = items.get(this); let r = q.length return r; } clear (){ items.set(this, []) } print (){ let q = items.get(this); console.log(q.toString()); }}return Queue;})(); 优先队列
队列大量应用在计算机科学以及我们的生活中，其中一个就是优先队列。元素的添加和移除是基于优先级的。现实中的例子就是登机的顺序。头等舱和商务舱的乘客优先级要优于经济舱乘客。
另外一个现实的例子就是医院的候诊室。医生会优先处理病情比较严重的患者。
实现一个队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级操作它们。在这个实例中，我们会在正确的位置添加元素，因此可以对它们使用默认的出列操作。
function ProrityQueue(){ 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; // 如果队列为空可以直接将元素插入，否则就要比较元素与该元素的优先级。 // 当找到一个比要添加元素的 priority 值更高（优先级更低）的项时， // 我们就把元素插入它之前，但是如果优先级相同的话就遵循先进先出的原则 for(let i = 0; i < items.length; i++){ if(queueElement.priority < items[i].priority ){ items.splice(i,0,queueElement); added = true; break; } } if(!added){ // 如果添加元素的 priority 值大于任何已有的元素，把它添加到队列的末尾就行了 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; } this.clear = function(){ items = []; } this.print = function(){ for(let i = 0; i < items.length; i++){ console.log(`${items[i].element} - ${items[i].priority}`); } }}let prorityQueue = new ProrityQueue();prorityQueue.enqueue('John',2);prorityQueue.enqueue('Mike',1);prorityQueue.enqueue('Jenny',1);prorityQueue.print(); /* Mike - 1 Jenny - 1 John - 2*/ 循环队列——击鼓传花
还有另一个修改版的队列实现，就是循环队列。循环队列的一个例子就是击鼓传花游戏（Hot Potato）。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人，某一时刻传花停止，这个时候，花就在谁的手里，谁就退出圆圈结束游戏。重复这个过程，直到最后一个孩子，就是胜者。
在这个例子中，我们要实现一个模拟的击鼓传花游戏。
function Queue(){ let items = []; this.enqueue = function(element){ return 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.clear = function(){ items = []; } this.print = function(){ console.log(items.toString()); }} function hotPotata(nameList, num){ let queue = new Queue(); // 将姓名名单 nameList 逐个加入到队列中 for(let i = 0; i < nameList.length; i++){ queue.enqueue(nameList[i]); } // 给定一个数字，然后迭代队伍，从队列中开头移除一项 // 然后将其添加到队伍的末尾，模拟击鼓传花 // 一旦传递次数达到给定的数字，拿着花的那个人就被淘汰 let eliminated = ''; while(queue.size() > 1){ for(let i = 0; i < num; i++){ queue.enqueue(queue.dequeue()); } eliminated = queue.dequeue(); console.log(eliminated+'在击鼓传花游戏中被淘汰'); } return queue.dequeue();}let names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];let winner = hotPotata(names, 7);console.log('获胜者是'+ winner);// Camila在击鼓传花游戏中被淘汰// John在击鼓传花游戏中被淘汰// Carl在击鼓传花游戏中被淘汰// Jack在击鼓传花游戏中被淘汰// 获胜者是Ingrid 下图模拟了这个输出过程：
可以改变传入 hotPotata 函数的数字，模拟不同的场景。
JavaScript 任务队列
当我们在浏览器中打开新标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，它被称为 事件循环。浏览器要负责多个任务，如渲染 HTML ，执行 JavaScript 代码，处理用户交互（用户输入，鼠标点击等），执行和处理异步请求。
小结
这一章学习了队列这种数据结构。实现了自己的队列算法，学习了如何通过 enqueue 方法和 dequeue 方法添加和移除元素。还学习了两种非常著名的特殊队列的实现，优先队列和循环队列（使用击鼓传花的实现）
下一章，将学习链表，一种比数组更加复杂的数据结构。
书籍链接：
转载地址：http://bcnba.baihongyu.com/