JavaScript数据结构03 - 队列
栏目: JavaScript · 发布时间: 6年前
内容简介:前面我们学习了队列是遵循FIFO(First In First Out,先进先出)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。
前面我们学习了 栈的实现 ,队列和栈非常类似,但是使用了不同的原则,而非后进先出。
队列是遵循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 。
实现最小优先队列:
// 定义最小优先队列 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
三、结束
本文会同步到我的个人博客,完整代码可以到我的 github仓库查看 ,如果对你有帮助的话欢迎点一个Star~~
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。