Les Piles

Un type abstrait de données (ou TAD) est défini par son interface (comment on s'en sert) plutôt que par son implémentation (comment il fonctionne, comment il a été programmé).

Un TAD est théorique et indépendant des langages de programmation.

Définition

Une pile (aussi appelée « stack » ou « LIFO » pour last in, first out) est un type abstrait de données dans lequel un seul élément est accessible à la fois : le sommet de la pile.

Interface d'une pile

Une interface possible de pile (en programmation impérative) est :

Méthode/Opérations	Description
P = Pile()	Initialisation d'une pile vide.
est_vide(P)	Renvoie True si la pile P est vide, False sinon.
empiler(P, elt)	Empile un nouvel élément au sommet de la pile.
depiler(P)	Lorsque la pile n'est pas vide, supprime le sommet de la pile et renvoie la valeur de ce sommet.

Remarque

Dans certains cas, l'interface propose deux opérations pour le dépilement :

• une opération pour renvoyer la valeur du sommet (sans dépiler) ;
• une opération pour supprimer le sommet (dépiler) sans renvoyer sa valeur.