Recommandations associées : tutoriel javascript
D'un point de vue de haut niveau, une file d'attente est une structure de données qui nous permet de traiter chaque élément de données dans l'ordre dans lequel il est stocké dans la base de données.
La file d'attente prend en charge 2 opérations principales : mettre en file d'attente et retirer de la file d'attente. De plus, il peut s'avérer utile d'effectuer des opérations d'aperçu et de longueur sur la file d'attente.
L'opération de mise en file d'attente dans la figure ci-dessus insère l'élément 8 jusqu'à la fin et 8 devient la fin de la file d'attente.
queue.enqueue(8);
Dans l'image ci-dessus, l'opération de retrait de la file d'attente renvoie et supprime l'élément 7 de la file d'attente. Après la sortie de la file d'attente, l'élément 2 devient le nouvel élément principal.
queue.dequeue(); // => 7
L'élément 7 est le début de la file d'attente dans l'image ci-dessus, et l'opération d'inspection renvoie uniquement l'en-tête (élément) 7 sans modifier la file d'attente.
queue.peek(); // => 7
Il y a 4 éléments dans la file d'attente dans l'image : 4, 6, 2 et 7. Par conséquent, la longueur de la file d'attente est de 4.
queue.length; // => 4
Le temps constant O(1) signifie que quelle que soit la taille de la file d'attente (elle peut contenir 10 ou 1 million d'éléments) : les opérations de mise en file d'attente, de retrait de la file d'attente, de coup d'œil et de longueur doivent toutes être effectuées simultanément.
Examinons une implémentation possible d'une structure de données de file d'attente tout en conservant l'exigence selon laquelle toutes les opérations doivent être effectuées en temps constant O(1).
file d'attente de classe {
constructeur() {
this.items = {};
this.headIndex = 0 ;
this.tailIndex = 0 ;
}
mettre en file d'attente (élément) {
this.items[this.tailIndex] = article ;
this.tailIndex++;
}
retirer la file d'attente() {
const item = this.items[this.headIndex];
supprimez this.items[this.headIndex] ;
this.headIndex++;
retourner l'article ;
}
coup d'oeil() {
retourner this.items[this.headIndex];
}
obtenir la longueur() {
retourner this.tailIndex - this.headIndex ;
}
}
const file d'attente = new Queue();
queue.enqueue(7);
queue.enqueue(2);
queue.enqueue(6);
queue.enqueue(4);
queue.dequeue(); // => 7
queue.peek(); // => 2
queue.length; // => 3 const queue = new Queue() explique comment créer une instance de file d'attente.
Appelez la méthode queue.enqueue(7) pour mettre l'élément 7 dans la file d'attente.
queue.dequeue() supprime un élément principal de la file d'attente, tandis que queue.peek() jette un coup d'œil depuis le début.
Enfin, queue.length indique combien d'éléments restent dans la file d'attente.
Concernant l'implémentation : à l'intérieur de la classe Queue, l'objet simple this.items contient les éléments de la file d'attente par index numérique. L'index de l'élément de tête est suivi par this.headIndex, et l'index de l'élément de queue est suivi par this.tailIndex.
Les méthodes queue(), dequeue(), peek() et length() de la classe Queue utilisent uniquement :
l'accès aux attributs (comme this.items[this.headIndex]), ou effectuer des opérations arithmétiques (telles que this.headIndex++).
Par conséquent, la complexité temporelle de ces méthodes est un temps constant O(1).
La structure des données de file d'attente est un type de "premier entré, premier sorti" (FIFO) : le premier élément à être mis en file d'attente est le premier élément à être retiré de la file d'attente.
Les files d'attente ont 2 opérations principales : mettre en file d'attente et retirer la file d'attente. De plus, les files d'attente peuvent avoir des opérations auxiliaires telles que l'affichage et la longueur.
Toutes les opérations de file d'attente doivent effectuer O(1) en temps constant.
Recommandations associées : Tutoriel d'apprentissage de JavaScript.
Ce qui précède est une explication détaillée de l'implémentation des files d'attente en JavaScript avec des exemples et des images. Pour plus d'informations, veuillez prêter attention aux autres articles connexes sur le site Web PHP chinois !
