Files d'attente prioritaires en javascript

Une file d'attente prioritaire est l'extension d'une structure de données de file d'attente simple avec des éléments contenant une valeur de priorité, une file d'attente est une collection d'éléments dans lesquels le premier élément à saisir la file d'attente est le premier élément à sortir d'une file d'attente. Cette technique d'exécution est connue sous le nom de FIFO (premier dans et premier sorti). Considérez une ligne de personnes debout à l'extérieur d'un guichet automatique, la personne à se tenir debout en premier dans la ligne sera celle qui utilisera d'abord le guichet automatique. La personne qui se joint à la fin de la file d'attente pour le guichet automatique sera la dernière à utiliser l'ATM.

Donc, maintenant nous savons quelle est une file d'attente de base, mais qu'en est-il de la file d'attente prioritaire? Dans la file d'attente prioritaire, chaque élément qui entre dans la file d'attente a deux valeurs, une valeur de priorité et les données. Les éléments qui ont la même valeur de priorité seront exécutés en fonction de FIFO (premier dans et premier sorti) Mais les éléments ayant une priorité plus élevée que les autres seront exécutés d'abord, peu importe quand ils ont été ajoutés dans la file d'attente.

Il s'agit d'un sujet de structure de données avancé, nous supposons donc que vous connaissez le fonctionnement de JavaScript et les fonctionnalités de base de JavaScript. Pour implémenter une file d'attente prioritaire en JavaScript, nous devons d'abord savoir comment implémenter une file d'attente simple dans JavaScript.

Implémentation d'une file d'attente dans JavaScript

Les concepts de structure de données comme les files d'attente, les piles, les tas ou les files d'attente prioritaires sont implémentées à l'aide de tableaux en javascript.

Définissons une fonction qui définira notre structure:

Function Queue ()
// Le code ultérieur sera placé à l'intérieur ici

Nous savons que les files d'attente sont implémentées avec des tableaux, nous allons donc créer un tableau nommé Collections

À l'intérieur de la fonction:

Array = [];

Maintenant, pour implémenter la structure de données des files d'attente, nous devons implémenter les fonctionnalités suivantes:

• ENQUEUE: Pour ajouter un nouvel élément à la fin de la liste
• Dequeue: pour supprimer le premier élément de la liste
• iSempty: pour vérifier si la file d'attente est vide ou non
• Taille: pour retourner la longueur de la file d'attente
• Front: pour retourner la valeur du premier élément de la liste
• Imprimer: pour imprimer la file d'attente

Ces fonctionnalités sont toutes facilement ajoutées en utilisant les lignes de code suivantes:

functionQueue ()
Array = [];
ce.print = function ()
console.journal (tableau);
;
ce.enqueue = fonction (newMem)
déployer.push (NewMem);
;
ce.dequeue = function ()
returnArray.changement();
;
ce.front = function ()
Return Array [0];
;
ce.size = function ()
returnArray.longueur;
;
ce.isEmpty = function ()
retour (tableau.longueur === 0);
;

Maintenant que nous avons notre structure de données prête, nous devons créer un objet mappé sur cette structure, nous le faisons en utilisant la ligne:

var newqueue = new queue ();

Maintenant, nous avons besoin de certains éléments à placer dans la file d'attente, nous le faisons en utilisant les lignes suivantes:

Newqueue.ENQUEUe («A»);
Newqueue.ENQUEUe ('B');
Newqueue.ENQUEUe ('C');

Pour voir à quoi ressemble notre file d'attente en ce moment, nous pouvons appeler la fonction d'impression comme tel:

Newqueue.imprimer();

Nous obtenons la sortie suivante sur notre console:

Pour tester, si la mise en œuvre du premier et de la première sortie fonctionne correctement, nous allons désactiver un élément de la liste, et imprimer la valeur la plus importante, puis imprimer toute la file d'attente restante avec les lignes suivantes:

Newqueue.Dequeue ();
console.journal (newqueue.devant());
Newqueue.imprimer();

L'extrait de code complet de la structure de la file d'attente est:

functionQueue ()
Array = [];
ce.print = function ()
console.journal (tableau);
;
ce.enqueue = fonction (newMem)
déployer.push (NewMem);
;
ce.dequeue = function ()
returnArray.changement();
;
ce.front = function ()
Return Array [0];
;
ce.size = function ()
returnArray.longueur;
;
ce.isEmpty = function ()
returnArray.longueur === 0;
;

varNewQueue = new queue ();
Newqueue.ENQUEUe ("A");
Newqueue.ENQUEUe ("B");
Newqueue.ENQUEUe ("C");
Newqueue.imprimer();
Newqueue.Dequeue ();
console.journal (newqueue.devant());
Newqueue.imprimer();

Lors de l'exécution de ce code, nous pouvons observer le résultat suivant sur la console:

Ainsi, lorsque nous avons appelé la fonction de désagréation, il a supprimé le premier élément de la liste. Après cela, nous avons vérifié l'élément le plus important de la file d'attente qui était "B". Ensuite, nous avons à nouveau imprimé la file d'attente et cela nous a donné la file d'attente restante dans le bon ordre. Cela signifie que notre mise en œuvre de la file d'attente fonctionne parfaitement:

Implémentation d'une file d'attente prioritaire dans JavaScript

Nous savons que la différence entre une file d'attente normale et une file d'attente prioritaire est que les éléments à l'intérieur de la file d'attente prioritaire contiennent une valeur de priorité avec leurs données. Cela signifie que toutes les fonctionnalités de la file d'attente prioritaire sont les mêmes qu'une file d'attente normale, sauf pour le Fonction d'attache.

Dans les files d'attente prioritaires, la fonction d'Enqueue place l'élément de priorité plus élevé avant l'élément de priorité inférieur. Et si deux éléments ou plus ont la même priorité, les éléments nouvellement ajoutés sont placés à l'extrémité ultérieure de la file d'attente pour maintenir une méthode d'évaluation de premier et de première sortie.

Ainsi, en gardant cela à l'esprit, nous pouvons écrire la nouvelle fonction d'agitation pour la file d'attente prioritaire avec les lignes de code suivantes:

ce.enqueue = fonction (newMem)
var array = [];
// Le code ultérieur sera placé à l'intérieur ici
;

La première chose que nous faisons dans la fonction ENQUEUe est que si la collection est vide, alors nous poussons l'élément sur la file d'attente:

si ce.est vide())
déployer.push (NewMem);

Si la file d'attente n'est pas vide:

• Ensuite, nous allons vérifier la priorité du nouvel élément avec la priorité de chaque élément de la file d'attente
• Si la priorité du nouvel élément est inférieure à l'élément de la collection.Nous allons ajouter le nouvel élément avant l'élément de cette collection
• Ceci est dû au fait 1 signifie première priorité alors que 2 signifie deuxième priorité
• Si la priorité du nouvel élément est plus grande en valeur (plus faible en priorité réelle), alors nous allons passer à la fin de la file d'attente et ajouter l'élément là-bas

autre
var ajouté = false;
pour (vari = 0; iif (NewMem [1] < array[i][1])
déployer.Splice (I, 0, NewMem);
ajouté = true;
casser;


si (!ajoutée)
déployer.push (NewMem);

La totalité enquérir La fonction ressemblera à ceci:

ce.enqueue = fonction (newMem)
si ce.est vide())
déployer.push (NewMem);
autre
var ajouté = false;
pour (vari = 0; iif (NewMem [1] < array[i][1])
déployer.Splice (I, 0, NewMem);
ajouté = true;
casser;


si (!ajoutée)
déployer.push (NewMem);


;

Le reste des fonctions de file d'attente prioritaire est à peu près la même que la file d'attente normale, avec un léger changement de fonction de désactivation pour afficher uniquement le nom et non la valeur de l'élément. L'ensemble de l'extrait de code de file d'attente prioritaire est:

functionPriorityQueue ()
VarArray = [];
ce.printCollection = function ()
console.journal (tableau);
;
ce.enqueue = fonction (newMem)
si ce.est vide())
déployer.push (NewMem);
autre
var ajouté = false;
pour (vari = 0; iif (NewMem [1] déployer.Splice (I, 0, NewMem);
ajouté = true;
casser;


si (!ajoutée)
déployer.push (NewMem);


;
ce.dequeue = function ()
VAR VALLE = tableau.changement();
valeur de retour [0];
;
ce.front = function ()
returnArray [0];
;
ce.size = function ()
returnArray.longueur;
;
ce.isEmpty = function ()
returnArray.longueur === 0;
;

Il est temps de mettre des éléments dans la file d'attente en utilisant les lignes de code suivantes:

var pq = new priorityQueue ();
pq.Enqueue (["Google", 2]);
pq.Enqueue (["Bing", 3]);
pq.enqueue (["Microsoft", 1]);
pq.Enqueue (["Apple", 2]);
pq.printCollection ();

Comme vous pouvez le voir, la première priorité est le "Microsoft" élément avec valeur 1. Ce doit être au début de la file d'attente même s'il a été ajouté à la 3e place.

Maintenant, si nous appelons la fonction DeQueue, puis la fonction d'impression à nouveau, le premier élément doit être supprimé de la liste:

pq.Dequeue ();
pq.printCollection ();

Voilà, notre file d'attente prioritaire fonctionne parfaitement.

Conclusion

Les files d'attente sont des concepts de structure de données qui fonctionnent sur la méthode d'évaluation du premier-in et du premier-out. De même, les files d'attente prioritaires fonctionnent sur l'évaluation du premier et du premier-out, mais avec une valeur supplémentaire de «priorité», l'élément avec la priorité la plus élevée sera exécuté d'abord, peu importe quand ils ont été ajoutés à la file d'attente. Dans cet article, nous avons appris à implémenter une file d'attente simple en JavaScript et à utiliser cette structure de données pour implémenter le fonctionnement d'une file d'attente prioritaire.