Livre_silo 30 août 2013 16:32 Page 303
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
303
12 – Structure de pile
On choisit d’initialiser les cases avec None, de manière arbitraire, ce qui n’a de toute façon
aucune importance puisque le contenu initial du tableau sera écrasé lors des appels à empiler.
Il ne reste plus qu’à stocker le nombre d’éléments (0 pour une pile vide) dans la case 0 de p
et à renvoyer le tableau.
p[0] = 0
return p
Dépiler un élément
Pour dépiler le sommet d’une pile p, on commence par récupérer son nombre d’éléments n
dans la première case du tableau.
def depiler(p):
n = p[0]
On s’assure que n n’ est pas nul, c’est-à-dire que la pile contient au moins un élément. Si ce
n’ est pas le cas, on fait échouer le programme.
assert n > 0
On laisse donc au programmeur le soin de s’assurer que taille(p) est strictement positif
avant d’appeler depiler(p).
Le sommet de la pile se trouve dans p[n]. Avant de le renvoyer, on prend soin de décrémenter la taille de la pile.
p[0] = n - 1
return p[n]
Empiler un élément
Pour empiler un élément v dans une pile p, on commence par tester s’il y a de la place pour
cela, sachant que la capacité de la pile est égale à len(p)-1.
def empiler(p, v):
n = p[0]
assert n < len(p)-1
Ici, on fait délibérément échouer le programme avec assert si la pile est pleine. Décider
de ne rien faire serait une mauvaise idée : cela obligerait le programmeur à tester systématiquement la taille de la pile avant d’appeler empiler, au risque d’oublier de le faire et de
chercher longtemps son erreur.
Si, en revanche, il y a de la place, alors on incrémente le nombre d’éléments et on stocke v
au (nouveau) sommet de la pile.
n = n + 1
p[0] = n
p[n] = v
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
303
12 – Structure de pile
On choisit d’initialiser les cases avec None, de manière arbitraire, ce qui n’a de toute façon
aucune importance puisque le contenu initial du tableau sera écrasé lors des appels à empiler.
Il ne reste plus qu’à stocker le nombre d’éléments (0 pour une pile vide) dans la case 0 de p
et à renvoyer le tableau.
p[0] = 0
return p
Dépiler un élément
Pour dépiler le sommet d’une pile p, on commence par récupérer son nombre d’éléments n
dans la première case du tableau.
def depiler(p):
n = p[0]
On s’assure que n n’ est pas nul, c’est-à-dire que la pile contient au moins un élément. Si ce
n’ est pas le cas, on fait échouer le programme.
assert n > 0
On laisse donc au programmeur le soin de s’assurer que taille(p) est strictement positif
avant d’appeler depiler(p).
Le sommet de la pile se trouve dans p[n]. Avant de le renvoyer, on prend soin de décrémenter la taille de la pile.
p[0] = n - 1
return p[n]
Empiler un élément
Pour empiler un élément v dans une pile p, on commence par tester s’il y a de la place pour
cela, sachant que la capacité de la pile est égale à len(p)-1.
def empiler(p, v):
n = p[0]
assert n < len(p)-1
Ici, on fait délibérément échouer le programme avec assert si la pile est pleine. Décider
de ne rien faire serait une mauvaise idée : cela obligerait le programmeur à tester systématiquement la taille de la pile avant d’appeler empiler, au risque d’oublier de le faire et de
chercher longtemps son erreur.
Si, en revanche, il y a de la place, alors on incrémente le nombre d’éléments et on stocke v
au (nouveau) sommet de la pile.
n = n + 1
p[0] = n
p[n] = v