JavaScript數據結構之優(yōu)先隊列與循環(huán)隊列實例詳解
本文實例講述了JavaScript數據結構之優(yōu)先隊列與循環(huán)隊列。分享給大家供大家參考,具體如下:
優(yōu)先隊列
實現一個優(yōu)先隊列:設置優(yōu)先級,然后在正確的位置添加元素。
我們這里實現的是最小優(yōu)先隊列,優(yōu)先級的值?。▋?yōu)先級高)的元素被放置在隊列前面。
//創(chuàng)建一個類來表示優(yōu)先隊列 function Priorityqueue(){ var items=[];//保存隊列里的元素 function QueueEle(e,p){//元素節(jié)點,有兩個屬性 this.element=e;//值 this.priority=p;//優(yōu)先級 } this.enqueue=function(e,p){//添加一個元素到隊列尾部 var queueEle=new QueueEle(e,p); var added=false; //priority小的優(yōu)先級高,優(yōu)先級高的在隊頭 if(this.isEmpty()){ items.push(queueEle); }else{ for(var i=0;i<items.length;i++){ if(items[i].priority>queueEle.priority){ items.splice(i,0,queueEle); added=true; break; } } if(!added){ items.push(queueEle); } } } this.isEmpty=function(){ return items.length==0; } this.dequeue=function(){ return items.shift(); } this.clear=function(){ items=[]; } this.print=function(){ console.log(items); } this.mylength=function(){ return items.length; } } var pqueue=new Priorityqueue(); pqueue.enqueue('a',2); pqueue.enqueue('b',1); pqueue.enqueue('c',2); pqueue.enqueue('d',2); pqueue.enqueue('e',1); pqueue.print(); //[ QueueEle { element: 'b', priority: 1 }, // QueueEle { element: 'e', priority: 1 }, // QueueEle { element: 'a', priority: 2 }, // QueueEle { element: 'c', priority: 2 }, // QueueEle { element: 'd', priority: 2 } ]
運行結果:
在正確的位置添加元素:如果隊列為空,可以直接將元素入列。否則,就需要比較該元素與其他元素的優(yōu)先級。當找到一個比要添加的元素優(yōu)先級更低的項時,就把新元素插入到它之前,這樣,對于其他優(yōu)先級相同,但是先添加到隊列的元素,我們同樣遵循先進先出的原則。
最大優(yōu)先隊列:優(yōu)先級的值大的元素放置在隊列前面。
循環(huán)隊列
實現擊鼓傳花游戲。
//創(chuàng)建一個類來表示隊列 function Queue(){ var items=[];//保存隊列里的元素 this.enqueue=function(e){//添加一個元素到隊列尾部 items.push(e); } this.dequeue=function(){//移除隊列的第一項,并返回 return items.shift(); } this.front=function(){//返回隊列的第一項 return items[0]; } this.isEmpty=function(){//如果隊列中部包含任何元素,返回true,否則返回false return items.length==0; } this.mylength=function(){//返回隊列包含的元素個數 return items.length; } this.clear=function(){//清除隊列中的元素 items=[]; } this.print=function(){//打印隊列中的元素 console.log(items); } } //擊鼓傳花 function hotPotato(namelist,num){ var queue=new Queue(); for(var i=0;i<namelist.length;i++){ queue.enqueue(namelist[i]); } var eliminated=''; while(queue.mylength()>1){ for(i=0;i<num;i++){ queue.enqueue(queue.dequeue()); } eliminated=queue.dequeue(); console.log("淘汰"+eliminated); } return queue.dequeue(); } var namelist=['a','b','c','d','e']; var winner=hotPotato(namelist,7); console.log(winner+"獲勝"); //淘汰c //淘汰b //淘汰e //淘汰d //a獲勝
運行結果:
得到一份名單,把里面的名字全都加入隊列。給定一個數字,然后迭代隊列。從隊列頭移除一項,加入到隊列尾部,模擬循環(huán)隊列。一旦傳遞次數達到給定的數字,拿到花的那個人就被淘汰。最后只剩一個人的時候,他就是勝利者。
更多關于JavaScript相關內容感興趣的讀者可查看本站專題:《JavaScript數據結構與算法技巧總結》、《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
相關文章
JavaScript引用類型之基本包裝類型實例分析【Boolean、Number和String】
這篇文章主要介紹了JavaScript引用類型之基本包裝類型,結合實例形式分析了javascript中Boolean、Number和String三種基本包裝類型的基本用法與相關操作注意事項,需要的朋友可以參考下2018-08-08