Livre_silo 30 août 2013 16:32 Page 304
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
304
Informatique pour tous
Le code complet est donné programme 11 ci-après. Il contient également les opérations
taille, est_vide et sommet.
PROGRAMME 11 Piles à capacité finie
Le premier élément du tableau contient le nombre d’éléments n de la pile. Les cases d’indices 1 à n du tableau contiennent alors les éléments de la pile, le sommet de la pile se
trouvant à l’indice n.
def creer_pile(c):
p = (c + 1) * [None]
p[0] = 0
return p
def depiler(p):
n = p[0]
assert n > 0
p[0] = n - 1
return p[n]
def empiler(p, v):
n = p[0]
assert n < len(p)-1
n = n + 1
p[0] = n
p[n] = v
def taille(p):
return p[0]
def est_vide(p):
return taille(p) == 0
def sommet(p):
assert taille(p) > 0
return p[p[0]]
12.2.2 Piles non bornées
Un défaut de la structure de pile précédente est sa capacité bornée. En particulier, il faut
être capable de déterminer une borne maximale sur le nombre d’éléments, ce qui n’est pas
toujours possible.
On présente ici une seconde structure de piles, sans limite de taille. Elle exploite une propriété des tableaux de Python qu’ on n’a pas encore utilisée, à savoir la possibilité d’ajouter
ou de supprimer des éléments à l’extrémité droite d’un tableau en temps constant ¹.
1. Il s’agit en fait de temps constant amorti ; voir plus loin l’encadré à ce propos.