Introduction aux Piles (LIFO)

1. Qu'est-ce qu'une Pile ?

Imaginez que vous rangiez une pile d'assiettes. Vous posez la première assiette, puis une deuxième par-dessus, puis une troisième. Quand vous voulez reprendre une assiette, laquelle prenez-vous ? Naturellement, celle du dessus, la dernière que vous avez posée. Vous ne pouvez pas retirer une assiette du milieu sans faire tomber toute la pile.

Une pile (en anglais, stack) en algorithmique fonctionne exactement sur ce même principe. C'est une structure de données où l'on ne peut ajouter ou retirer des éléments qu'à une seule extrémité, appelée le sommet de la pile.

Cette règle d'accès a une conséquence très importante : le dernier élément ajouté à la pile sera toujours le premier à en être retiré. C'est ce qu'on appelle le principe LIFO : Last-In, First-Out (Dernier Arrivé, Premier Sorti).

Pour approfondir cette définition et l'analogie, je vous invite à lire un court extrait d'un cours.

2. Visualiser les opérations de base

Les deux opérations fondamentales d'une pile sont donc :

• Empiler (Push) : Ajouter un élément au sommet de la pile.
• Dépiler (Pop) : Retirer l'élément qui se trouve au sommet de la pile.

L'image suivante illustre parfaitement ce processus.

Analysons cette image ensemble :

1. On part d'une pile vide.
2. Empiler(B) : B est ajouté. Le sommet est B.
3. Empiler(A) : A est ajouté sur B. Le sommet est maintenant A.
4. Empiler(E), Empiler(C), Empiler(D) : Les éléments sont ajoutés successivement au sommet. Après ces opérations, le sommet est D.
5. Dépiler() : L'élément au sommet, D, est retiré. Le nouveau sommet devient C.

Si on voulait dépiler à nouveau, on retirerait C, puis E, et ainsi de suite. L'ordre de sortie serait l'inverse de l'ordre d'entrée : D, C, E, A, B.

3. Les opérations fondamentales en détail

Au-delà d'empiler et dépiler, une gestion propre d'une pile nécessite quelques opérations supplémentaires pour vérifier son état et l'initialiser. Une bonne conception algorithmique, qui mène à un "code clean", doit toujours anticiper les cas d'erreur : que se passe-t-il si on essaie de dépiler une pile vide ?

Pour comprendre l'ensemble des opérations, nous allons nous baser sur une spécification formelle.

Synthétisons ces opérations en pseudo-code standard.

• CreerPile()

  • Rôle : Crée et retourne une nouvelle pile, initialement vide.
  • Post-condition : La pile existe mais ne contient aucun élément.

• PileVide(p : Pile) : Booleen

  • Rôle : Vérifie si la pile p est vide.
  • Post-condition : Retourne VRAI si p ne contient aucun élément, FAUX sinon.
  • Utilisation : Essentiel avant de tenter de Dépiler ou de lire le Sommet.

• PilePleine(p : Pile) : Booleen

  • Rôle : Vérifie si la pile p a atteint sa capacité maximale. Cette notion est surtout pertinente quand une pile est implémentée avec un tableau de taille fixe.
  • Post-condition : Retourne VRAI si on ne peut plus rien empiler, FAUX sinon.
  • Utilisation : Essentiel avant de tenter d'Empiler.

• Empiler(p : Pile, e : Element)

  • Rôle : Ajoute l'élément e au sommet de la pile p.
  • Pré-condition : La pile p ne doit pas être pleine (PilePleine(p) est FAUX).
  • Post-condition : e est le nouvel élément au sommet de p.

• Dépiler(p : Pile)

  • Rôle : Retire l'élément au sommet de la pile p. Certaines définitions précisent que cette opération retourne aussi l'élément retiré. Pour plus de clarté, nous séparons les rôles.
  • Pré-condition : La pile p ne doit pas être vide (PileVide(p) est FAUX).
  • Post-condition : L'élément qui était au sommet a été enlevé.

• Sommet(p : Pile) : Element

  • Rôle : Retourne la valeur de l'élément au sommet de la pile p, sans le retirer.
  • Pré-condition : La pile p ne doit pas être vide.
  • Post-condition : La valeur du sommet est retournée, mais la pile reste inchangée.

La gestion des erreurs (pré-conditions) est cruciale. Tenter d'empiler sur une pile pleine provoque un débordement (stack overflow), et tenter de dépiler d'une pile vide provoque un débordement négatif (stack underflow).

Le document suivant montre comment gérer ces erreurs dans le pseudo-code des opérations EMPILER et DEPILER.

4. Traçons l'exécution d'une pile

Pour bien assimiler le mécanisme, rien de tel qu'un traçage manuel. Suivons l'état d'une pile à travers une série d'opérations. Nous allons manipuler une pile de nombres entiers.

Séquence d'opérations :

1. CreerPile()
2. Empiler(10)
3. Empiler(25)
4. Sommet()
5. Dépiler()
6. Empiler(40)
7. Dépiler()
8. Dépiler()
9. PileVide()

Ce traçage montre comment la pile grandit et rétrécit, et comment le sommet change constamment, tout en respectant strictement la règle LIFO.

Conclusion

Aujourd'hui, nous avons découvert une structure de données fondamentale, la pile. Son concept est simple mais sa puissance est immense, comme nous le verrons dans les prochaines leçons.

Les points clés à retenir :

• Une pile (stack) est une structure de données basée sur le principe LIFO (Dernier Arrivé, Premier Sorti).
• Toutes les opérations (ajouts, suppressions) se font à une seule extrémité : le sommet.
• Les deux opérations principales sont Empiler (ajouter au sommet) et Dépiler (retirer du sommet).
• D'autres opérations sont essentielles pour une utilisation robuste : CreerPile, PileVide, PilePleine, et Sommet.
• Penser aux cas limites (pile vide ou pleine) est une étape cruciale vers l'écriture d'un algorithme "clean".

Et après ?

Maintenant que nous avons défini ce qu'est une pile et comment elle fonctionne, il est temps de la mettre en pratique. Dans la prochaine leçon, nous verrons notre premier cas d'utilisation concret : nous allons utiliser une pile pour résoudre un problème simple, celui d'inverser une chaîne de caractères. Vous verrez alors à quel point le principe LIFO est élégant pour résoudre ce type de défi.