JavaScript实现队列结构(Queue)
发布网友
发布时间：2024-09-04 22:37
共1个回答
热心网友
时间：2024-12-12 21:45
队列是是一种受限的线性表，特点为先进先出（FIFO：firstinfirstout）。
受限之处在于它只允许在表的前端（front）进行删除操作；
在表的后端（rear）进行插入操作；
相当于排队买票，先来的先买票，后来的后买票。
队列的应用：
打印队列：计算机打印多个文件的时候，需要排队打印；
线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待CPU处理；
队列类的实现：
队列的实现和栈一样，有两种方案：
基于数组实现；
基于链表实现；
队列的常见操作：
enqueue（element）：向队列尾部添加一个（或多个）新的项；
dequeue（）：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素；
front（）：返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与Stack类的peek方法非常类似）；
isEmpty（）：如果队列中不包含任何元素，返回true，否则返回false；
size（）：返回队列包含的元素个数，与数组的length属性类似；
toString（）：将队列中的内容，转成字符串形式；
二、封装队列类2.1.代码实现//?基于数组封装队列类function?Queue()?{??//?属性??this.items?=?[];}//?方法//?1.enqueue():将元素加入到队列中Queue.prototype.enqueue?=?function?(element)?{??this.items.push(element);};//?2.dequeue():从队列中删除前端元素,并返回被移除的元素Queue.prototype.dequeue?=?function?()?{??return?this.items.shift();};//?3.front():查看前端的元素Queue.prototype.front?=?function?()?{??return?this.items[0];};//?4.isEmpty:查看队列是否为空Queue.prototype.isEmpty?=?function?()?{??return?this.items.length?==?0;};//?5.size():查看队列中元素的个数Queue.prototype.size?=?function?()?{??return?this.items.length;};//?6.toString():将队列中元素以字符串形式输出Queue.prototype.toString?=?function?()?{??let?resultString?=?"";??for?(let?i?of?this.items)?{????resultString?+=?i;??}??return?resultString;};测试代码：
//?创建队列let?queue?=?new?Queue();//?将元素加入到队列中queue.enqueue("a");queue.enqueue("b");queue.enqueue("c");queue.enqueue("d");console.log(queue);//?从队列中删除元素queue.dequeue();console.log(queue);queue.dequeue();console.log(queue);//frontconsole.log(queue.front());//?验证其他方法console.log(queue.isEmpty());console.log(queue.size());console.log(queue.toString());测试结果：
2.2.队列的应用-击鼓传花使用队列实现小游戏：击鼓传花，传入一组数据和设定的数字num，循环遍历数组内元素，遍历到的元素为指定数字num时将该元素删除，直至数组剩下一个元素。
代码实现：
//?队列应用：面试题：击鼓传花,利用了上面封装好的队列结构let?passGame?=?(nameList,?num)?=>?{??//1.创建队列结构??let?queue?=?new?Queue();??//2.将所有人依次加入队列??for?(let?i?of?nameList)?{????queue.enqueue(i);??}??//?3.开始数数，队列中只剩1个人就停止数数??while?(queue.size()?>?1)?{????//?3.1.num数字之前的人重新放入队列的末尾(把队列前面删除的加到队列最后)????for?(let?i?=?0;?i?<?num?-?1;?i++)?{??????queue.enqueue(queue.dequeue());????}????//?3.2.num对应这个人，直接从队列中删除????queue.dequeue();??}??//4.获取剩下的那个人??let?endName?=?queue.front();??return?endName;};//5.测试击鼓传花let?names?=?["lily",?"lucy",?"Tom",?"Lilei",?"Tony"];console.log(passGame(names,?3));测试结果：Lilei
三、优先队列优先级队列主要考虑的问题为：
每个元素不再只是一个数据，还包含数据的优先级；
在添加数据过程中，根据优先级放入到正确位置；
3.1.优先级队列的实现代码实现：
//?封装优先级队列function?PriorityQueue()?{??//内部类：在类里面再封装一个类;表示带优先级的数据??function?QueueElement(element,?priority)?{????this.element?=?element;????this.priority?=?priority;??}??//?封装属性??this.items?=?[];??//?1.实现按照优先级插入方法（箭头函数内的this指向PriorityQueue函数的作用域，这里使用箭头函数和普通函数都可）??PriorityQueue.prototype.enqueue?=?(element,?priority)?=>?{????//?1.1.创建QueueElement对象（会顺着作用域链找到QueueElement构造函数）????let?queueElement?=?new?QueueElement(element,?priority);????//?1.2.判断队列是否为空????if?(this.items.length?==?0)?{??????this.items.push(queueElement);????}?else?{??????//?定义一个变量记录是否成功插入了新元素??????let?added?=?false;??????for?(let?i?in?this.items)?{????????//?让新插入的元素与原有元素进行优先级比较(priority越小，优先级越大)????????if?(queueElement.priority?<?this.items[i].priority)?{??????????//?从第i个元素开始，删除0个，并在第i个元素的前面插入queueElement??????????this.items.splice(i,?0,?queueElement);??????????added?=?true;??????????//?新元素已经找到插入位置了可以使用break停止循环??????????break;????????}??????}??????//?新元素没有成功插入，就把它放在队列的最后面??????if?(!added)?{????????this.items.push(queueElement);??????}????}??};??????//?2.dequeue()从队列中删除前端元素,并返回被移除的元素??//?3.front():查看前端的元素??//?...}测试代码：
//?测试代码let?pq?=?new?PriorityQueue();pq.enqueue("Tom",?111);pq.enqueue("Hellen",?200);pq.enqueue("Mary",?30);pq.enqueue("Gogo",?27);pq.enqueue("Lala",?28);//?打印修改过后的优先队列对象console.log(pq);测试结果：
3.2.注意点关于数组方法splice用法：
splice（1，0，'Tom'）：表示在索引为1的元素前面插入元素’Tom‘（也可以理解为从索引为1的元素开始删除，删除0个元素，再在索引为1的元素前面添加元素'Tom'）；
splice（1，1，'Tom'）：表示从索引为1的元素开始删除（包括索引为1的元素），共删除1个元素，并添加元素'Tom'。即把索引为1的元素替换为元素'Tom'。
数组的push方法在数组、栈和队列中的形式：
数组：在数组[0,1,2]中，push(3)，结果为[0，1，2，3]；
栈：执行push(0)，push1)，push(2)，push(3)，从栈底到栈顶的元素分别为：0，1，2，3；如果看成数组，可写为[0，1，2，3]，但是索引为3的元素3其实是栈顶元素；所以说栈的push方法是向栈顶添加元素（但在数组的视角下为向数组尾部添加元素）；
队列：enqueue方法可以由数组的push方法实现，与数组相同，相当于在数组尾部添加元素。
可以这样想：栈结构是头朝下（索引值由下往上增大）的数组结构。
原文：https://juejin.cn/post/7095608521110061064
