Introduction
Les structures de données organisent le stockage dans les ordinateurs afin que nous puissions accéder et modifier efficacement les données. Les piles et les files d’attente sont parmi les premières structures de données définies en informatique.
Simples à apprendre et faciles à mettre en œuvre, leurs utilisations sont courantes et vous vous retrouverez très probablement à les incorporer dans votre logiciel pour diverses tâches.
Il est courant que les piles et les files d’attente soient implémentées avec un tableau ou une liste chaînée. Nous nous appuierons sur la structure de données List pour accueillir à la fois les piles et les files d’attente.
Comment fonctionnent-ils ?
Pile
Les piles, comme leur nom l’indique, suivent le principe du Dernier entré, premier sorti (LIFO). Comme si on empilait des pièces les unes sur les autres, la dernière pièce que nous mettons sur le dessus est celle qui sera la première à être retirée de la pile plus tard.
Pour implémenter une pile, nous avons donc besoin de deux opérations simples :
-
push– ajoute un élément en haut de la pile:
-
pop– supprime l’élément en haut de la pile :
Queue
Les files d’attente, comme leur nom l’indique, suivent le principe du premier entré, premier sorti (FIFO). Comme si vous attendiez dans une file d’attente pour les billets de cinéma, le premier à faire la queue est le premier à acheter un billet et à profiter du film.
Pour implémenter une file d’attente, nous avons donc besoin de deux opérations simples :
-
enqueue– ajoute un élément à la fin de la file d’attente:
-
dequeue– supprime l’élément au début de la file d’attente :
Piles et files d’attente utilisant des listes
La structure de données List intégrée à Python est livrée avec des méthodes pour simuler les opérations de pile et de file d’attente.
Considérons une pile de lettres:
Nous pouvons utiliser les mêmes fonctions pour implémenter une file d’attente. La fonction pop prend éventuellement l’index de l’élément que nous voulons récupérer en argument.
Nous pouvons donc utiliser pop avec le premier index de la liste, c’est-à-dire 0, pour obtenir un comportement de type file d’attente.
Considérons une « file d’attente » de fruits:
Encore une fois, nous utilisons ici les opérations append et pop de la liste pour simuler les opérations principales d’une file d’attente.
Piles et files d’attente avec la bibliothèque Deque
Python a une bibliothèque deque (prononcé ‘deck’) qui fournit une séquence avec des méthodes efficaces pour fonctionner comme une pile ou une file d’attente.
deque est l’abréviation de File d’attente à double extrémité – une file d’attente généralisée qui peut obtenir le premier ou le dernier élément stocké:
Si vous souhaitez en savoir plus sur la bibliothèque deque et d’autres types de collections fournies par Python, vous pouvez lire notre article Introduction au module Collections de Python.
Implémentations plus strictes en Python
Si votre code avait besoin d’une pile et que vous fournissez un List, rien n’empêche un programmeur d’appeler insertremove ou d’autres fonctions de liste qui affecteront l’ordre de votre pile! Cela ruine fondamentalement le point de définir une pile, car elle ne fonctionne plus comme elle le devrait.
Il y a des moments où nous aimerions nous assurer que seules des opérations valides peuvent être effectuées sur nos données.
Nous pouvons créer des classes qui n’exposent que les méthodes nécessaires pour chaque structure de données.
Pour ce faire, créons un nouveau fichier appelé stack_queue.py et définissons deux classes:
Les programmeurs utilisant notre Stack et Queue sont maintenant encouragés à utiliser les méthodes fournies pour manipuler les données à la place.
Exemples
Imaginez que vous êtes un développeur travaillant sur un tout nouveau traitement de texte. Vous êtes chargé de créer une fonctionnalité d’annulation, permettant aux utilisateurs de revenir en arrière sur leurs actions jusqu’au début de la session.
Une pile est idéale pour ce scénario. Nous pouvons enregistrer chaque action de l’utilisateur en la poussant dans la pile. Lorsque l’utilisateur souhaite annuler une action, il la fait sortir de la pile. Nous pouvons rapidement simuler la fonctionnalité comme ceci:
Les files d’attente ont également des utilisations répandues en programmation. Pensez à des jeux comme Street Fighter ou Super Smash Brothers. Les joueurs de ces jeux peuvent effectuer des mouvements spéciaux en appuyant sur une combinaison de boutons. Ces combinaisons de boutons peuvent être stockées dans une file d’attente.
Imaginez maintenant que vous êtes un développeur travaillant sur un nouveau jeu de combat. Dans votre jeu, chaque fois qu’un bouton est enfoncé, un événement d’entrée est déclenché. Un testeur a remarqué que si les boutons sont pressés trop rapidement, le jeu ne traite que le premier et les coups spéciaux ne fonctionneront pas!
Vous pouvez résoudre ce problème avec une file d’attente. Nous pouvons mettre en file d’attente tous les événements d’entrée au fur et à mesure qu’ils entrent. De cette façon, peu importe si les événements d’entrée ont peu de temps entre eux, ils seront tous stockés et disponibles pour le traitement. Lorsque nous traitons les mouvements, nous pouvons les retirer de la file d’attente. Un mouvement spécial peut être élaboré comme ceci:
Conclusion
Les piles et les files d’attente sont de simples structures de données qui nous permettent de stocker et de récupérer des données de manière séquentielle. Dans une pile, le dernier élément que nous entrons est le premier à sortir. Dans une file d’attente, le premier élément que nous entrons est le premier sorti.
Nous pouvons ajouter des éléments à une pile en utilisant l’opération push et récupérer des éléments en utilisant l’opération pop. Avec les files d’attente, nous ajoutons des éléments en utilisant l’opération enqueue et récupérons des éléments en utilisant l’opération dequeue.
En Python, nous pouvons implémenter des piles et des files d’attente simplement en utilisant la structure de données List intégrée. Python a également la bibliothèque deque qui peut fournir efficacement des opérations de pile et de file d’attente dans un objet. Enfin, nous avons créé nos classes de pile et de file d’attente pour un contrôle plus strict de nos données.
Il existe de nombreux cas d’utilisation réels pour les piles et les files d’attente, les comprendre nous permet de résoudre de nombreux problèmes de stockage de données de manière simple et efficace.