Séquence 1 – Notion de Pile
Une pile est une structure abstraite et linéaire de données dans laquelle on peut ajouter ou enlever des éléments un par un, mais toujours par la même extrémité, comme pour une pile d’assiettes : on met ou on enlève toujours par le dessus.
Cette extrémité est appelée « sommet de la pile ».
La hauteur d’une Pile correspond au nombre d’éléments empilés.
Une Pile fonctionne sur le principe LIFO (Last In First Out).
Des exemples d’utilisation de Piles en informatique
Une pile pour gérer les appels de fonctions.
Si une fonction1 appelle une autre fonction2, le contenu de fonction2 est empilé par-dessus celui de fonction1. Lorsque fonction2 revoie un résultat à fonction1, elle est dépilée.
L’utilisation d’une pile dans ce cas est assez évidente puisque l’on n’a pas besoin de fonction1 tant que l’on en a pas fini avec fonction2.
Par déduction, la programmation par récursivité (fonction qui s’appelle elle-même) est une pile d’appels que l’on dépile lorsque l’on est arrivé au plus profond de la récursivité.
(Visualisation possible dans PythonTutor)
D’autres exemples
- conservation des pages visitées dans un navigateur web dans une Pile, avec possibilité de revenir sur une page précédente en cliquant sur une flèche « précédente »
- conservation des actions réalisées dans une logiciel de traitement de texte, de création graphique de retouche d’images, etc., ce qui permet d’annuler ces actions notamment grâce au raccourci clavier « ctrl+Z » (dans © MS-Windows)
Interface d’une Pile : fonctions primitives
L’interface d’une structure abstraite « Pile » comprend les fonctions primitives suivantes :
- un constructeur, qui permet de créer une Pile ;
- des observateurs qui permettent de connaître l’état de la Pile : la pile est-elle vide ? Quelle est la hauteur de la Pile ? Quelle est la valeur au sommet de la Pile ?
- des transformateurs qui permettent d’ajouter une donnée au sommet de la Pile : « empiler », de retirer la donnée se trouvant au sommet de la Pile : « dépiler ».