Notebook associé
Le notebook constitue le support principal de cette séance. Il permet de lire les explications, modifier le code et exécuter les cellules pas à pas.
Consultez le mode d’emploi Jupyter.
Le principe d’une pile
Une pile est une structure de données linéaire dans laquelle les éléments sont ajoutés et retirés par une même extrémité : le sommet.
Son fonctionnement est comparable à celui d’une pile d’assiettes : la dernière assiette déposée est généralement la première que l’on retire.
Ce comportement est appelé LIFO — Last In, First Out, c’est-à-dire : « dernier entré, premier sorti ».
Représenter une pile
Le fonctionnement d’une pile peut être représenté de la manière suivante.
Si les éléments A, B puis
C sont successivement empilés,
C se trouve au sommet.
Le prochain élément dépilé sera donc C,
puis B, puis A.
Les opérations fondamentales
Pour manipuler une pile, on dispose généralement d’un petit nombre d’opérations.
- Créer une pile vide.
- Empiler un élément : ajouter un élément au sommet de la pile.
- Dépiler : retirer l’élément situé au sommet.
- Consulter le sommet sans retirer l’élément.
- Tester si la pile est vide.
Ces opérations décrivent ce que l’on peut faire avec une pile, sans préciser encore comment les éléments sont effectivement représentés dans un programme.
Interface et implémentation
Les opérations empiler, dépiler, consulter le sommet et tester si la pile est vide définissent l’interface de la pile.
Elles indiquent les services que la structure doit fournir.
En revanche, elles ne précisent pas comment les éléments sont réellement organisés dans la mémoire de l’ordinateur.
La manière choisie pour représenter la pile et réaliser ces opérations constitue son implémentation.
Une même structure de pile peut donc être réalisée de plusieurs façons différentes, tout en conservant le même comportement LIFO.
Quelques usages des piles
Les piles apparaissent dans de nombreuses situations informatiques.
- la gestion des appels de fonctions ;
- les mécanismes d’annulation d’actions ;
- la navigation dans certains historiques ;
- l’analyse d’expressions ;
- le parcours de certaines structures de données ;
- certains algorithmes de recherche.
Dans chacune de ces situations, l’ordre dernier entré, premier sorti joue un rôle essentiel.
À retenir
- Une pile est une structure de données LIFO : dernier entré, premier sorti.
- Les ajouts et les retraits s’effectuent au sommet de la pile.
- Les opérations fondamentales sont : créer une pile, empiler, dépiler, consulter le sommet et tester si la pile est vide.
- Ces opérations constituent l’interface de la pile.
- L’implémentation décrit la manière dont cette interface est effectivement réalisée.
- Une même pile peut avoir plusieurs implémentations tout en conservant le même comportement LIFO.