Résumé 15 - TYPE ABSTRAIT PILE LIFO
Lien vers l'activité : type abstrait Pile LIFO
Dernière modif. : 25 10 2020
1-Type abstrait PILE / STACK : organisation et interface
C'est une séquence ordonnée et finie d'éléments respectant le principe LIFO.
LIFO veut dire Last In First Out. Le dernier élément arrivé sera le premier à repartir.
Fonctions d'interface minimale
On retrouve les fonctions de la liste mais limitées à l'action sur le SOMMET. On en trouve des versions mutables ou non mutables. Ici, c'est non mutable puisqu'on renvoie des Piles après chaque modification.
nouvellePile() -> Pile
estVide(p:Pile) -> bool
empiler(elt:Elt, p:Pile) -> Pile
: on rajoute au SOMMETdepiler(p:Pile) -> Pile
: on supprime le SOMMETlireSommet(p:Pile) -> Elt
2-Implémentations d'une PILE avec Python
Implémentation sous forme d'un tableau ou d'une liste chaînée
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 |
|
On peut utiliser un TABLEAU ou une LISTE CHAINEE puisqu'au final une PILE est un peu un cas particulier et limité de la LISTE. On peut utiliser le type natif list si on fait du Python et qu'on ne veut pas tout avoir à refaire. On utiilse alors un tableau dynamique.
Implémentation sous forme de tuple (sommet,queue)
Nous avions vu que le coût en insertion / suppression de la tête était constant pour cette implémentation. Or, une pile est bien une telle liste dont la tête se nomme le sommet.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 |
|