一, 定义
前面我们学习了栈的实现, 队列和栈非常类似, 但是使用了不同的原则, 而非后进先出.
队列是遵循 FIFO(First In First Out, 先进先出) 原则的一组有序的项. 队列在尾部添加新元素, 并从顶部移除元素. 最新添加的元素必须排在队列的末尾.
在计算机科学中, 一个最常见的例子就是打印队列. 比如说我们要打印五份文档. 我们会打开每个文档, 然后点击打印按钮. 每个文档都会被发送至打印队列. 第一个发送到打印队列的文档会首先被打印, 以此类推, 直到打印完所有文档.
二, 队列的实现
2.1 普通队列
创建普通队列类:
- // Queue 类
- function Queue () {
- this.items = [];
- this.enqueue = enqueue;
- this.dequeue = dequeue;
- this.front = front;
- this.isEmpty = isEmpty;
- this.size = size;
- this.clear = clear;
- this.print = print;
- }
复制代码
队列里面有一些声明的辅助方法:
enqueue(element): 向队列尾部添加新项
dequeue(): 移除队列的第一项 (即排在队列最前面的项), 并返回被移除的元素
front(): 返回队列中第一个元素, 队列不做任何变动, 和 Stack 的 peek() 方法类似
isEmpty(): 如果队列中不包含任何元素, 返回 true, 否则返回 false
size(): 返回队列包含的元素个数, 与数组的 length 属性类似
print(): 打印队列中的元素
clear(): 清空整个队列
下面我们来一一实现这些辅助方法:
- // 向队列尾部添加元素
- function enqueue (element) {
- this.items.push(element);
- }
- // 移除队列的第一个元素, 并返回被移除的元素
- function dequeue () {
- return this.items.shift();
- }
- // 返回队列的第一个元素
- function front () {
- return this.items[0];
- }
- // 判断是否为空队列
- function isEmpty () {
- return this.items.length === 0;
- }
- // 获取队列的长度
- function size () {
- return this.items.length;
- }
- // 清空队列
- function clear () {
- this.items = [];
- }
- // 打印队列里的元素
- function print () {
- console.log(this.items.toString());
- }
复制代码
创建普通队列实例进行测试:
- // 创建 Queue 实例
- var queue = new Queue();
- console.log(queue.isEmpty()); // true
- queue.enqueue("John"); // undefined
- queue.enqueue("Jack"); // undefined
- queue.enqueue("Camila"); // undefined
- queue.print(); // "John,Jack,Camila"
- console.log(queue.size()); // 3
- console.log(queue.isEmpty()); // false
- queue.dequeue(); // "John"
- queue.dequeue(); // "Jack"
- queue.print(); // "Camila"
- queue.clear(); // undefined
- console.log(queue.size()); // 0
复制代码
2.2 优先队列
2.2.1 定义
普通队列的添加和移除只依赖于先后顺序, 先来的先添加, 后来的后添加, 然后按照先后顺序依次从队列移除.
但是, 还有一种队列叫优先队列, 元素的添加和移除是依赖优先级的.
一个现实的例子就是机场登机的顺序. 头等舱和商务舱乘客的优先级要高于经济舱乘客. 再比如火车, 老年人, 孕妇和带小孩的乘客是享有优先检票权的.
2.2.2 分类
优先队列分为两类:
最小优先队列
最大优先队列
最小优先队列是把优先级的值最小的元素被放置到队列的最前面 (代表最高的优先级). 比如有四个元素:"John", "Jack", "Camila", "Tom", 他们的优先级值分别为 4,3,2,1.
那么最小优先队列排序应该为:"Tom","Camila","Jack","John".
最大优先队列正好相反, 把优先级值最大的元素放置在队列的最前面, 以上面的为例, 最大优先队列排序应该为:"John", "Jack", "Camila", "Tom".
2.2.2 实现
实现一个优先队列, 有两种选项:
设置优先级, 根据优先级正确添加元素, 然后和普通队列一样正常移除
设置优先级, 和普通队列一样正常按顺序添加, 然后根据优先级移除
这里最小优先队列和最大优先队列我都采用第一种方式实现, 大家可以尝试一下第二种.
所以我只重写 enqueue() 方法和 print() 方法, 其他方法和上面的普通队列完全相同. 完整代码见我的 github https://github.com/leocoder351/data-structure .
实现最小优先队列:
- // 定义最小优先队列
- function MinPriorityQueue () {
- this.items = [];
- this.enqueue = enqueue;
- this.dequeue = dequeue;
- this.front = front;
- this.isEmpty = isEmpty;
- this.size = size;
- this.clear = clear;
- this.print = print;
- }
复制代码
实现最小优先队列 enqueue() 方法和 print() 方法:
- // 优先队列添加元素, 要根据优先级判断在队列中的插入顺序
- function enqueue (element, priority) {
- var queueElement = {
- element: element,
- priority: priority
- };
- if (this.isEmpty()) {
- this.items.push(queueElement);
- } else {
- var added = false;
- for (var i = 0; i <this.size(); i++) {
- if (queueElement.priority < this.items[i].priority) {
- this.items.splice(i, 0, queueElement);
- added = true;
- break ;
- }
- }
- if (!added) {
- this.items.push(queueElement);
- }
- }
- }
- // 打印队列里的元素
- function print () {
- var strArr = [];
- strArr = this.items.map(function (item) {
- return `${item.element}->${item.priority}`;
- });
- console.log(strArr.toString());
- }
复制代码
最小优先队列测试:
- // 创建最小优先队列 minPriorityQueue 实例
- var minPriorityQueue = new MinPriorityQueue();
- console.log(minPriorityQueue.isEmpty()); // true
- minPriorityQueue.enqueue("John", 1); // undefined
- minPriorityQueue.enqueue("Jack", 3); // undefined
- minPriorityQueue.enqueue("Camila", 2); // undefined
- minPriorityQueue.enqueue("Tom", 3); // undefined
- minPriorityQueue.print(); // "John->1,Camila->2,Jack->3,Tom->3"
- console.log(minPriorityQueue.size()); // 4
- console.log(minPriorityQueue.isEmpty()); // false
- minPriorityQueue.dequeue(); // {element: "John", priority: 1}
- minPriorityQueue.dequeue(); // {element: "Camila", priority: 2}
- minPriorityQueue.print(); // "Jack->3,Tom->3"
- minPriorityQueue.clear(); // undefined
- console.log(minPriorityQueue.size()); // 0
复制代码
实现最大优先队列
最大优先队列只要将优先级的判断改为大于号 ">" 就可以了:
- // 最大优先队列 MaxPriorityQueue 类
- function MaxPriorityQueue () {
- this.items = [];
- this.enqueue = enqueue;
- this.dequeue = dequeue;
- this.front = front;
- this.isEmpty = isEmpty;
- this.size = size;
- this.clear = clear;
- this.print = print;
- }
- // 优先队列添加元素, 要根据优先级判断在队列中的插入顺序
- function enqueue (element, priority) {
- var queueElement = {
- element: element,
- priority: priority
- };
- if (this.isEmpty()) {
- this.items.push(queueElement);
- } else {
- var added = false;
- for (var i = 0; i <this.items.length; i++) {
- // 注意, 只需要将这里改为大于号就可以了
- if (queueElement.priority> this.items[i].priority) {
- this.items.splice(i, 0, queueElement);
- added = true;
- break ;
- }
- }
- if (!added) {
- this.items.push(queueElement);
- }
- }
- }
复制代码
最大优先队列测试:
- // 创建最大优先队列 maxPriorityQueue 实例
- var maxPriorityQueue = new MaxPriorityQueue();
- console.log(maxPriorityQueue.isEmpty()); // true
- maxPriorityQueue.enqueue("John", 1); // undefined
- maxPriorityQueue.enqueue("Jack", 3); // undefined
- maxPriorityQueue.enqueue("Camila", 2); // undefined
- maxPriorityQueue.enqueue("Tom", 3); // undefined
- maxPriorityQueue.print(); // "Jack->3,Tom->3,Camila->2,John->1"
- console.log(maxPriorityQueue.size()); // 4
- console.log(maxPriorityQueue.isEmpty()); // false
- maxPriorityQueue.dequeue(); // {element: "Jack", priority: 3}
- maxPriorityQueue.dequeue(); // {element: "Tom", priority: 3}
- maxPriorityQueue.print(); // "Camila->2,John->1"
- maxPriorityQueue.clear(); // undefined
- console.log(maxPriorityQueue.size()); // 0
复制代码
2.3 循环队列
还有一种队列实现叫做循环队列.
循环队列的一个例子就是击鼓传花游戏 (Hot Potato). 在这个游戏中, 孩子们围城一个圆圈, 击鼓的时候把花尽快的传递给旁边的人. 某一时刻击鼓停止, 这时花在谁的手里, 谁就退出圆圈直到游戏结束. 重复这个过程, 直到只剩一个孩子 (胜者).
下面我们在普通队列的基础上, 实现一个模拟的击鼓传花游戏:
- // 实现击鼓传花
- function hotPotato (nameList, num) {
- var queue = new Queue();
- for (var i = 0; i <nameList.length; i++) {
- queue.enqueue(nameList[i]);
- }
- var eliminated = '';
- while (queue.size()> 1) {
- // 循环 num 次, 队首出来去到队尾
- for (var i = 0; i < num; i++) {
- queue.enqueue(queue.dequeue());
- }
- // 循环 num 次过后, 移除当前队首的元素
- eliminated = queue.dequeue();
- console.log(`${eliminated} 在击鼓传花中被淘汰!`);
- }
- // 最后只剩一个元素
- return queue.dequeue();
- }
- // 测试
- var nameList = ["John", "Jack", "Camila", "Ingrid", "Carl"];
- var winner = hotPotato(nameList, 10);
- console.log(` 最后的胜利者是:${winner}`);
复制代码
执行结果为:
- // John 在击鼓传花中被淘汰!
- // Ingrid 在击鼓传花中被淘汰!
- // Jack 在击鼓传花中被淘汰!
- // Camila 在击鼓传花中被淘汰!
- // 最后的胜利者是: Carl
来源: https://juejin.im/post/5b597dc56fb9a04fdf39e85d