Explication détaillée des principes de file d'attente JavaScript et exemples d'utilisation

Une file d'attente est une sorte de liste. La différence est qu'une file d'attente ne peut insérer des éléments qu'à la fin de la file d'attente et supprimer des éléments au début de la file d'attente. Les files d'attente sont utilisées pour stocker les données classées dans l'ordre, premier entré, premier sorti, ce qui est différent des piles (dernier entré, premier sorti). Dans la pile, le dernier élément placé sur la pile est traité en premier. Nous pouvons désormais imaginer la file d'attente comme lorsque nous allons au restaurant pour manger. Beaucoup de gens font la queue pour manger, et la personne à l'avant prend son repas en premier. Les nouveaux arrivants ne peuvent faire la queue qu’à l’arrière. jusqu'à ce que ce soit leur tour. Cet article présente principalement les principes et l'utilisation des files d'attente dans les structures de données et les algorithmes JavaScript, explique les concepts et les principes des files d'attente plus en détail et analyse les techniques de fonctionnement et les précautions associées pour la mise en œuvre et l'utilisation des files d'attente dans JavaScript Friends sous forme d'exemples. dans le besoin peuvent se référer à Next, j'espère que cela pourra aider tout le monde.

1 : Opérations sur la file d'attente

La file d'attente comporte deux opérations principales, insérer de nouveaux éléments en fin de file d'attente mettre en file d'attente ( ) et la méthode dequeue() qui supprime l'élément en tête de file d'attente. De plus, nous avons également une méthode qui lit l'élément en tête de file d'attente. nous pouvons appeler la front()Méthode. Cette méthode renvoie l'élément head et d'autres méthodes.

Après avoir vu la description ci-dessus, beaucoup d'entre nous peuvent penser aux tableaux. Il existe également deux méthodes dans les tableaux qui ont des fonctions similaires aux méthodes ci-dessus. La méthode push() dans le tableau ajoute également de nouveaux éléments à l'arrière. du tableau. Dans le tableau shift(), la méthode peut supprimer le premier élément du tableau. Le code suivant :

var arrs = [];
arrs.push("a");
arrs.push("b");
console.log(arrs); // ["a","b"];
arrs.shift();
console.log(arrs); // ['b'];

Ci-dessous, nous pouvons utiliser les deux méthodes de push() et shift() dans le tableau ci-dessus pour encapsuler notre classe Queue

1. On peut d'abord définir une classe Queue constructeur, comme suit :

function Queue() {
  this.dataStore = [];
}

Comme ci-dessus : this.dataStore = []; Lorsque le tableau est vide, tous les éléments dans la file d'attente sont stockés élémentaires.

2. La méthode d'ajout d'un élément à la queue de la file d'attente est la suivante :

function enqueue(element) {
   this.dataStore.push(element);
}

3. du chef de file d'attente est le suivant :

function dequeue() {
  return this.dataStore.shift()
}

4. Les éléments à lire du chef d'équipe sont les suivants :

function front() {
  return this.dataStore[0];
}

5. Les éléments pour lire la queue de l'équipe sont les suivants :

function back() {
  return this.dataStore[this.dataStore.length - 1];
}

6. la file d'attente

function toString() {
  var retStr = "";
  for(var i = 0; i < this.dataStore.length; ++i) {
    retStr += this.dataStore[i] + "\n";
  }
  return retStr;
}

7. Déterminez si la file d'attente est vide comme suit :

function empty(){
  if(this.dataStore.length == 0) {
    return true;
  }else {
    return false;
  }
}

Voici le code JS complet comme suit :

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  }
};

Nous sommes maintenant Vous pouvez tester le code ci-dessus : comme suit :

var q = new Queue();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.toString()); // a b c
q.dequeue();
console.log(q.toString()); // b c
console.log("Front of queue:" +q.front()); // b
console.log("Back of queue:" +q.back()); // c

2 : Utiliser des files d'attente pour trier les données

Par exemple, lors du tri des nombres de 0 à 99, le principe est : d'abord trier les nombres dans le chiffre des unités, puis trier à nouveau les nombres dans le chiffre des dizaines. Chaque nombre est divisé en différentes cases en fonction de la valeur du chiffre correspondant, puis la méthode du reste est utilisée pour les nombres à la place des unités, et la méthode de division est utilisée pour les nombres au 10ème chiffre. Ensuite, ce tri est appelé. "tri par base" . Ce n'est pas la méthode de tri la plus rapide, mais elle décrit quelques façons intéressantes d'utiliser les files d'attente.

Par exemple, le tableau suivant :

var nums = ["50","12","95","7","90","3","74","81","91","72"];

1 Après le tri par base - tri des unités, les nombres sont répartis dans différentes cases. (En JS, nous pouvons l'attribuer à différentes classes d'instances de file d'attente). Comme suit

queues[0] = 50 或者 90
queues[1] = 81 或者 91
queues[2] = 12 或者 72
queues[3] = 3
queues[4] = 74
queues[5] = 95
queues[6] 
queues[7] = 7
queues[8]
queues[9]

Selon l'ordre des cases, les résultats après tri des premiers chiffres des nombres sont les suivants :

nums = [50,90,81,91,12,72,3,74,95,7]

2. Répartissez ensuite les résultats du dernier tri à différentes cases en fonction de la valeur à la place des dizaines. Comme suit :

queues[5] = 50
queues[9] = 90
queues[8] = 81
queues[9] = 91
queues[1] = 12
queues[7] = 72
queues[0] = 3
queues[7] = 74
queues[9] = 95
queues[0] = 7

Enfin, sortez les numéros de la boîte pour former une nouvelle liste, qui est le numéro trié. Comme suit :

peut être généré comme suit :

nums = [3,7,12,50,72,74,81,90,91,95];

En utilisant la zone de liste de file d'attente comme ci-dessus, cet algorithme peut être implémenté. files d'attente, chaque file d'attente correspond à un nombre, enregistrez toutes les files d'attente dans un tableau et utilisez les opérations de reste et de division pour déterminer les chiffres des unités et des dizaines. Le reste de l'algorithme ajoute les nombres à la file d'attente correspondante, les réorganise en fonction de la valeur à un chiffre, puis les trie en fonction de la valeur à dix chiffres et ajoute les nombres triés en conséquence.

La fonction suivante attribue des nombres à la file d'attente correspondante en fonction des valeurs des chiffres des unités ou des dizaines.

/*
* 根据个位或十位上的数值，将数字分配到相应队列的函数
* @param digit
* digit=1 表示先按个位来分配
* digit = 10 表示是按十位来分配的
* @param n 表示循环比较多少次 一般数组几个数字就比较多少次
*/
distribute: function(nums,queues,n,digit){
   for(var i = 0; i < n; ++i) {
    if(digit == 1) {
      queues[nums[i] % 10].enqueue(nums[i]);
     }else {
      queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
     }
   }
}

Voici la fonction permettant de collecter les numéros de la file d'attente comme suit :

// 收集数字的函数
collect: function(queues,nums,n) {
  var i = 0;
  for(var digit = 0; digit < n; ++digit) {
    while(!queues[digit].empty()) {
      nums[i++] = queues[digit].dequeue();
    }
  }
}

En raison de l'omission ci-dessus, il y a de nombreuses étapes et la description peut ne pas être très claire. Jetons d'abord un coup d'œil à l'organigramme, combinons-le avec l'organigramme, et enfin combinons-le avec tout le code JS pour comprendre le principe de base. de "tri par base" ; ci-dessous, nous pouvons regarder le processus suivant Image

Enfin, tous les codes JS sont les suivants :

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  },
  /*
   * 根据个位或十位上的数值，将数字分配到相应队列的函数
   * @param digit
   * digit=1 表示先按个位来分配
   * digit = 10 表示是按十位来分配的
   * @param n 表示循环比较多少次 一般数组几个数字就比较多少次
   */
  distribute: function(nums,queues,n,digit){
    for(var i = 0; i < n; ++i) {
      if(digit == 1) {
        queues[nums[i] % 10].enqueue(nums[i]);
      }else {
        queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
      }
    }
  },
  // 收集数字的函数
  collect: function(queues,nums,n) {
    var i = 0;
    for(var digit = 0; digit < n; ++digit) {
      while(!queues[digit].empty()) {
        nums[i++] = queues[digit].dequeue();
      }
    }
  },
  dispArray: function(arr) {
    for(var i = 0; i < arr.length; ++i) {
      console.log(arr[i]);
    }
  }
};

Ce qui suit est le code JS "radix sort" pour les tests ; le code suivant :

var q = new Queue();
  q.enqueue("a");
  q.enqueue("b");
  q.enqueue("c");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue:" +q.front());
console.log("Back of queue:" +q.back());
var queues = [];
for(var i = 0; i < 10; ++i) {
   queues[i] = new Queue();
}
var nums = ["50","12","95","7","90","3","74","81","91","72"];
console.log("before radix sort: ");
console.log(nums);
q.distribute(nums,queues,10,1);
q.collect(queues,nums,10);
q.dispArray(nums);
console.log("分割线");
q.distribute(nums,queues,10,10);
q.collect(queues,nums,10);
q.dispArray(nums);

相关推荐：

php中队列原理以及写文件的图文代码详解

详解JavaScript队列函数和异步执行

JavaScript队列函数和异步执行详解

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!