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 vos logiciels pour diverses tâches.

Il est courant que les piles et les files d’attente soient mises en œuvre 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-elles ?

Pile

Les piles, comme leur nom l’indique, suivent le principe du dernier entré, premier sorti (LIFO). Comme si on empilait des pièces de monnaie les unes sur les autres, la dernière pièce que l’on met sur le dessus est celle qui sera la première à être retirée de la pile par la suite.

Pour mettre en œuvre une pile, nous avons donc besoin de deux opérations simples :

• push – ajoute un élément au sommet de la pile :

• pop – retire l’élément au sommet de la pile:

Queueue

Les files d’attente, comme leur nom l’indique, suivent le principe du premier entré, premier sorti (FIFO). Comme 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 mettre en œuvre 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 à l’aide de listes

La structure de données intégrée de ListPython est fournie avec des méthodes pour simuler les opérations de pile et de file d’attente.

Préoccupons-nous d’une pile de lettres :

Nous pouvons utiliser les mêmes fonctions pour mettre en œuvre une file d’attente. La fonction pop prend optionnellement l’index de l’élément que nous voulons récupérer comme argument.

Nous pouvons donc utiliser pop avec le premier index de la liste c’est-à-dire 0, pour obtenir un comportement de type queue.

Considérez une « queue » de fruits:

De nouveau, ici nous utilisons les opérations append et pop de la liste pour simuler les opérations de base d’une queue.

Piles et files d’attente avec la bibliothèque Deque

Python possède une bibliothèque deque (prononcez ‘deck’) qui fournit une séquence avec des méthodes efficaces pour travailler comme une pile ou une queue.

deque est l’abréviation de Double Ended Queue – 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 les autres types de collections que Python fournit, vous pouvez lire notre article Introduction au module des collections de Python.

Mise en œuvre de stratagèmes en Python

Si votre code avait besoin d’une pile et que vous fournissez une List, rien n’empêche un programmeur d’appeler insert, remove ou d’autres fonctions de liste qui affecteront l’ordre de votre pile ! Cela ruine fondamentalement l’intérêt de définir une pile, car elle ne fonctionne plus comme elle le devrait.

Il y a des moments où nous voudrions nous assurer que seules les 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 nos 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 fonction d’annulation – permettant aux utilisateurs de revenir sur leurs actions jusqu’au début de la session.

Une pile est un ajustement idéal pour ce scénario. Nous pouvons enregistrer chaque action de l’utilisateur en la poussant dans la pile. Lorsque l’utilisateur veut annuler une action, il la sortira de la pile. Nous pouvons rapidement simuler la fonctionnalité comme ceci:

Les queues ont des utilisations répandues dans la programmation aussi. 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 pressé, 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 fonctionnent pas !

Vous pouvez corriger cela 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 arrivent. De cette façon, cela n’a pas d’importance si les événements d’entrée viennent avec 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 coup spécial peut être travaillé comme ceci:

Conclusion

Les piles et les files d’attente sont des structures de données simples qui nous permettent de stocker et de récupérer des données séquentiellement. 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 à sortir.

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 juste en utilisant la structure de données List intégrée. Python dispose également de la bibliothèque deque qui peut fournir efficacement des opérations de pile et de file d’attente dans un seul objet. Enfin, nous avons fait nos classes de pile et de file d’attente pour un contrôle plus serré de nos données.

Il existe de nombreux cas d’utilisation dans le monde réel pour les piles et les files d’attente, leur compréhension nous permet de résoudre de nombreux problèmes de stockage de données de manière simple et efficace.