Numérique et Sciences Informatiques > Algorithmique : Structures de Données Avancées > Piles et Files > Principes LIFO et FIFO

Piles et Files : Comprendre les principes LIFO et FIFO

Explorez les concepts fondamentaux des piles (LIFO) et des files (FIFO) en informatique. Découvrez leurs fonctionnements, leurs applications pratiques et comment les implémenter.

Introduction aux Structures de Données Linéaires

Les structures de données linéaires sont des organisations séquentielles d'éléments. Parmi elles, les piles et les files sont des structures essentielles, caractérisées par des règles spécifiques d'insertion et de suppression des éléments. Comprendre ces règles est crucial pour bien utiliser ces structures.

Les Piles (LIFO - Last-In, First-Out)

Une pile est une structure de données qui suit le principe LIFO (Last-In, First-Out), ce qui signifie que le dernier élément ajouté à la pile est le premier à être retiré. Imaginez une pile d'assiettes : vous ajoutez une assiette sur le dessus, et lorsque vous voulez en retirer une, vous prenez celle du dessus en premier.

Opérations principales sur une pile :

  • Empiler (Push) : Ajouter un élément au sommet de la pile.
  • Dépiler (Pop) : Retirer l'élément du sommet de la pile.
  • Sommet (Top/Peek) : Accéder à l'élément du sommet sans le retirer.
  • EstVide (isEmpty) : Vérifier si la pile est vide.

Exemple concret : L'historique de navigation d'un navigateur web. Chaque fois que vous visitez une nouvelle page, elle est "empilée" en haut de l'historique. Lorsque vous cliquez sur le bouton "Précédent", la dernière page visitée (le sommet de la pile) est "dépilée" et affichée.

Les Files (FIFO - First-In, First-Out)

Une file est une structure de données qui suit le principe FIFO (First-In, First-Out), ce qui signifie que le premier élément ajouté à la file est le premier à être retiré. Imaginez une file d'attente : la première personne à entrer dans la file est la première à être servie.

Opérations principales sur une file :

  • Enfiler (Enqueue) : Ajouter un élément à la fin de la file.
  • Défiler (Dequeue) : Retirer l'élément du début de la file.
  • Tête (Front) : Accéder à l'élément du début de la file sans le retirer.
  • EstVide (isEmpty) : Vérifier si la file est vide.

Exemple concret : Une imprimante qui reçoit des tâches d'impression. Les tâches sont ajoutées à la file d'impression dans l'ordre où elles sont soumises, et l'imprimante les traite dans cet ordre.

Comparaison LIFO vs FIFO

La principale différence entre les piles (LIFO) et les files (FIFO) réside dans l'ordre de traitement des éléments.

  • Les piles sont idéales lorsque l'ordre inverse d'insertion est important.
  • Les files sont idéales lorsque l'ordre d'arrivée est important.
Le choix entre une pile et une file dépend donc du problème à résoudre. Voici un tableau comparatif:

CaractéristiquePile (LIFO)File (FIFO)
PrincipeDernier entré, premier sortiPremier entré, premier sorti
Opération d'ajoutEmpiler (Push)Enfiler (Enqueue)
Opération de suppressionDépiler (Pop)Défiler (Dequeue)
ExempleHistorique de navigationFile d'impression

Implémentation en Python

En Python, on peut implémenter une pile à l'aide d'une liste. Voici un exemple simple :

pile = []
pile.append(1) # Empiler 1
pile.append(2) # Empiler 2
pile.append(3) # Empiler 3
print(pile.pop()) # Dépiler (affiche 3)
print(pile.pop()) # Dépiler (affiche 2)
print(pile.pop()) # Dépiler (affiche 1)

Pour implémenter une file, on peut utiliser la classe `deque` du module `collections` :

from collections import deque
file = deque()
file.append(1) # Enfiler 1
file.append(2) # Enfiler 2
file.append(3) # Enfiler 3
print(file.popleft()) # Défiler (affiche 1)
print(file.popleft()) # Défiler (affiche 2)
print(file.popleft()) # Défiler (affiche 3)
La méthode `append` ajoute des éléments, `pop` retire le dernier élément pour les piles et `popleft` retire le premier élément pour les files.

Ce qu'il faut retenir

  • Une pile suit le principe LIFO (Last-In, First-Out). L'opération principale pour ajouter un élément est empiler (push), et pour retirer un élément, c'est dépiler (pop).
  • Une file suit le principe FIFO (First-In, First-Out). L'opération principale pour ajouter un élément est enfiler (enqueue), et pour retirer un élément, c'est défiler (dequeue).
  • Le choix entre une pile et une file dépend de l'ordre de traitement souhaité : inverse pour les piles, ordre d'arrivée pour les files.
  • En Python, on peut utiliser une liste pour implémenter une pile et `deque` pour une file.

← Parcours d'arbres binaires : Préfixe, Infixe, Suffixe Représentation des Arbres Binaires →

FAQ

  • Quelle est la différence entre une pile et un tableau (liste en Python)?

    Un tableau (ou une liste) permet d'accéder à n'importe quel élément directement grâce à son index. Une pile, en revanche, limite l'accès aux éléments, seul le sommet de la pile est directement accessible. L'accès aux autres éléments nécessite de dépiler les éléments supérieurs.
  • Dans quel cas est-il plus judicieux d'utiliser une pile plutôt qu'une file?

    Une pile est plus appropriée lorsque l'ordre inverse d'insertion est important, par exemple pour annuler une série d'actions (comme avec Ctrl+Z). Une file est plus appropriée lorsque l'ordre d'arrivée est important, par exemple pour gérer des tâches à exécuter dans l'ordre où elles ont été soumises.