Algorithmique et Structures de Données

Spécification abstraite

Répertorions les fonctionnalités d’une pile LIFO (Last In First Out) en soulignant les verbes d'actions et les noms, à partir d’une description semi-formalisée :

• C’est un modèle pour toute structure de donnée où l’on accumule des informations les unes après les autres, mais où l’on choisit de n’effectuer un traitement que sur le dernier élément entré. Exemples : pile de dossiers sur un bureau, pile d’assiettes, etc...
• Il est possible dans une telle structure d’ajouter ou de retirer des éléments uniquement au début de la pile.
• L’ordre des éléments est imposé par la pile. Cet ordre est construit non sur la valeur des éléments de la liste, mais sur les places (rangs)de ces éléments dans la liste. Cet ordre n’est pas accessible à l’utilisateur, c’est un élément privé.
• La pile possède une place spéciale dénommée sommet qui identifie son premier élément et contient toujours le dernier élément entré.
• Le nombre d’éléments d’une pile LIFO P est appelé profondeur de la pile. Si la pile est vide nous dirons que sa profondeur est nulle (profondeur = 0 ).
• On doit pouvoir effectuer sur une pile LIFO au minimum (non exhaustif) les actions suivantes : voir si la pile est vide, dépiler un élément, empiler un élément, observer le premier élément sans le prendre, etc...

• C’est une structure de donnée séquentielle dans laquelle les données peuvent être traitées les unes à la suite des autres à partir du sommet.

Spécification opérationnelle concrète

• La Pile est représentée en mémoire dans un tableau.
• Le sommet (noté top) de la pile est un pointeur sur la case du tableau contenant le début de la pile. Les variations du contenu k de top se font au gré des empilements et dépilements.
• Le tableau est plus grand que la pile (il y a donc dans cette interprétation une contrainte sur la longueur, notons Longmax cette valeur maximale de profondeur de la pile).

• L’opérateur empiler : rajoute dans le tableau dans la case pointée par top un élément et top augmente d’une unité.
• L’opérateur depiler : renvoie l’élément pointé par top et diminue top d’une unité.
• L’opérateur premier fournit une copie du sommet pointé par top (la pile reste intacte).
• L’opérateur Est_vide teste si la pile est vide (vrai si elle est vide, faux sinon).