Définition
Pile:
En informatique, une pile (en anglais "stack") est une structure de données de type LIFO (anglais pour Last In, First Out), c'est à dire fonctionnant sur le principe « dernier arrivé, premier sorti » . Les derniers éléments ajoutés à la pile seront les premiers à être récupérés.
La manière la plus simple de comprendre le fonctionnement d'une pile est d'imaginer une pile d'assiettes ou de dossiers. En l'attente de traitement, les dossiers sont empilés. Cette structure se comporte alors de sorte à ce que le dernier dossier placé dans la pile soit le premier traité. On l'appelle alors structure LIFO ou Last In First Out , c'est à dire 'dernier entré, premier sorti'.
Il peut être déduit de cet exemple qu'une personne traitant cette pile de dossier aura besoin de quatre primitives ou fonctions de service associées à une structure de type pile:
- empiler (en anglais push ): ajouter un élément à la pile
- dépiler (en anglais po p ): enlever un élément de la pile
- la pile est-elle vide?
- combien y'a-t-il d'éléments dans la pile?
Structure d'une pile
Une pile est représentée en mémoire par une structure de donnée contenant un tableau dont les éléments sont du type souhaité. Le comportement de pile LIFO est obtenu par l'ajout de l'indice sommet représentation la position dans le tableau du sommet de la pile. A cet indice, est ajouté tailleMax , la taille maximale de la pile.
Par convention, l'indice du sommet d'une pile vide est -1.
Structure de Pile en Pseudo-Code :
Structure De Pile:
- tableau d'Element
- tailleMax
- sommet
Fin de structure
Structure LIFO pour une Pile en C (cliquer pour ouvrir)
typedef struct pile {
pElement * pTabElements; // tableau des pointeurs pElement
int iTailleMax; // la taille maximale de la Pile
int iSommet; // index du sommet, -1 si Pile vide
} Pile;
Primitives
La pile est-elle vide ?
Nous avons rappelé en présentation de la structure de pile que la convention voulait que le sommet d'une pile vide ait pour indice -1. C'est donc ce qu'il suffit de vérifier pour savoir si la pile est vide.
Primitive 'PileVide' en Pseudo-Code :
Fonction PileVide (Pile P):
Si sommet[P] = -1 alors
retourner VRAI
Sinon
retourner FAUX
FinSi
FinFonction
Implémentation en C de la primitive 'PileVide' (cliquer pour ouvrir)
int PileVide ( Pile* p)
{
if ( p-> iSommet == - 1 ) // Si le sommet vaut -1:
return 1 ; // SUCCCES: pile vide
else // Sinon
return 0 ; // ECHEC
}
Nombre d'éléments de la pile
Le nombre d'éléments d'une pile est tout simplement la hauteur du sommet de cette pile. Petit bémol toutefois: en informatique, un tableau commence à l'indice 0: il faut donc rajouter +1 à la hauteur du sommet pour obtenir le nombre d'éléments de la pile.
Primitive 'NbreElement' en Pseudo-Code :
Fonction NbreElement (Pile P):
retourner sommet[P]+1
FinFonction
Implémentation en C de la primitive 'NbreElement' (cliquer pour ouvrir)
int NbreElement ( Pile* p)
{
return ( p-> iSommet + 1 ) ; // taille = sommet + 1
}
Enpilage
Empiler un élément dans une pile revient simplement à l'ajouter au sommet de celle-ci. Une simple vérification toutefois: il ne faut pas que la pile soit pleine !
Primitive 'Empiler' en Pseudo-Code :
Fonction Empiler(Pile P, Element NouvElement):
Si sommet[P] < tailleMax[P] alors
# Ajout du nouvel élément #
# au sommet de la pile #
pile[sommet[P]] = nouvElement
incrémente sommet[P]
Sinon
Afficher "Pile pleine"
FinSi
FinFonction
Implémentation en C de la primitive 'Empiler' (cliquer pour ouvrir)
int Empiler ( Pile* p, Element* pNouvElement)
{
if ( NbreElement( p) < p-> iTailleMax) // Si la pile est pleine
return 0 ; // ECHEC (cause: pile pleine)
if ( p-> sommet == - 1 ) // Si la pile est vide
p-> sommet = 0 ; // Hauteur du sommet = 0
p-> iSommet = ( p-> iSommet+ 1 ) % p-> iTailleMax; // Décalage du sommet de pile
p-> pTabElements[ p-> iSommet] = pNouvElement; // Ajout du nouvel élément au somme
return 1 ; // SUCCES
}
Dépilage
Le dépilage consiste tout simplement à enlever le premier élément au sommet de la pile, à condition bien-sûr que celle-ci ne soit pas vide !
Primitive 'Dépiler' en Pseudo-Code :
Fonction Depiler (Pile P): Element:
Si (P non vide) alors
element = pile[sommet[P]]
décrémente sommet[P]
Sinon
Afficher "Pile vide"
FinSi
Retourner element
FinFonction
Implémentation en C de la primitive 'Depiler' (cliquer pour ouvrir)
Element* Depiler ( Pile* p)
{
if ( PileVide( p) ) // Si la pile est vide:
return NULL; // ECHEC (cause: pile vide)
Element* pElement;
pElement = p-> pTabElement[ p-> iSommet] ] ; // Récupération de l'élément
if ( p-> iSommet == 0 ) // S'il s'agissait du dernier élément:
p-> iSommet = - 1 ; // Indiquer que la pile est vide
else // sinon:
p-> iSommet = ( p-> iSommet- 1 ) % p-> iTailleMax; // Décalage du sommet de pile
return element; // Renvoit de l'élément dépilé
}
Imprimer
Envoyer
Bug ou erreur ?