Livre_silo 30 août 2013 16:32 Page 301
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
301
12 – Structure de pile
p = creer_pile(10)
empiler(p, A)
A
empiler(p, B)
empiler(p, C)
C
B
A
depiler(p)
B
A
D’autres opérations sont disponibles, mais ne modifient pas la pile :
• taille(p) renvoie le nombre d’éléments contenus dans la pile p.
• est_vide(p) indique si la pile p est vide.
• sommet(p) renvoie le sommet de la pile p, sans modifier p.
SAVOIR-FAIRE Choisir un type de données en fonction d’un problème
à résoudre
La pile est une structure de données appropriée quand :
• On veut stocker des éléments dont le nombre est variable, a fortiori dont le cardinal
maximum est inconnu à l’avance.
• On peut ou on doit se contenter d’accéder au dernier élément stocké.
Réciproquement :
• Si on veut pouvoir accéder à un élément quelconque à tout moment, il faudra utiliser un tableau.
• Pour cela, il est préférable de connaître au moins un majorant du nombre d’éléments
à stocker.
Exercice 12.1 Quelle structure de données choisir pour chacune de ces tâches ?
1 Représenter un répertoire téléphonique.
2 Stocker l’historique des actions effectuées dans un logiciel et disposer d’une commande Annuler (ou
Undo).
3 Comptabiliser les pièces ramassées et dépensées par un personnage dans un jeu.
4 Ranger des dossiers à traiter sur un bureau.
1 Le nombre d’entrées du répertoire varie au cours du temps, mais on veut pouvoir accéder à n’importe
quel élément. On doit donc utiliser un tableau, quitte à réserver trop de place dans celui-ci.
2 La commande Annuler n’a besoin que de connaître la dernière action effectuée. Une fois celle-ci annulée, on peut annuler l’avant-dernière, etc. Une pile est donc tout à fait appropriée.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
301
12 – Structure de pile
p = creer_pile(10)
empiler(p, A)
A
empiler(p, B)
empiler(p, C)
C
B
A
depiler(p)
B
A
D’autres opérations sont disponibles, mais ne modifient pas la pile :
• taille(p) renvoie le nombre d’éléments contenus dans la pile p.
• est_vide(p) indique si la pile p est vide.
• sommet(p) renvoie le sommet de la pile p, sans modifier p.
SAVOIR-FAIRE Choisir un type de données en fonction d’un problème
à résoudre
La pile est une structure de données appropriée quand :
• On veut stocker des éléments dont le nombre est variable, a fortiori dont le cardinal
maximum est inconnu à l’avance.
• On peut ou on doit se contenter d’accéder au dernier élément stocké.
Réciproquement :
• Si on veut pouvoir accéder à un élément quelconque à tout moment, il faudra utiliser un tableau.
• Pour cela, il est préférable de connaître au moins un majorant du nombre d’éléments
à stocker.
Exercice 12.1 Quelle structure de données choisir pour chacune de ces tâches ?
1 Représenter un répertoire téléphonique.
2 Stocker l’historique des actions effectuées dans un logiciel et disposer d’une commande Annuler (ou
Undo).
3 Comptabiliser les pièces ramassées et dépensées par un personnage dans un jeu.
4 Ranger des dossiers à traiter sur un bureau.
1 Le nombre d’entrées du répertoire varie au cours du temps, mais on veut pouvoir accéder à n’importe
quel élément. On doit donc utiliser un tableau, quitte à réserver trop de place dans celui-ci.
2 La commande Annuler n’a besoin que de connaître la dernière action effectuée. Une fois celle-ci annulée, on peut annuler l’avant-dernière, etc. Une pile est donc tout à fait appropriée.