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

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

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

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

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

Votre note : Aucun(e) Moyenne : 4.7 (10 votes)

Commentaires

Utilisateur non enregistré

Can I Get Cialis Without A Perscription Achat Lioresal Novartis viagra online pharmacy Cialis Mazatlan Mexico