JavaScript队列结构Queue实现过程解析
一、队列简介
队列是是一种受限的线性表，特点为先进先出（FIFO：firstinfirstout）。
受限之处在于它只允许在表的前端（front）进行删除操作；在表的后端（rear）进行插入操作；
打印队列：计算机打印多个文件的时候，需要排队打印；线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待CPU处理；
队列类的实现：
队列的实现和栈一样，有两种方案：
基于数组实现；基于链表实现；
队列的常见操作：
- enqueue（element）：向队列尾部添加一个（或多个）新的项；
- dequeue（）：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素；
- front（）：返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与Stack类的peek方法非常类似）；
- isEmpty（）：如果队列中不包含任何元素，返回true，否则返回false；
- size（）：返回队列包含的元素个数，与数组的length属性类似；
- toString（）：将队列中的内容，转成字符串形式；
二、封装队列类
2.1.代码实现
//基于数组封装队列类
functionQueue(){
//属性
this.items=[]
//方法
//1.enqueue():将元素加入到队列中
Queue.prototype.enqueue=element=>{
this.items.push(element)
}
//2.dequeue():从队列中删除前端元素
Queue.prototype.dequeue=()=>{
returnthis.items.shift()
}
//3.front():查看前端的元素
Queue.prototype.front=()=>{
returnthis.items[0]
}
//4.isEmpty:查看队列是否为空
Queue.prototype.isEmpty=()=>{
returnthis.items.length==0;
}
//5.size():查看队列中元素的个数
Queue.prototype.size=()=>{
returnthis.items.length
}
//6.toString():将队列中元素以字符串形式输出
Queue.prototype.toString=()=>{
letresultString=''
for(letiofthis.items){
resultString+=i+''
}
returnresultString
}
}
测试代码：
//创建队列
letqueue=newQueue()
//将元素加入到队列中
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
console.log(queue);//58
//从队列中删除元素
queue.dequeue()
console.log(queue);//62
queue.dequeue()
console.log(queue);//64
//front
console.log(queue.front());//67
//验证其他方法
console.log(queue.isEmpty());//70
console.log(queue.size());//71
console.log(queue.toString());//72
测试结果：
使用队列实现小游戏：击鼓传花，传入一组数据和设定的数字num，循环遍历数组内元素，遍历到的元素为指定数字num时将该元素删除，直至数组剩下一个元素。
代码实现：
//队列应用：面试题：击鼓传花
letpassGame=(nameList,num)=>{
//1.创建队列结构
letqueue=newQueue()
//2.将所有人依次加入队列
//这是ES6的for循环写法，i相当于nameList[i]
for(letiofnameList){
queue.enqueue(i)
}
//3.开始数数
while(queue.size()>1){//队列中只剩1个人就停止数数
//不是num的时候，重新加入队列末尾
//是num的时候，将其从队列中删除
//3.1.num数字之前的人重新放入队列的末尾(把队列前面删除的加到队列最后)
for(leti=0;i
测试结果：
三、优先队列
优先级队列主要考虑的问题为：
每个元素不再只是一个数据，还包含数据的优先级；在添加数据过程中，根据优先级放入到正确位置；3.1.优先级队列的实现
代码实现：
//封装优先级队列
functionPriorityQueue(){
//内部类：在类里面再封装一个类;表示带优先级的数据
functionQueueElement(element,priority){
this.element=element;
this.priority=priority;
}
//封装属性
this.items=[]
//1.实现按照优先级插入方法
PriorityQueue.prototype.enqueue=(element,priority)=>{
//1.1.创建QueueElement对象
letqueueElement=newQueueElement(element,priority)
//1.2.判断队列是否为空
if(this.items.length==0){
this.items.push(queueElement)
}else{
//定义一个变量记录是否成功添加了新元素
letadded=false
for(letiofthis.items){
//让新插入的元素与原有元素进行优先级比较(priority越小，优先级越大)
if(queueElement.priority{
returnthis.items.shift()
}
//3.front():查看前端的元素
PriorityQueue.prototype.front=()=>{
returnthis.items[0]
}
//4.isEmpty():查看队列是否为空
PriorityQueue.prototype.isEmpty=()=>{
returnthis.items.length==0;
}
//5.size():查看队列中元素的个数
PriorityQueue.prototype.size=()=>{
returnthis.items.length
}
//6.toString():以字符串形式输出队列中的元素
PriorityQueue.prototype.toString=()=>{
letresultString=''
for(letiofthis.items){
resultString+=i.element+'-'+i.priority+''
}
returnresultString
}
}
测试代码：
//测试代码
letpq=newPriorityQueue();
pq.enqueue('Tom',111);
pq.enqueue('Hellen',200);
pq.enqueue('Mary',30);
pq.enqueue('Gogo',27);
//打印修改过后的优先队列对象
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]中，pop(3)，结果为[0，1，2，3]；
- 栈：执行pop(0)，pop(1)，pop(2)，pop(3)，从栈底到栈顶的元素分别为：0，1，2，3；如果看成数组，可写为[0，1，2，3]，但是索引为3的元素3其实是栈顶元素；所以说栈的push方法是向栈顶添加元素（但在数组的视角下为向数组尾部添加元素）；
- 队列：enqueue方法可以由数组的push方法实现，与数组相同，相当于在数组尾部添加元素。
可以这样想：栈结构是头朝下（索引值由下往上增大）的数组结构。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。