Structure de pile

Pour découvrir le concept, voir ce jeu sérieux.

La plus vieille mention de pile connue est d'Alan Turing dans un rapport technique sur l'ordinateur ACE. La mémoire de cette machine était formée de registres de 32 bits chacun, nommés TS1 à TS32. C'est le registre TS31 qui servait à implémenter la pile des appels. La pile doit, selon Turing, permettre ces deux instructions :

BURY (General Description): The content of TS1 with 1 added is 
transferred to the position indicated in TS31, and 1 is added to the 
reference in TS31. We then proceed to carry out the instruction in 
TS1.

UNBURY (General Description): The minor cycle whose position is given 
in TS31 is taken to be the position of the next instruction.

On utilisera ces traductions :

Turing	Forth	en français	Python
`Bury`	`push`	empiler	`append`
`Unbury`	`pop`	dépiler	`pop`

I/ Définition

1) LIFO

Une pile est une liste ne pouvant être parcourue itérativement, et dont les ajouts et suppressions ne se font que d'un côté. L'acronyme LIFO voulant dire « Last In, First Out ».

2) Interface

Une pile est donc caractérisée par les méthodes

de création de la pile (__init__)
d'ajout d'un élément au sommet de la pile ( empiler ou append)
de retrait de l'élément au sommet de la pile ( dernier ou pop)
de test de vacuité (est_vide)

On rappelle que l'interface des listes possède déjà tout ça (à part la dernière méthode) :

class Liste():
	def __init__(self,L):
		self.contenu = L
	def dernier(self):
		pass
	def empiler(self,elt):
		pass
	def premier(self):
		pass
	def pousser(self,elt):
		pass
	def __iter__(self):
		pass
	def __repr__(self):
		return str(self.contenu)

3) Classe

Alors on en extrait l'interface des piles :

class Pile(Liste):
    def est_vide(self):
        return len(self.contenu)==0
    def dernier(self):
        return self.contenu.pop()
    def empiler(self,elt):
        self.contenu.append(elt)

On constate par des messages d'erreur que l'objet Pile ne peut être itéré et qu'on ne peut accéder à un de ses élements (autre que le dernier, par les méthodes dernier et empiler). Par contre on peut dépiler l'un après l'autre les éléments, ce qui les fait apparaître « à l'envers » :

p = Pile(list('PILE'))
while not p.est_vide():
    print(p.dernier())

E
L
I
P

En machine, une pile est une liste assortie d'un pointeur vers son sommet :

II/ Exemples

1) La tour d'Hanoï (Édouard Lucas, 1880)

Le but du jeu est de déplacer les 3 disques du premier piquet vers le second piquet en s'arrangeant pour que les piles soient toujours triées dans l'ordre décroissant :

Chacun des 3 piquets est une pile, à ceci près que l'empilement est interdit si l'objet à empiler est plus grand que le sommet de la pile. On redéfinit alors la méthode d'empilement, en levant une exception si l'empilement est interdit :

class Clou(Pile):
    def empiler(self,elt):
        if self.est_vide() or self.contenu[-1]>elt:
            self.contenu.append(elt)
        else:
            raise Exception("Tricheur !")

La position initiale du jeu s'obtient par

piquet1 = Clou([3,2,1])
piquet2 = Clou([])
piquet3 = Clou([])

et la solution est

piquet2.empiler(piquet1.dernier())
piquet3.empiler(piquet1.dernier())
piquet3.empiler(piquet2.dernier())
piquet2.empiler(piquet1.dernier())
piquet1.empiler(piquet3.dernier())
piquet2.empiler(piquet3.dernier())
piquet2.empiler(piquet1.dernier())

2) Parcours en profondeur

Pour parcourir un graphe en profondeur, on utilise une pile. C'est le cas, en particulier, pour chercher la sortie d'un labyrinthe. C'est le cas également pour vérifier la syntaxe d'un document html. Mais aussi pour évaluer une expression donnée sous forme suffixe :

3) Notation polonaise inverse

On veut évaluer cette expression, sachant que x==8 :

En notation suffixe, l'expression est x 5 - 2 x * 3 + *. et pour l'évaluer on la lit de gauche à droite, à l'aide d'une pile qu'on utilise de la manière suivante :

Chaque fois qu'on a un nombre ou une variable, on l'empile.
Chaque fois qu'on obtient une opération,
- on dépile les deux nombres qui sont au sommet de la pile,
- on applique l'opération à ces deux nombres,
- puis on empile le résultat de cette opération.

def rpn(L):
    pile = []
    for e in L:
        if e in '+-*/':
            a = pile.pop()
            b = pile.pop()
            pile.append(str(eval(b+e+a)))
        else:
            pile.append(str(eval(e)))
    return pile

Au cours de l'évaluation de l'expression les états de la pile sont les suivants :

[]
['8']
['8', '5']
['3']
['3', '2']
['3', '2', '8']
['3', '16']
['3', '16', '3']
['3', '19']
['57']

4) Appels de fonctions

La machine virtuelle qui exécute le code Python compilé, utilise une pile pour stocker les appels de fonction. C'est ce qui permet la récursivité.