首页 > 代码库 > 队列&优先队列
队列&优先队列
1、队列
普通的队列都是先进先出，元素从队尾添加，从队头删除。
function queue(){ var arr=[]; this.enqueue=function(item){ arr.push(item); }; this.dequeue=function(){ arr.shift(); }; this.queueSize=function(){ return arr.length; }; this.isEmpty=function(){ return arr.length==0; }; this.front=function(){ return arr[0]; }; this.clear=function(){ arr=[]; }; this.print=function(){ console.log(arr.toString()); } } var q=new queue(); q.enqueue(‘1‘); q.enqueue(2); q.enqueue(3); q.dequeue() q.print();
2、优先级队列
优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出的特征。
| 任务编号 | 1 | 2 | 3 | 4 | 5 |
| 优先级编号 | 20 | 0 | 40 | 30 | 10 |
| 执行顺序 | 3 | 1 | 5 | 4 | 2 |
优先号越小，优先级越高。
优先队列主要有3个操作，查找，插入，删除。
分为两种最大优先队列和最小优先队列。
最大优先队列：先查找，找到优先级最大的元素将其删除。
最小优先队列：先查找，找到优先级最小的元素将其删除。
下面用JS写一个最大优先队列。入队列我们按照优先级从小到大排序，出队列仍然直接从队首出
function priorityQueue(){ var arr=[]; this.enqueue=function(item,pri){ // 入队列要比较优先级大小。同等优先级的情况下，按照普通队列处理 var flag=false; var temp={ item:item, pri:pri } for(var i=0,len=arr.length;i<len;i++){ if(arr[i].pri>temp.pri){ arr.splice(i,0,temp); flag=true; break; } } if(flag==false){ arr.push(temp); } }; this.dequeue=function(){ arr.shift(); }; this.size=function(){ return arr.length; }; this.isEmpty=function(){ return arr.length==0; }; this.front=function(){ return arr[0]; }; this.clear=function(){ arr=[]; }; this.print=function(){ for(var i=0;i<arr.length;i++){ console.log(arr[i].item); } } } var q=new priorityQueue(); q.enqueue(1,30); q.enqueue(2,20); q.enqueue(3,90); q.enqueue(4,0); q.enqueue(5,50); q.enqueue(7,30); q.enqueue(8,0); q.dequeue(); q.print();
队列&优先队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。