1.概念
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
生活中基于队列的现象有：排队买东西，打印机工作。图解如下所示。
2.自定义队列的完整操作
function Queue() { var items = [] // 队列操作的方法 // enter queue方法 this.enqueue = function (element) { items.push(element) } // delete queue方法 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 } }
3.优先级队列
对于普通的队列，队列中元素的处理顺序和插入的顺序是密切相关的。而优先级队列则与插入顺序无关。优先级队列, 在插入一个元素的时候会考虑该数据的优先级，与其他元素比较后插入到正确的队列。要实现优先级队列, 最主要是要修改添加方法。
生活中常见的优先级队列的现象有：VIP客户和普通客户，医院里病情较重的人优先治疗等。
封装优先级队列
function PriorityQueue() { var items = [] // 封装一个新的构造函数, 用于保存元素和元素的优先级 function QueueElement(element, priority) { this.element = element this.priority = priority } // 添加元素的方法 this.enqueue = function (element, priority) { // 1.根据传入的元素, 创建新的QueueElement var queueElement = new QueueElement(element, priority) // 2.获取传入元素应该在正确的位置 if (this.isEmpty()) { items.push(queueElement) } else { var added = false for (var i = 0; i < items.length; i++) { // 这里是数字越小, 优先级越高 if (queueElement.priority < items[i].priority) { items.splice(i, 0, queueElement) added = true break } } // 遍历完所有的元素, 优先级都大于新插入的元素时, 就插入到最后 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 } } // test // 创建优先级队列对象 var pQueue = new PriorityQueue(); // 添加元素 pQueue.enqueue("abc", 10); pQueue.enqueue("cba", 5); pQueue.enqueue("nba", 12); pQueue.enqueue("mba", 3); // 遍历所有的元素 var size = pQueue.size(); for (var i = 0; i < size; i++) { var item = pQueue.dequeue(); console.log(item.element + "----" + item.priority); } //结果： //mba----3 //cba----5 //abc----10 //nba----12
4.使用队列来实现击鼓传花案例
几个朋友一起玩一个游戏, 围成一圈, 开始数数, 数到某个数字的人自动淘汰。最后剩下的这个人会获得胜利, 请问最后剩下的是原来在哪一个位置上的人?
function passGame(nameList, num) { // 1.创建一个队列, 并且将所有的人放在队列中 // 1.1.创建队列 var queue = new Queue(); // 1.2.通过for循环, 将nameList中的人放在队列中 for (var i = 0; i < nameList.length; i++) { queue.enqueue(nameList[i]); } // 2.寻找最后剩下的人 while (queue.size() > 1) { // 将前num-1中的人, 都从队列的前端取出放在队列的后端 for (var i = 0; i < num; i++) { queue.enqueue(queue.dequeue()); } // 将第num个人, 从队列中移除 queue.dequeue(); } // 3.获取剩下的一个人 var endName = queue.dequeue(); // 4.获取该人在队列中的位置 return endName; } // test var names = ["John", "Jack", "Camila", "Ingrid", "Carl"]; var endName = passGame(names, 7); // 数到8的人淘汰 console.log("最终留下:" + endName); // ‘john‘
原文：https://www.cnblogs.com/zjqzilq/p/14529689.html