Quelle est la différence entre une pile LIFO et une file FIFO ?
Réponse courte
Une pile est LIFO : le dernier élément ajouté est le premier retiré. Une file est FIFO : le premier élément arrivé est le premier retiré. Le choix dépend donc de l’ordre de traitement voulu.
Comprendre
Deux règles de retrait
Dans une pile, on empile et dépile au sommet : le dernier entré ressort d’abord (LIFO, Last In, First Out). Dans une file, on ajoute à une extrémité et on retire à l’autre : le premier arrivé sort en premier (FIFO, First In, First Out). Ces règles définissent l’ordre observable, quelle que soit la représentation interne.
Suivre les valeurs
Empile A, puis B, puis C : les dépilements donnent C, B, A. Enfile A, puis B, puis C : les défilements donnent A, B, C. Après un retrait de la file, D peut être ajouté ; B reste prioritaire sur C puis D. Une file convient à une attente ordinaire, tandis qu’une pile convient quand on reprend le travail le plus récent.
Pièges à éviter
Une liste Python peut représenter les deux structures, mais les opérations diffèrent : pop() à la fin d’une liste utilisée avec append réalise la pile ; pop(0) peut réaliser le retrait d’une file. Faire pop() dans ce dernier cas enlèverait C, donc inverserait la règle. Avec des valeurs identiques, cette erreur peut passer inaperçue ; teste avec des éléments distincts.
Exemples
- Pile : empiler 4, puis 7 ; dépiler renvoie 7 et laisse 4.
- File : enfiler A, B, C ; défiler renvoie A et laisse B puis C.
Pièges fréquents
- Retirer le dernier arrivé d’une file applique LIFO au lieu de FIFO et change l’ordre d’attente.
- Confondre l’interface avec une liste Python impose une représentation particulière alors que plusieurs implémentations peuvent respecter le même ordre.
