Structure de pile
Étape 1 : Concevoir le cahier des charges (TAD)
Une pile est un type abstrait de données contenant un ensemble d'éléments, dont l'élément ajouté en dernier est accessible.
Nous nommons notre structure de pile avec le nom Pile[T] dont tous ces éléments sont de type T.
Les Primitives
Nous avons donc nos quatre premières primitives qui vont nous permettre de créer et manipuler notre pile :
creer_file(): Pile[T] : crée une pile vide et renvoie cette nouvelle pile.estVide(): Pile[T] -> Booléen : renvoie un booléen indiquant si la pile passée en paramètre est vide ou non.empiler(): Pile[T], T -> Pile[T] : ajoute un élément de type T au sommet de la pile.depiler(): Pile[T] -> 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.
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).
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 en 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)
Étape 2 : Proposer une implémentation
À vous de le découvrir !