建设网站建设哪家快,龙岩建设局网站罗小波,北海做网站哪家好,网站怎样做全国地区推广其实队列跟栈有很多相似的地方#xff0c;包括其中的一些方法和使用方式#xff0c;只是队列使用了与栈完全不同的原则#xff0c;栈是后进先出原则#xff0c;而队列是先进先出#xff08;First In First Out#xff09;。
一、队列 队列是一种特殊的线性表#xff0c… 其实队列跟栈有很多相似的地方包括其中的一些方法和使用方式只是队列使用了与栈完全不同的原则栈是后进先出原则而队列是先进先出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)) 上面的方法每次循环都会依次把头部元素放入到尾部就实现了一个圈然后我们以循环结束后队列最前端的元素视为淘汰直到最后只剩下一个元素也就真实的模拟了击鼓传花游戏。 最后由于本人水平有限能力与大神仍相差甚远若有错误或不明之处还望大家不吝赐教指正。非常感谢 更多专业前端知识请上
【猿2048】www.mk2048.com
