Dernièrement, nous avons vu la structure des données de la pile et comment implémenter notre propre version des piles à l'aide de JavaScript. Dans cet article, nous allons voir un autre type de structure de données qui va dans le même bucket et qui est souvent mentionné à côté des piles. Nous allons parler des files d'attente cette fois.

Files d'attente : concepts

Les files d'attente sont aussi importantes que les piles dans le monde de l'informatique. Ils sont utilisés dans de nombreuses situations différentes. Je pourrais peut-être affirmer qu'ils sont indispensables dans tout système important et important qui nécessite beaucoup de communication, de planification et de priorisation.

# Que sont les files d'attente ?

Une file d'attente est une structure de données linéaire où les éléments sont disposés les uns après les autres. De la même manière que les piles, elles ont certaines restrictions quant à la manière dont les opérations (insertion et suppression) sont effectuées sur elles. Dans les files d'attente, les opérations sont effectuées sur deux extrémités plutôt qu'une seule extrémité comme dans le cas des piles. Une file d'attente fonctionne sur le principe du premier entré, premier sorti (FIFO). Si nous souhaitons illustrer les files d'attente avec un exemple de notre vie quotidienne, nous pourrions observer la file d'attente des personnes dans un magasin Starbucks qui attendent leur café. Le premier qui arrive est le premier servi et ainsi de suite...

Ainsi, lorsque quelqu'un vient acheter un café, il se place au fond de la file d'attente. En termes de structures de données, nous dirions que nous sommes en file d'attente. En d'autres termes, nous insérons un nouvel élément à l'arrière de la file d'attente. En revanche, si celui en tête de file est servi, il laisserait alors sa place à celui d'après et ainsi de suite. Encore une fois, en termes de structures de données, nous dirions que nous sortons un élément de la file d'attente ou que nous supprimons un élément de la tête de la file d'attente.

# Pourquoi utiliseriez-vous des files d'attente ?

Je ne peux pas compter les différents scénarios où les files d'attente conviennent plus que tout autre type de structure de données. Pourtant, j'énumérerais deux raisons principales qui pourraient vous donner un aperçu du fait que vous avez peut-être besoin d'utiliser des files d'attente pour une situation particulière.

1. Attendre…

2. Un ordre équitable…

Si le problème que vous résolvez veut que vous garantissiez que le premier qui arrive doit être le premier à être servi, alors une file d'attente pour le sauvetage. Le fait que les files d'attente suivent le principe FIFO donne l'assurance d'un ordre équitable.

Files d'attente : implémentation en JavaScript

Maintenant, nous allons implémenter notre version personnalisée des files d'attente en utilisant JavaScript. Dans le dernier article, nous avons mentionné que les piles peuvent être implémentées en utilisant des tableaux ou des listes chaînées selon vos besoins. Cependant, pour la structure de données de la file d'attente, l'utilisation d'une liste chaînée serait une approche plus sage, peu importe. Pourquoi?

En termes simples, si nous utilisons des tableaux, l' opération de retrait de la file d'attente, par exemple, nécessiterait de déplacer le tableau chaque fois que nous supprimons un élément de la file d'attente. Cela prendrait du temps. Par conséquent, cela augmente la complexité temporelle de votre solution. De plus, en supposant que vous ne ferez aucun décalage après avoir retiré un élément de la file d'attente, cela peut entraîner un gaspillage de mémoire car vous laissez des espaces vides dans le tableau. Encore une fois, cela conduit à une augmentation de la complexité de l'espace de votre solution.

Maintenant, faisons-le en utilisant plutôt des listes liées…

Nous n'avons pas encore fini… Ce morceau de code a besoin de quelques améliorations…

Files d'attente : maintenant, c'est à vous de jouer…

# Tâche 1

Utilisez votre langage de programmation préféré pour ajouter une nouvelle opération back() pour afficher la valeur à l'arrière de la file d'attente.

# Tâche 2

Nous avons besoin d'une opération pour imprimer la file d'attente, pouvez-vous le faire pour nous, s'il vous plaît ? Néanmoins, utilisez votre langage de programmation préféré…

Attendez une seconde, s'il vous plaît ! Avant de partir, si vous le souhaitez, connectons-nous…

• Sur YouTube
• Sur Linkedin
• Sur Twitter