Structure de Pile
Méthode : Notation des types
Nous noterons Pile[T] une structure de données nommée Pile et dont tous les éléments sont de type T.
Définition : Primitives
Nous avons donc nos quatre premières primitives simples qui vont nous permettre de créer et manipuler notre pile :
creer_pile() -> Pile[T]: crée une pile vide et renvoie cette nouvelle pile.est_vide(Pile[T]) -> bool: renvoie un booléen indiquant si la pile passée en paramètre est vide ou non.empiler(Pile[T], T) -> None: ajoute un élément de type T au sommet de la pile.depiler(Pile[T]) -> T: retire et renvoie l'élément au sommet de la pile.
Nous pouvons remarquer que le type de données T n'est pas passé en paramètre lors de la création de la pile.
Comment faire pour connaître alors ce type T ? Il suffit de regarder le type du premier élément inséré, ce qui permettra de déterminer le type de notre pile.
Remarque : English version
In English, we refer to this as a stack, to which elements can be push() or pop().
Rappel : Primitives et Python
Nous parlons pour l'instant de primitives. Il s'agit donc d'une vue abstraite de nos données. Lorsque l'on codera en Python, la primitive creer_pile() sera en réalité la méthode __init__ d'une classe Pile, et non pas une méthode creer_pile().
De même pour les primitives empiler() et depiler() qui, en Python, ne prennent pas de pile en paramètre, car il s'agit d'une méthode appliquée à un objet : pile.empiler(valeur).
Dans le cours, nous serons emmenés à utiliser les deux versions (version primitive et version classe Python). Ainsi, empiler(pile, valeur) est équivalent à pile.empiler(valeur).
Quelques exemples d'utilisation des piles
Exemple : Historique de navigateur
Au démarrage du navigateur, on charge une pile vide qui va contenir les adresses précédentes.
adresse_courante = ""
adresses_precedentes = creer_pile()
Ensuite, à chaque navigation vers une nouvelle page, le navigateur va empiler l'ancienne page dans la pile, au-dessus des pages précédentes.
def aller_a(adresse_cible):
empiler(adresses_precedentes, adresse_courante)
adresse_courante = adresse_cible
Enfin, lorsqu'un utilisateur clique sur le bouton retour de son navigateur, celui-ci va changer la page actuelle e dépilant l'adresse de la dernière page visitée, c'est-à-dire l'adresse de la page en tête de pile.
def retour():
adresse_courante = depiler(adresses_precedentes)
Exemple : Pile d'appels
Un autre exemple d'utilisation des piles est celui de la pile d'appels.
La pile d’appels est présente tout au long de l’exécution d’un programme, stockant constamment les informations relatives à tous les appels de fonctions imbriqués en cours d’exécution. Comme son nom l’indique, c’est bien une structure de pile.
Lorsqu'une fonction f est en cours d’exécution et qu’elle déclenche un appel à une autre fonction g (ou à elle-même de manière récursive), l’exécution de f est mise en pause jusqu'à ce que le résultat de l’appel à g soit obtenu. L’appel à f ne peut donc se terminer et être retiré de la pile d’appels qu’après la fin de l’appel à g.
En d’autres termes, le premier appel à être retiré de la pile d’appels est le dernier qui y a été ajouté. Cela est dû à la propriété des appels de fonctions qui sont bien imbriqués.