File d'attente prioritaire et file d'attente circulaire dans la structure de données JavaScript-js tutoriel-php.cn

File d'attente prioritaire et file d'attente circulaire dans la structure de données JavaScript

黄舟

Libérer： 2017-10-28 09:23:52

original

1761 Les gens l'ont consulté

L'exemple de cet article décrit la file d'attente JavaScript de priorité de structure de données et la file d'attente boucle . Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

File d'attente prioritaire

Mise en place d'une file d'attente prioritaire : définition de la priorité puis ajoutez l'élément à la bonne position.

Ce que nous implémentons ici est une file d'attente à priorité minimale, et les éléments avec de petites valeurs de priorité (priorité élevée) sont placés en tête de la file d'attente.

//创建一个类来表示优先队列
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 } ]

Copier après la connexion

Résultats d'exécution :

Ajouter des éléments à la bonne position : Si la file d'attente est vide, vous pouvez directement mettre l'élément en file d'attente. Sinon, vous devez comparer la priorité de cet élément avec d'autres éléments. Lorsqu'un élément de priorité inférieure à l'élément à ajouter est trouvé, le nouvel élément est inséré avant lui. De cette manière, pour les autres éléments de même priorité mais ajoutés en premier à la file d'attente, nous suivons également le premier entré. principe du premier sorti.

File d'attente à priorité maximale : les éléments avec des valeurs de priorité plus élevées sont placés en tête de la file d'attente.

File circulaire

Mettre en œuvre le jeu de tambour et de passage de fleurs.

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

Copier après la connexion

Résultat de l'exécution :

Obtenez une liste et ajoutez tous les noms qu'elle contient à la file d'attente. Étant donné un numéro, la file d’attente est itérée. Supprimez un élément de la tête de la file d'attente et ajoutez-le à la queue de la file d'attente pour simuler une file d'attente circulaire. Une fois que le nombre de passes atteint un nombre donné, la personne qui a obtenu la fleur est éliminée. Lorsqu'il ne reste qu'une seule personne à la fin, c'est lui qui est le gagnant.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!