Une pile est un type abstrait particulièrement simple, mais souvent très utile. C'est un conteneur avec un une restriction assez sévère sur l'accès des objets contenus.
L'idée principale de la pile est que les objets sont récupérés à l'ordre inverse par rapport a l'ordre dont ils ont été insérés. Cette restriction permet des implémentations très efficaces.
Les opérations possible sur une file sont :
Si l'interface est fonctionnelle, voici le détail de ces opérations :
Si l'interface est impérative, voici le détail de ces opérations :
arguments | Une pile et un objet quelconque. |
---|---|
valeur de retour | Aucune. |
préconditions | Aucune. |
effets de bord | La pile passée en argument est modifiée de telle façon à ce que le nouvel objet devienne le sommet. |
arguments | Une pile. |
---|---|
valeur de retour | Aucune. |
préconditions | La pile ne doit pas être vide. |
effets de bord | La pile. passée en argument est modifiée de telle façon à ce que le dernier objet empilé et non encore dépilé soit supprimé de la pile. |
arguments | Une pile. |
---|---|
valeur de retour | Le dernier objet empilé qui n'a pas encore été dépilé. |
préconditions | La pile ne doit pas être vide. |
effets de bord | Aucun |
arguments | Une pile. |
---|---|
valeur de retour | Un booléen indiquant si la pile est vide (si elle ne contient aucun objet). |
préconditions | Aucune |
effets de bord | Aucun |
Dans le cas impératif, on préfère parfois combiner les opérations de dépiler un objet et de récupérer l'objet au sommet de la pile en une seule opération. Ceci est également possible dans le cas fonctionnelle si le langage de programmation permet des valeurs multiples d'une opération.
Parfois (surtout dans le cas impératif), on voit une extension de l'opération pour déterminer si la pile est vide. Cette opération devient alors déterminer le nombre d'objets dans la pile.