Undo/redo and a Python implementation

A very concrete use case: undo/redo

The « undo » feature (Ctrl+Z) in most software relies directly on a stack. Each action you perform is pushed onto a history stack. When you undo, the software pops the last action and cancels it: this is exactly the LIFO behaviour you need, since you always want to undo the most recent action first, never an older one.

Diagram: the undo stack

Actions: type "a", then type "ab", then type "abc"

undo stack:
["a"]
["a", "ab"]
["a", "ab", "abc"]        (displayed state: "abc")

Ctrl+Z (undo) -> pop "abc"
displayed state becomes "ab" again
"abc" is pushed onto a redo stack, just in case

Python implementation using a list

In Python, a list is enough to represent a stack: append plays the role of push, and pop (with no argument) that of pop, since it removes and returns the last element of the list, exactly the top of the stack.

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]

Common pitfall

pop() with no index removes the last element (the top) in constant time: perfect for a stack. But if you mistakenly write pop(0), you remove the first element of the list, which matches the behaviour of a queue, not a stack, and completely breaks the expected LIFO behaviour.