Prioritätswarteschlange und zirkuläre Warteschlange in der JavaScript-Datenstruktur-js-Tutorial-php.cn

Prioritätswarteschlange und zirkuläre Warteschlange in der JavaScript-Datenstruktur

黄舟

Freigeben： 2017-10-28 09:23:52

Original

1760 Leute haben es durchsucht

Das Beispiel in diesem Artikel beschreibt die JavaScript-Datenstrukturprioritäts--Warteschlange und die Schleifen--Warteschlange. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Prioritätswarteschlange

Implementieren einer Prioritätswarteschlange: Festlegen der Priorität und fügen Sie dann das Element an der richtigen Position hinzu.

Was wir hier implementieren, ist eine Warteschlange mit minimaler Priorität, und Elemente mit kleinen Prioritätswerten (hohe Priorität) werden an den Anfang der Warteschlange gestellt.

//创建一个类来表示优先队列
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(&#39;a&#39;,2);
pqueue.enqueue(&#39;b&#39;,1);
pqueue.enqueue(&#39;c&#39;,2);
pqueue.enqueue(&#39;d&#39;,2);
pqueue.enqueue(&#39;e&#39;,1);
pqueue.print();
//[ QueueEle { element: &#39;b&#39;, priority: 1 },
// QueueEle { element: &#39;e&#39;, priority: 1 },
// QueueEle { element: &#39;a&#39;, priority: 2 },
// QueueEle { element: &#39;c&#39;, priority: 2 },
// QueueEle { element: &#39;d&#39;, priority: 2 } ]

Nach dem Login kopieren

Ausführungsergebnisse:

Elemente an der richtigen Position hinzufügen: Wenn die Warteschlange leer ist, können Sie das Element direkt in die Warteschlange stellen. Andernfalls müssen Sie die Priorität dieses Elements mit anderen Elementen vergleichen. Wenn ein Element mit einer niedrigeren Priorität als das hinzuzufügende Element gefunden wird, wird das neue Element davor eingefügt. Auf diese Weise folgen wir für andere Elemente mit derselben Priorität, die jedoch zuerst zur Warteschlange hinzugefügt werden, ebenfalls dem ersten Element. First-out-Prinzip.

Warteschlange mit maximaler Priorität: Elemente mit größeren Prioritätswerten werden an den Anfang der Warteschlange gestellt.

Rundförmige Warteschlange

Implementieren Sie das Trommel- und Blumenspiel.

//创建一个类来表示队列
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=&#39;&#39;;
  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=[&#39;a&#39;,&#39;b&#39;,&#39;c&#39;,&#39;d&#39;,&#39;e&#39;];
var winner=hotPotato(namelist,7);
console.log(winner+"获胜");
//淘汰c
//淘汰b
//淘汰e
//淘汰d
//a获胜

Nach dem Login kopieren

Ergebnis ausführen:

Rufen Sie eine Liste ab und fügen Sie alle darin enthaltenen Namen zur Warteschlange hinzu. Bei gegebener Zahl wird die Warteschlange iteriert. Entfernen Sie ein Element vom Kopf der Warteschlange und fügen Sie es am Ende der Warteschlange hinzu, um eine kreisförmige Warteschlange zu simulieren. Sobald die Anzahl der Durchgänge eine bestimmte Anzahl erreicht, scheidet die Person aus, die die Blume erhalten hat. Wenn am Ende nur noch einer übrig ist, ist er der Gewinner.

Das obige ist der detaillierte Inhalt vonPrioritätswarteschlange und zirkuläre Warteschlange in der JavaScript-Datenstruktur. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!