Livre_silo 30 août 2013 16:32 Page 302
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
302
Informatique pour tous
3 La seule chose qui compte est la valeur totale des pièces ; leur valeur individuelle ou l’ordre dans lequel
on les ramasse et dépense n’a pas d’importance. Il suffit ici d’un entier pour garder trace de la somme
dont on dispose.
4 Si on utilise une pile, on traitera toujours en premier le dernier dossier arrivé et on risque de faire attendre
longtemps les dossiers situés au bas de la pile. Pour bien faire, il faut ici tenir compte des priorités des
différents dossiers, ce qui demande de les ranger dans un tableau ordonné.
12.2 Réalisation d’une structure de pile
12.2.1 Piles à capacité finie
La manière la plus simple de réaliser une pile consiste à utiliser un tableau de taille N ,
avec N suffisamment grand, c’est-à-dire au moins égal au nombre maximal d’éléments qui
seront stockés dans la pile. Les éléments sont rangés dans l’ordre où ils ont été empilés.
Pour pouvoir empiler et dépiler, il faut connaître la position du sommet de la pile dans le
tableau. Pour cela, le plus simple est de stocker le nombre d’éléments n de la pile dans la
case 0 du tableau, puis les n éléments de la pile dans les cases 1 à n. On a donc la structure
suivante :
0 1
. . .
n
N
n
éléments
place disponible
0 1 2 3
. . .
p = creer_pile(10)
0
. . .
empiler(p, A)
1 A
. . .
empiler(p, B)
2 A B
. . .
empiler(p, C)
3 A B C
. . .
depiler(p)
2 A B C
. . .
Les éléments colorés sont ceux qui sont réellement dans la pile. Les autres, par exemple
C à la dernière ligne, ne sont plus accessibles et seront écrasés lorsqu’on en empilera de
nouveaux.
Création d’une nouvelle pile
Pour créer une nouvelle pile de capacité c, on commence par allouer un tableau p de
c+1 cases.
def creer_pile(c):
p = (c + 1) * [None]
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
302
Informatique pour tous
3 La seule chose qui compte est la valeur totale des pièces ; leur valeur individuelle ou l’ordre dans lequel
on les ramasse et dépense n’a pas d’importance. Il suffit ici d’un entier pour garder trace de la somme
dont on dispose.
4 Si on utilise une pile, on traitera toujours en premier le dernier dossier arrivé et on risque de faire attendre
longtemps les dossiers situés au bas de la pile. Pour bien faire, il faut ici tenir compte des priorités des
différents dossiers, ce qui demande de les ranger dans un tableau ordonné.
12.2 Réalisation d’une structure de pile
12.2.1 Piles à capacité finie
La manière la plus simple de réaliser une pile consiste à utiliser un tableau de taille N ,
avec N suffisamment grand, c’est-à-dire au moins égal au nombre maximal d’éléments qui
seront stockés dans la pile. Les éléments sont rangés dans l’ordre où ils ont été empilés.
Pour pouvoir empiler et dépiler, il faut connaître la position du sommet de la pile dans le
tableau. Pour cela, le plus simple est de stocker le nombre d’éléments n de la pile dans la
case 0 du tableau, puis les n éléments de la pile dans les cases 1 à n. On a donc la structure
suivante :
0 1
. . .
n
N
n
éléments
place disponible
0 1 2 3
. . .
p = creer_pile(10)
0
. . .
empiler(p, A)
1 A
. . .
empiler(p, B)
2 A B
. . .
empiler(p, C)
3 A B C
. . .
depiler(p)
2 A B C
. . .
Les éléments colorés sont ceux qui sont réellement dans la pile. Les autres, par exemple
C à la dernière ligne, ne sont plus accessibles et seront écrasés lorsqu’on en empilera de
nouveaux.
Création d’une nouvelle pile
Pour créer une nouvelle pile de capacité c, on commence par allouer un tableau p de
c+1 cases.
def creer_pile(c):
p = (c + 1) * [None]