Livre_silo 30 août 2013 16:32 Page 305
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
305
12 – Structure de pile
Étant donné un tableau p de taille n, on peut lui ajouter un (n+1)-ième élément v à droite
avec p.append(v). Inversement, on peut récupérer le n-ième élément de p et le supprimer
avec p.pop(), le tableau p prenant alors la taille n − 1. De manière évidente, ces deux opérations correspondent exactement à empiler(p, v) et depiler(p). Le programme 12 ci-dessous
contient une réalisation de piles non bornées à l’aide de ces deux opérations.
PROGRAMME 12 Piles non bornées
Cette réalisation exploite les méthodes append et pop des tableaux de Python. On note que
l’argument c de creer_pile n’est pas utilisé (mais conservé afin de garder la même interface).
def creer_pile(c):
return []
def depiler(p):
assert len(p) > 0
return p.pop()
def empiler(p, v):
p.append(v)
def sommet(p):
assert len(p) > 0
return p[-1]
def taille(p):
return len(p)
def est_vide(p):
return taille(p) == 0
POUR ALLER PLUS LOIN Tableaux redimensionnables et complexité amortie
Les tableaux de Python sont en réalité des tableaux redimensionnables, c’est-à-dire des
tableaux dont la taille peut varier avec le temps. C’est ce qui permet notamment de fournir
les opérations append et pop. Le principe d’un tableau redimensionnable est en réalité très
proche de celui des piles bornées : on utilise un tableau plus grand, à l’intérieur duquel
seuls certains des éléments sont significatifs. Lorsqu’il s’agit d’augmenter la taille, disons
d’une unité, deux cas se présentent : soit il reste de la place et dans ce cas il n’y a rien
à faire (si ce n’est se souvenir de la nouvelle taille), soit il ne reste plus de place et on
alloue un nouveau tableau, deux fois plus grand, dans lequel les éléments sont recopiés et
qui prend la place de l’ancien tableau. (Pour pouvoir remplacer un tableau par un autre,
de manière transparente, il suffit de créer une indirection, c’est-à-dire un tableau — de
taille 1 — contenant un tableau.)
Si on choisit d’allouer un nouveau tableau deux fois plus grand, et non pas seulement plus
grand d’une unité, c’est pour des raisons de performances. En effet, chaque déplacement
des éléments d’un tableau vers un autre a un coût proportionnel au nombre d’éléments.
Allouer successivement un tableau de taille 1, puis 2... puis n aurait un coût total quadratique, alors qu’allouer un tableau de taille 1, puis 2, puis 4... puis 2 k a un coût total de
l’ordre de 2 k+1 , c’est-à-dire proportionnel à la taille finale du tableau.
¯
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
305
12 – Structure de pile
Étant donné un tableau p de taille n, on peut lui ajouter un (n+1)-ième élément v à droite
avec p.append(v). Inversement, on peut récupérer le n-ième élément de p et le supprimer
avec p.pop(), le tableau p prenant alors la taille n − 1. De manière évidente, ces deux opérations correspondent exactement à empiler(p, v) et depiler(p). Le programme 12 ci-dessous
contient une réalisation de piles non bornées à l’aide de ces deux opérations.
PROGRAMME 12 Piles non bornées
Cette réalisation exploite les méthodes append et pop des tableaux de Python. On note que
l’argument c de creer_pile n’est pas utilisé (mais conservé afin de garder la même interface).
def creer_pile(c):
return []
def depiler(p):
assert len(p) > 0
return p.pop()
def empiler(p, v):
p.append(v)
def sommet(p):
assert len(p) > 0
return p[-1]
def taille(p):
return len(p)
def est_vide(p):
return taille(p) == 0
POUR ALLER PLUS LOIN Tableaux redimensionnables et complexité amortie
Les tableaux de Python sont en réalité des tableaux redimensionnables, c’est-à-dire des
tableaux dont la taille peut varier avec le temps. C’est ce qui permet notamment de fournir
les opérations append et pop. Le principe d’un tableau redimensionnable est en réalité très
proche de celui des piles bornées : on utilise un tableau plus grand, à l’intérieur duquel
seuls certains des éléments sont significatifs. Lorsqu’il s’agit d’augmenter la taille, disons
d’une unité, deux cas se présentent : soit il reste de la place et dans ce cas il n’y a rien
à faire (si ce n’est se souvenir de la nouvelle taille), soit il ne reste plus de place et on
alloue un nouveau tableau, deux fois plus grand, dans lequel les éléments sont recopiés et
qui prend la place de l’ancien tableau. (Pour pouvoir remplacer un tableau par un autre,
de manière transparente, il suffit de créer une indirection, c’est-à-dire un tableau — de
taille 1 — contenant un tableau.)
Si on choisit d’allouer un nouveau tableau deux fois plus grand, et non pas seulement plus
grand d’une unité, c’est pour des raisons de performances. En effet, chaque déplacement
des éléments d’un tableau vers un autre a un coût proportionnel au nombre d’éléments.
Allouer successivement un tableau de taille 1, puis 2... puis n aurait un coût total quadratique, alors qu’allouer un tableau de taille 1, puis 2, puis 4... puis 2 k a un coût total de
l’ordre de 2 k+1 , c’est-à-dire proportionnel à la taille finale du tableau.
¯