TNSI : Cours sur les Piles

Qu'est-ce qu'une Pile ?

Une Pile , ou Stack est une collection d'objets, ayant des opérations basées sur la structure LIFO (Last In, First Out) / Dernier Arrivé, Premier Sorti . Dans une pile, les ajouts et suppressions n'ont lieu que sur une même extremité : le Sommet de la Pile.

Définition

Def

Une Pile / Stack / LIFO (Last In First Out ou Dernier Arrivé Premier Sorti ) est une une Structure de Données, donc une collection d'objets implémentant les opérations/primitives suivantes:

• savoir la pile est vide: est_vide ou is_empty
• empiler / push un nouvel élément au sommet de la pile, en temps constant : empiler ou push
• dépiler / pop l'élément courant au sommet de la pile, en temps constant : depiler ou pop Parfois, on peut trouver deux opérations distinctes:
  • une opération pour (seulement) renvoyer le sommet de la pile, sans le supprimer
  • une opération pour le supprimer
• Sommet renvoie la valeur du Sommet

Exp

• Pile d'assiettes: c'est en haut de la pile qu'il faut prendre ou ajouter des assiettes.
• Pile de Livres: idem. etc..

Principales Utilisations

Traitement des appels de fonctions

gestion des adresses de retour, nécessaire dans le cas de fonctions récursives…

Évaluation d'expressions arithmétiques

les algorithmes utilisent la structure de Pile

Spécification

Préconditions

• dépiler est défini \(\Leftrightarrow\) est_vide=Faux
• Sommet est définie \(\Leftrightarrow\) est_vide=Faux

Axiomes

Une Pile dispose des axiomes suivants:

• est_vide(Pile_vide) = Vrai
• est_vide(empiler(Pile p,Element e)) = Faux
• dépiler(empiler(Pile p, Element e)) = p
• Sommet(empiler(Pile p, Element e)) = e

Implémentations

Avec un Tableau Dynamique (avec le type list de Python)

Avec le module collections.deque