JavaScript数据结构之优先队列与循环队列实例详解

2019-11-19 15:02:43

字体：大中小

来源：转载

供稿：网友

本文实例讲述了JavaScript数据结构之优先队列与循环队列。分享给大家供大家参考，具体如下：

优先队列

实现一个优先队列：设置优先级，然后在正确的位置添加元素。

我们这里实现的是最小优先队列，优先级的值小（优先级高）的元素被放置在队列前面。

//创建一个类来表示优先队列function Priorityqueue(){  var items=[];//保存队列里的元素  function QueueEle(e,p){//元素节点，有两个属性    this.element=e;//值    this.priority=p;//优先级  }  this.enqueue=function(e,p){//添加一个元素到队列尾部    var queueEle=new QueueEle(e,p);    var added=false;    //priority小的优先级高，优先级高的在队头    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 } ]

运行结果：

在正确的位置添加元素：如果队列为空，可以直接将元素入列。否则，就需要比较该元素与其他元素的优先级。当找到一个比要添加的元素优先级更低的项时，就把新元素插入到它之前，这样，对于其他优先级相同，但是先添加到队列的元素，我们同样遵循先进先出的原则。

最大优先队列：优先级的值大的元素放置在队列前面。

循环队列

实现击鼓传花游戏。

//创建一个类来表示队列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获胜

运行结果：