Annuler/refaire et implémentation en Python

Un cas d'usage très concret : annuler/refaire

La fonctionnalité « annuler » (Ctrl+Z) de la plupart des logiciels repose directement sur une pile. Chaque action que tu effectues est empilée dans une pile d'historique. Quand tu annules, le logiciel dépile la dernière action et l'annule : c'est exactement le comportement LIFO qu'il te faut, puisque tu veux toujours annuler l'action la plus récente en premier, jamais une action plus ancienne.

Schéma : pile d'annulation

Actions : taper "a", puis taper "ab", puis taper "abc"

pile d'annulation :
["a"]
["a", "ab"]
["a", "ab", "abc"]        (état affiché : "abc")

Ctrl+Z (annuler) -> depiler "abc"
etat affiche redevient "ab"
"abc" est repousse dans une pile de retablissement (redo), au cas ou

Implémentation en Python avec une liste

En Python, une liste suffit pour représenter une pile : append joue le rôle d'empiler, et pop (sans argument) celui de dépiler, car il retire et renvoie le dernier élément de la liste, exactement le sommet de la pile.

class Pile:
    def __init__(self):
        self.elements = []

    def empiler(self, valeur):
        self.elements.append(valeur)

    def depiler(self):
        if self.est_vide():
            raise IndexError("pile vide")
        return self.elements.pop()

    def sommet(self):
        return self.elements[-1]

    def est_vide(self):
        return len(self.elements) == 0

p = Pile()
p.empiler(3)
p.empiler(7)
p.empiler(9)
print(p.depiler())   # 9
print(p.depiler())   # 7
print(p.elements)    # [3]

Piège classique

pop() sans indice retire le dernier élément (le sommet) en temps constant : c'est parfait pour une pile. Mais si tu écris par erreur pop(0), tu retires le premier élément de la liste, ce qui correspond au comportement d'une file, pas d'une pile, et casse complètement le comportement LIFO attendu.