Au coeur de la science !
Vous êtes libre de partager, reproduire, imprimer, distribuer et communiquer cet article, à condition de ne pas le vendre et d'en citer la source.
URL source: http://axiomcafe.fr/les-piles

Les piles

sam, 15/05/2010 - 16:49 par Dom [1]
Type:
  • Article spécialisé [2]
Sujet:
  • Programmation [3]
  • |
  • Informatique [4]

Les piles

Définition

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

  1. Structure De Pile:
  2. - tableau d'Element
  3. - tailleMax
  4. - sommet
  5. Fin de structure

Structure LIFO pour une Pile en C      (cliquer pour ouvrir)

  1. typedef struct pile {
  2. pElement * pTabElements; // tableau des pointeurs pElement
  3. int iTailleMax; // la taille maximale de la Pile
  4. int iSommet; // index du sommet, -1 si Pile vide
  5. } 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 :

  1. Fonction PileVide (Pile P):
  2. Si sommet[P] = -1 alors
  3. retourner VRAI
  4. Sinon
  5. retourner FAUX
  6. FinSi
  7. FinFonction

Implémentation en C de la primitive 'PileVide'    (cliquer pour ouvrir)

  1. int PileVide (Pile* p)
  2. {
  3. if (p->iSommet == -1) // Si le sommet vaut -1:
  4. return 1; // SUCCCES: pile vide
  5. else // Sinon
  6. return 0; // ECHEC
  7. }

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 :

  1. Fonction NbreElement (Pile P):
  2. retourner sommet[P]+1
  3. FinFonction

Implémentation en C de la primitive 'NbreElement' (cliquer pour ouvrir)

  1. int NbreElement (Pile* p)
  2. {
  3. return (p->iSommet + 1); // taille = sommet + 1
  4. }

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 :

  1. Fonction Empiler(Pile P, Element NouvElement):
  2. Si sommet[P] < tailleMax[P] alors
  3. # Ajout du nouvel élément #
  4. # au sommet de la pile #
  5. pile[sommet[P]] = nouvElement
  6. incrémente sommet[P]
  7. Sinon
  8. Afficher "Pile pleine"
  9. FinSi
  10. FinFonction

Implémentation en C de la primitive 'Empiler'    (cliquer pour ouvrir)

  1. int Empiler (Pile* p, Element* pNouvElement)
  2. {
  3. if (NbreElement(p) < p->iTailleMax) // Si la pile est pleine
  4. return 0; // ECHEC (cause: pile pleine)
  5.  
  6. if(p->sommet == -1) // Si la pile est vide
  7. p->sommet = 0; // Hauteur du sommet = 0
  8.  
  9. p->iSommet = (p->iSommet+1)%p->iTailleMax; // Décalage du sommet de pile
  10. p->pTabElements[p->iSommet] = pNouvElement; // Ajout du nouvel élément au somme
  11. return 1; // SUCCES
  12. }

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 :

  1. Fonction Depiler (Pile P): Element:
  2. Si (P non vide) alors
  3. element = pile[sommet[P]]
  4. décrémente sommet[P]
  5. Sinon
  6. Afficher "Pile vide"
  7. FinSi
  8. Retourner element
  9. FinFonction

Implémentation en C de la primitive 'Depiler' (cliquer pour ouvrir)

  1. Element* Depiler (Pile* p)
  2. {
  3. if (PileVide(p)) // Si la pile est vide:
  4. return NULL; // ECHEC (cause: pile vide)
  5.  
  6. Element* pElement;
  7. pElement = p->pTabElement[p->iSommet]]; // Récupération de l'élément
  8. if (p->iSommet == 0) // S'il s'agissait du dernier élément:
  9. p->iSommet = -1; // Indiquer que la pile est vide
  10. else // sinon:
  11. p->iSommet = (p->iSommet-1)%p->iTailleMax; // Décalage du sommet de pile
  12. return element; // Renvoit de l'élément dépilé
  13. }

Signaler un bug ou une erreur

Si vous apercevez un bug ou souhaitez voir une addition sur la page courante, n'hésitez pas à nous envoyer un message.
Si vous souhaitez une réponse, merci d'indiquer également votre adresse mail.

Envoyer [5]

Liens:
[1] http://axiomcafe.fr/dom
[2] http://axiomcafe.fr/term/article-specialise
[3] http://axiomcafe.fr/term/programmation
[4] http://axiomcafe.fr/term/informatique
[5] http://axiomcafe.fr/les-piles


AxiomCafe, au coeur de la science: site de vulgarisation scientifique concis, clair et amusant !
Pour toute information, contacter : admin@axiomcafe.fr