Les piles

Définition

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'.

Schéma d'équivalence d'une structure LIFO et d'une pile de dossier

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 pop): 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é
}