Sommaire

Piles

1. Principes de la pile

a. Modèle de données pile

La pile est une liste qui stocke de manière ordonnée les éléments. On peut l’assimiler à une pile d’assiettes : les assiettes à laver sont empilées les unes par-dessus les autres au fur et à mesure de leur arrivée et la personne qui lave les prend en commençant par le haut, ce qui fait que la dernière arrivée est la première lavée. De même, dans une pile informatique les éléments sont ajoutés un par un selon leur ordre d’arrivée et ils sont retirés un par un en partant du dernier arrivé appelé le sommet de la pile :

images/06ri35.PNG

C’est la règle du dernier entré premier sorti : LIFO (Last In First Out).

b. Implémentation statique ou dynamique

Du point de vue de l’implémentation, une pile est une liste simplifiée qui n’accepte que des entrées-sorties en tête de liste. De même que pour les listes, il est possible d’avoir une pile en dynamique réalisée à la demande à l’aide de pointeurs ou une pile en mémoire contiguë réalisée selon une taille définie au départ avec un tableau.

Allocation dynamique de mémoire

Représentation d’une pile en dynamique :

images/06ri36.PNG

Une pile en dynamique n’a pas de taille limite, hormis celle de la mémoire centrale (RAM) disponible.

Allocation contiguë ...