Les piles

Définition

Comme la file d'attente, la pile constitue aussi l'un des concepts les plus utilisés dans la science des ordinateurs.

Une pile peut être définie comme une collection d'éléments dans laquelle tout nouveau élément est inséré à la fin et tout élément ne peut être supprimé que de la fin.

C'est le principe "LIFO", abréviation de "Last In First Out" qui veut dire " dernier entré premier servi ".

La pile est très utilisée dans le domaine de la compilation : résolution de la portée des objets, récursivité, évaluation d'expressions, etc.

La pile est aussi utilisée pour le parcours des arbres et pour résoudre un grand nombre de problèmes.

Modèle

On définit une machine abstraite sur les piles avec l'ensemble des opérations suivantes :

CreerPile(P),EmPiler(P,Val),DePiler(P,Val),PileVide(P), PilePleine(P) définies comme suit:

CreerPile(P) : créer une pile vide.

EmPiler(P,Val) : ajouter Val en sommet de pile.

DéPiler(P,Val) : retirer dans Val l'élément en sommet de pile.

PileVide((P) : tester si la pile est vide.

PilePleine(P) : tester si la pile est pleine.

Implémentation

De la même manière, une pile peut être représentée en mémoire soit dans un tableau, soit dans une liste linéaire chaînée.