Piles

Une pile est une sorte de liste mais pour laquelle on s'intéresse surtout à la façon de faire entrer et sortir les données.

On pourra adopter la même notation que pour les listes. Par exemple, 3:85:17:9 est une pile dans laquelle on a ajouté, dans l'ordre, 3, 85, 17 et 9.

LIFO

Il faut penser à une pile d'assiettes.

Quand on ajoute une assiette, on la met forcément sur le dessus.
Quand on retire une assiette, on retire forcément celle du dessus.

Donc, quand on retire un élément, c'est toujours le dernier à avoir été ajouté.

On parle de LIFO = Last In First Out, c'est à dire Dernier entré, premier sorti.

Retenez bien : Dans 3:85:17:9, 9 est le dernier inséré, c'est donc le dessus de la pile.

Interface

Méthode	Description
CREER_PILE_VIDE()	Renvoie une pile de contenu vide
EST_VIDE(P)	Renvoie vrai si la pile est vide
EMPILER(P, e)	Ajoute l'élément e sur le dessus de la pile
DEPILER(P)	Enlève l'élément sur le dessus de la pile et le renvoie précondition : pile non vide

Taille maximale ?

Pour une pile c'est surtout le mode d'empilement et de dépilement qui importe. Il n'est pas indispensable que la taille de la pile puisse augmenter indéfiniment comme dans une Liste. Il est donc courant de créer une pile en prévoyant un espace mémoire maximal, si bien qu'il peut arriver que la pile soit pleine.

Dans ce cas, on a dans l'interface :

Méthode	Description
CREER_PILE_VIDE(taille)	Renvoie une pile de contenu vide avec une taille max spécifiée
EST_PLEINE(P)	Renvoie vrai si la pile est pleine
EMPILER(P, e)	Ajoute l'élément e sur le dessus de la pile précondition : pile non pleine

Exercices

Exercice 1

Donner la pile P obtenue après exécution des lignes suivantes (dans les deux cas) :

P = CREER_PILE_VIDE()
EMPILER(P, 'X')
EMPILER(P, 'B')
EMPILER(P, 'E')
DEPILER(P)
EMPILER(P, 'Y')

Q = CREER_PILE_VIDE()
EMPILER(Q, 51)
EMPILER(Q, 3)
P = CREER_PILE_VIDE()
EMPILER(P, DEPILER(Q))
EMPILER(P, 17)
EMPILER(P, DEPILER(Q))

Exercice 2

On veut connaître le nombre d'éléments contenu dans une pile en n'utilisant que les fonctions disponibles dans l'interface.

L'astuce est, pour une pile P donnée, de la dépiler, constituant ainsi une nouvelle pile Q, en comptant les éléments. Il faut penser ensuite à reformer la pile P en remettant le contenu de Q dans P.

Écrire une fonction hauteur_pile(P) qui renvoie le nombre d'éléments de P.

Écrivez la fonction en syntaxe Python.