Infoforall

Identification

Infoforall

Résumé 15 - TYPE ABSTRAIT PILE LIFO


Lien vers l'activité : type abstrait Pile LIFO

Dernière modif. : 25 10 2020

1-Type abstrait PILE / STACK : organisation et interface

C'est une séquence ordonnée et finie d'éléments respectant le principe LIFO.

LIFO veut dire Last In First Out. Le dernier élément arrivé sera le premier à repartir.

LIFO

Fonctions d'interface minimale

On retrouve les fonctions de la liste mais limitées à l'action sur le SOMMET. On en trouve des versions mutables ou non mutables. Ici, c'est non mutable puisqu'on renvoie des Piles après chaque modification.

  • nouvellePile() -> Pile
  • estVide(p:Pile) -> bool
  • empiler(elt:Elt, p:Pile) -> Pile  : on rajoute au SOMMET
  • depiler(p:Pile) -> Pile : on supprime le SOMMET
  • lireSommet(p:Pile) -> Elt

2-Implémentations d'une PILE avec Python

Implémentation sous forme d'un tableau ou d'une liste chaînée

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
def nouvellePile() : return [] def estVide(pile) : return pile == [] def empiler(x, pile) : pile.append(x) # rajoute un élément à la fin du tableau def depiler(pile) : if not estVide(pile) : return pile.pop() # supprime et renvoie le dernier élément du tableau def lireSommet(pile) : if not estVide(pile) : return pile[-1] # ou return pile[len(pile)-1]


On peut utiliser un TABLEAU ou une LISTE CHAINEE puisqu'au final une PILE est un peu un cas particulier et limité de la LISTE. On peut utiliser le type natif list si on fait du Python et qu'on ne veut pas tout avoir à refaire. On utiilse alors un tableau dynamique.


Implémentation sous forme de tuple (sommet,queue)

Nous avions vu que le coût en insertion / suppression de la tête était constant pour cette implémentation. Or, une pile est bien une telle liste dont la tête se nomme le sommet.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
class Elt : '''Juste pour pouvoir noter Elt dans les prototypes''' class Pile : '''Juste pour pouvoir noter Pile dans les prototypes''' '''Implémentation de type abstrait Pile en utilisant des tuples (sommet, autre_pile)''' def nouvellePile() -> Pile : '''Renvoie une liste vide''' return () def pileVide(p:Pile) -> bool : '''Renvoie True si la pile est vide''' return p == () def empiler(elt:Elt, p:Pile) -> Pile : '''Renvoie une nouvelle pile où x est le sommet et pile la suite de notre nouvelle pile.''' return (elt, p) def lireSommet(p:Pile) -> Elt : '''Renvoie la valeur stockée au sommet, sans la supprimer de la pile''' if not pileVide(p) : return p[0] def depiler(p:Pile) -> Pile : '''Renvoie une nouvelle pile où on a supprimé l'ancien sommet''' if pileVide(p) : # la liste envoyée est () return nouvellePile() else : return p[1]