17 - Implémenter une Pile
Nous sommes parvenus à implémenter le type Liste sous la forme de plusieurs structures de données ayant des comportements internes différents mais ayant les mêmes fonctions d'interface primitives.
- Liste contiguë IMMUABLE avec des tableaux statiques : mauvaise idée, insertion et suppression linéaire partout.
- Liste contiguë MUABLE avec des tableaux dynamiques, comme le type list de Python : insertion et suppression à coût constant sur la dernière case mais linéaire ailleurs.
- Liste chaînée IMMUABLE avec un tuple () ou (valeur de tête, queue) : insertion et suppression à coût constant sur la tête, mais linéaire alleurs.
- Liste chaînée MUABLE avec des Classes Cellule et Liste : insertion et suppression à coût constant sur la tête, mais linéaire alleurs.
Aujourd'hui, nous allons implémenter le type abstrait Pile.
Prerequis : l'activité sur la Pile et celles sur les implémentations des Listes.
Documents de cours : open document ou pdf
1 - Implémentation d'une pile via un tableau dynamique
Les 5 fonctions primitives
Les 5 fonctions primitives à réaliser avec le meilleur coût possible sont :
PRIMITIVES pour un type IMMUABLE
- nouvellePile() -> Pile : on crée une nouvelle Pile vide.
- estPileVide(p:Pile) -> bool ou juste estVide() : renvoie un booléen qui vaut True si la pile p transmise est une pile vide.
- empiler(p:Pile, elt:Elt) -> Pile : on renvoie une pile en rajoutant l'élément elt au sommet p.
- depiler(p:Pile NON VIDE) -> Pile : on supprime le sommet et renvoie la nouvelle pile p. La fonction n'est définie que si la pile n'est pas vide.
- lireSommet(p:Pile NON VIDE) -> Elt : on renvoie l'élément qui occupe le sommet. La fonction n'est définie que si la pile n'est pas vide.
Attention, pour les types muables, les fonctions d'insertion et de suppression ont un prototype différent :
PRIMITIVES pour un type MUABLE
- empiler(p:Pile, elt:Elt) -> None
- depiler(p:Pile NON VIDE) -> Element
Le principe est donc de tenter de réaliser une implémentation où les primitives auront un coût le plus faible possible.
Tentons de partir sur des primitives à coût constant.
Cela veut donc dire qu'on veut que les fonctions d'insertion et de suppression soient à coût constant.
Réfléchissons :
- Nous voulons implémenter la Pile sous forme d'un tableau de type list.
- Nous savons que l'insertion et la suppression sur l'indice 0 est à coût LINEAIRE dans ces tableaux dynamiques.
- Nous savons que l'insertion et la suppression sur l'indice de fin (avec les méthodes append() et pop() est à coût amorti CONSTANT dans ces tableaux dynamiques.
- CONCLUSION : nous allons placer le SOMMET de notre Pile du côté de l'indice final.
Quelques explications sur le contenu interne du tableau (on notera que les instructions correspondent bien à un type mutable) : on ne stocke pas la réponse d'empiler() puisque cette réponse est ... None.
>>> a = nouvelle_pile()
>>> empiler(a, 5)
>>> empiler(a, 10)
>>> empiler(a, 20)
>>> depiler(a)
20
Localisation du Sommet dans l'implémentation tableau
Les données de la Pile sont dans un tableau.
On place le Sommet de la Pile à la fin du tableau pour profiter des coûts constants des méthodes append() et pop().
01° Compléter les différentes primitives pour parvenir à implémenter notre Pile MUABLE sous forme d'un tableau dynamique à l'interne.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | """MODULE d'implémentation de type abstrait PILE MUABLE
en utilisant des TABLEAUX DYNAMIQUES
La Pile vide sera représentée par un tableau vide [].
Le sommet d'une Pile non vide est situé en fin de tableau.
Fonctions primitives
--------------------
... : nouvelle_pile() -> 'Pile'
... : est_pile_vide(p:'Pile') -> bool
... : empiler(p:'Pile', elt:'Element') -> None
... : depiler(p:'Pile NON VIDE') -> 'Element'
... : lire_sommet(p:'Pile NON VIDE') -> 'Element'
"""
def nouvelle_pile() -> 'Pile':
"""Renvoie une nouvelle Pile vide"""
pass
def est_pile_vide(p:'Pile') -> bool:
"""Prédicat qui renvoie True si p est une Pile vide"""
pass
def empiler(p:'Pile', elt:'Element' ) -> None:
"""Modifie la pile p en rajouter elt au sommet"""
pass
def depiler(p:'Pile NON VIDE') -> 'Element':
"""Supprime le sommet de la Pile p et renvoie l'élément supprimé"""
pass
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
"""Renvoie la valeur actuellement au sommet de la Pile p NON VIDE"""
pass
if __name__ == '__main__':
a = nouvelle_pile()
empiler(a, 0)
empiler(a, 5)
empiler(a, 10)
empiler(a, 15)
s = lire_sommet(a)
assert s == 15
depiler(a)
s = lire_sommet(a)
assert s == 10
|
02° Estimer le coût des cinq fonctions primitives.
...CORRECTION...
Difficile de répondre sans connaître les codes des méthodes correspondantes de Python. C'est bien cela le problème de cette façon de faire.
Si on suppose que
- l'accès à la dernière case avec les crochets est à coût constant,
- le rajout d'une case en fin de tableau avec append() et
- la suppression de la dernière case pop() est à coût constant,
alors les opérations sur le sommet (lecture/modification et insertion/suppression) sont toutes à coût constant.
Implémentation du type Pile (MUABLE) en utilisant un TABLEAU DYNAMIQUE Python
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | """MODULE d'implémentation de type abstrait PILE MUABLE
en utilisant des TABLEAUX DYNAMIQUES
La Pile vide sera représentée par un tableau vide [].
Le sommet d'une Pile non vide est situé en fin de tableau.
Fonctions primitives
--------------------
CST : nouvelle_pile() -> 'Pile'
CST : est_pile_vide(p:'Pile') -> bool
CST : empiler(p:'Pile', elt:'Element') -> None
CST : depiler(p:'Pile NON VIDE') -> 'Element'
CST : lire_sommet(p:'Pile NON VIDE') -> 'Element'
"""
def nouvelle_pile() -> 'Pile':
"""Renvoie une nouvelle Pile vide"""
return []
def est_pile_vide(p:'Pile') -> bool:
"""Prédicat qui renvoie True si p est une Pile vide"""
return p == []
def empiler(p:'Pile', elt:'Element' ) -> None:
"""Modifie la pile p en rajouter elt au sommet"""
p.append(elt) # rajoute un élément à la fin du tableau
def depiler(p:'Pile NON VIDE') -> 'Element':
"""Supprime le sommet de la Pile p et renvoie l'élément supprimé"""
return p.pop() # supprime et renvoie le dernier élément du tableau
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
"""Renvoie la valeur actuellement au sommet de la Pile p NON VIDE"""
return p[len(p)-1] # ou même return p[-1]
if __name__ == '__main__':
a = nouvelle_pile()
empiler(a, 0)
empiler(a, 5)
empiler(a, 10)
empiler(a, 15)
s = lire_sommet(a)
assert s == 15
depiler(a)
s = lire_sommet(a)
assert s == 10
|
Attention : dans la version MUABLE (ou MUTABLE en franglais), la pile est modifiée directement en mémoire. Pour modifier une pile, il faut donc écrire quelque chose comme empiler(a, 15) puisque la fonction ne renvoie rien. N'écrivez SURTOUT PAS a = empiler(a, 15). Sinon, votre Pile contiendra None après exécution !
03° Utiliser cette implémentation pour constater qu'on a bien une Pile et, qu'à part la mutabilité, on ne peut pas savoir comment tout cela est implémenté à l'interne tant qu'on utilise uniquement les fonctions d'interface.
>>> a = nouvelle_pile()
>>> empiler(a, 5)
>>> a
[5]
>>> empiler(a, 10)
>>> a
[5, 10]
>>> empiler(a, 20)
>>> a
[5, 10, 20]
>>> depiler(a)
20
>>> a
[5, 10]
>>> depiler(a)
10
>>> a
[5]
>>> empiler(a, 40)
>>> a
[5, 40]
>>> depiler(a)
40
>>> a
[5]
>>> depiler(a)
5
Notez bien le comportement en PILE : le 40, qu'on rajoute plus tard, sort immédiatement alors qu'il est arrivé bien après : comportement LIFO.
Ce dernier exemple vous permet aussi de vous rendre compte que la pile fonctionne vraiment comme une pile d'assiettes ou de legos : on récupère nécessairement le dernier élément qu'on a inséré dans la Pile.
2 - Implémentation d'une Pile via une liste chaînée de tuples
Nous allons ici implémenter une Pile IMMUABLE en reprenant l'idée d'une liste chaînée dont les cellules sont des tuples (valeur de Tête, Queue) en remplaçant les noms des éléments pour qu'ils soient ceux de la Pile : un tuple (valeur du sommet, reste de la Pile).
Tentons de partir sur des primitives à coût constant.
Cela veut donc dire qu'on veut que les fonctions d'insertion et de suppression soient à coût constant.
Réfléchissons :
- Nous voulons implémenter la Pile sous forme d'un tuple n'ayant que deux éléments : la valeur à l'indice 0 et la cellule suivante sur l'indice 1.
- Nous savons que l'insertion et la suppression sur la tête de la liste chainée est à coût CONSTANT.
- Nous savons que l'insertion et la suppression sur la cellule de fin est à côut LINEAIRE.
- CONCLUSION : nous allons placer le SOMMET de notre Pile du côté de la TETE de la Liste chaînée.
Localisation du Sommet dans l'implémentation liste chaînée de tuples
Les données de la Pile sont dans les cellules de la liste chaînée.
On place le Sommet de la Pile sur la Tête de la liste chaînée pour profiter des coûts constants des fonctions inserer_tete() et supprimer_tete().
04° Compléter les différentes primitives pour parvenir à implémenter notre Pile IMMUABLE sous forme du tuple à l'interne.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | """MODULE d'implémentation de type abstrait PILE IMMUABLE
en utilisant des Cellules TUPLES pour former une liste chaînée
La Pile vide sera représentée par un tuple vide ().
Le sommet d'une Pile non vide est situé du même côté que la tête de la liste chaînée associée.
Fonctions primitives
--------------------
... : nouvelle_pile() -> 'Pile'
... : est_pile_vide(p:'Pile') -> bool
... : empiler(p:'Pile', elt:'Element') -> 'Pile'
... : depiler(p:'Pile NON VIDE') -> 'Pile'
... : lire_sommet(p:'Pile NON VIDE') -> 'Element'
"""
def nouvelle_pile() -> 'Pile':
"""Renvoie une nouvelle Pile vide"""
pass
def est_pile_vide(p:'Pile') -> bool:
"""Prédicat qui renvoie True si p est une Pile vide"""
pass
def empiler(p:'Pile', elt:'Element' ) -> 'Pile':
"""Renvoie une pile basée sur p mais en rajoutant elt au sommet"""
pass
def depiler(p:'Pile NON VIDE') -> 'Pile':
"""Renvoie une pile basée sur p mais en supprimant le sommet"""
pass
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
"""Renvoie la valeur actuellement au sommet de la Pile p NON VIDE"""
pass
if __name__ == '__main__':
a = nouvelle_pile()
a = empiler(a, 0)
a = empiler(a, 5)
a = empiler(a, 10)
a = empiler(a, 15)
s = lire_sommet(a)
assert s == 15
a = depiler(a)
s = lire_sommet(a)
assert s == 10
|
05° Estimer le coût des cinq fonctions primitives.
...CORRECTION...
On retrouve les mêmes coûts qu'avec la liste chaînée dont les cellules sont des tuples : toutes les opérations sont à coût CONSTANT sur la tête.
Et c'est pour cela qu'on a placer le sommet du côté de la tête.
Implémentation du type Pile IMMUABLE en utilisant des Cellules TUPLES pour former une liste chaînée
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | """MODULE d'implémentation de type abstrait PILE IMMUABLE
en utilisant des Cellules TUPLES pour former une liste chaînée
La Pile vide sera représentée par un tuple vide ().
Le sommet d'une Pile non vide est situé du même côté que la tête de la liste chaînée associée.
Fonctions primitives
--------------------
CST : nouvelle_pile() -> 'Pile'
CST : est_pile_vide(p:'Pile') -> bool
CST : empiler(p:'Pile', elt:'Element') -> 'Pile'
CST : depiler(p:'Pile NON VIDE') -> 'Pile'
CST : lire_sommet(p:'Pile NON VIDE') -> 'Element'
"""
def nouvelle_pile() -> 'Pile':
"""Renvoie une nouvelle Pile vide"""
return ()
def est_pile_vide(p:'Pile') -> bool:
"""Prédicat qui renvoie True si p est une Pile vide"""
return p == ()
def empiler(p:'Pile', elt:'Element' ) -> 'Pile':
"""Renvoie une pile basée sur p mais en rajoutant elt au sommet"""
return (elt, p) # renvoie un tuple contenant elt et menant ensuite à la pile p reçue
def depiler(p:'Pile NON VIDE') -> 'Pile':
"""Renvoie une pile basée sur p mais en supprimant le sommet"""
return p[1] # renvoie un tuple qui est le reste de la pile p
def lire_sommet(p:'Pile NON VIDE') -> 'Element':
"""Renvoie la valeur actuellement au sommet de la Pile p NON VIDE"""
return p[0] # renvoie la valeur stockée dans la cellule Sommet
if __name__ == '__main__':
a = nouvelle_pile()
a = empiler(a, 0)
a = empiler(a, 5)
a = empiler(a, 10)
a = empiler(a, 15)
s = lire_sommet(a)
assert s == 15
a = depiler(a)
s = lire_sommet(a)
assert s == 10
|
Attention : dans la version IMMUABLE, la pile n'est pas vraiment modifiée. Pour modifier une pile, il faut donc écrire quelque chose comme a = empiler(a, 15)
06° Utiliser cette implémentation pour constater qu'on a bien une Pile et, qu'à part la mutabilité, on ne peut pas savoir comment tout cela est implémenté à l'interne tant qu'on utilise uniquement les fonctions d'interface.
>>> a = nouvelle_pile()
>>> a = empiler(a, 5)
>>> a
(5, ())
>>> a = empiler(a, 10)
>>> a
(10, (5, ()))
>>> a = empiler(a, 20)
>>> a
(20, (10, (5, ())))
>>> a = depiler(a)
(10, (5, ()))
>>> a
(10, (5, ()))
>>> depiler(a)
(5, ())
>>> a
(10, (5, ())) # on voit que a n'a pas été modifié car on a juste écrit depiler(a)
>>> a = empiler(a, 40)
>>> a
(40, (10, (5, ())))
>>> a = depiler(a)
(10, (5, ()))
>>> a
(10, (5, ())) # on voit que a a été modifié car on a écrit a = depiler(a)
>>> a = depiler(a)
(5, ())
3 - Implémentation d'une pile via une liste chaînée basée sur des cellules-objets
Nous allons ici implémenter une Pile MUABLE en reprenant l'idée d'une liste chaînée dont les cellules sont des instances d'une classe Cellule n'ayant que deux attributs : v pour la valeur et s pour le successeur.
Tentons de partir sur des primitives à coût constant.
Cela veut donc dire qu'on veut que les fonctions d'insertion et de suppression soient à coût constant.
Réfléchissons :
- Nous voulons implémenter la Pile sous forme d'une liste chaînée simple. Comme pour la liste chaînée précédente, on sait qu'on ne parvient à insérer et supprimer à coût constant qu'au niveau de la Tête.
- CONCLUSION : nous allons placer le SOMMET de notre Pile du côté de la TETE de la Liste chaînée.
Localisation du Sommet dans l'implémentation liste chaînée d'objets-cellules
Les données de la Pile sont dans les cellules de la liste chaînée.
On place le Sommet de la Pile sur la Tête de la liste chaînée pour profiter des coûts constants des fonctions inserer_tete() et supprimer_tete().
07° Compléter les différentes primitives pour parvenir à implémenter notre Pile MUABLE sous forme d'objets à l'interne.
Commencez par réaliser les méthodes de l'objet puis compléter les fonctions pour qu'un utilisateur utilisant vos fonctions ne se rende pas compte qu'on utilise des objets pour implémenter la Pile.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 | |
08° Estimer le coût des cinq fonctions primitives.
...CORRECTION...
On retrouve les mêmes coûts qu'avec la liste chaînée dont les cellules sont des tuples : toutes les opérations sont à coût CONSTANT sur la tête.
Et c'est pour cela qu'on a placer le sommet du côté de la tête.
Implémentation du type Pile MUABLE en utilisant des Cellules Objets pour former une liste chaînée
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88 | |
Mais on peut faire bien plus simple : notre Pile utilise une liste chaînée muable. Pourquoi ne pas importer cette structure que nous avons déjà réalisée et simplement la manipuler ?
09° Télécharger le module suivant qui implémente une liste chaînée sous forme de Cellules-objets. Répérer bien le répertoire dans lequel vous le placer puisque vous allez devoir y placer un second programme.
10° Créer ce programme en le plaçant au même endroit que notre module liste_chainee_tete.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 | |
CONCLUSION
Avantage de ce module par rapport à la Pile où nous avions tous reconstruit : beaucoup plus léger, on utilise juste la Liste.
Désavantage : notre module possède une dépendance. Il faut donc d'abord récuper le module sur la Liste avant de pouvoir utiliser le notre.
4 - Mini-Projet pour les plus rapides : Pile sous forme dictionnaire + tableau statique
Bon, à vous de travailler : on veut créer une implémentation de Pile muable ne pouvant contenir que 10 élements.
Le principe est le suivant :
- On crée un dictionnaire qui encodera la pile et qui intégre
- le nombre d'éléments dans la Pile via une clé "nbr",
- le nombre d'éléments maximum dans la Pile via une clé "max",
- les données de la Pile via une clé "data"
- On crée un tableau statique contenant 10 cases vides. Ce tableau est destiné à contenir les données de notre Pile et sa référence est la valeur associée à la clé "data".
Un exemple d'utilisation qui devra fonctionner de la même manière avec votre implémentation une fois qu'elle sera fonctionnelle.
>>> a = nouvellePile()
>>> empiler(5, a)
>>> a
{'nb': 1, 'max': 10, 'data': [5, None, None, None, None, None, None, None, None, None]}
>>> empiler(10, a)
>>> a
{'nb': 2, 'max': 10, 'data': [5, 10, None, None, None, None, None, None, None, None]}
>>> empiler(20, a)
>>> a
{'nb': 3, 'max': 10, 'data': [5, 10, 20, None, None, None, None, None, None, None]}
>>> estPileVide(a)
False
>>> estPilePleine(a)
False
>>> taille(a)
3
>>> depiler(a)
20
>>> a
{'nb': 2, 'max': 10, 'data': [5, 10, None, None, None, None, None, None, None, None]}
>>> empiler(40, a)
>>> a
{'nb': 3, 'max': 10, 'data': [5, 10, 40, None, None, None, None, None, None, None]}
>>> depiler(a)
40
>>> depiler(a)
10
>>> depiler(a)
5
>>> depiler(a)
>>> a
{'nb': -1, 'max': 10, 'data': [None, None, None, None, None, None, None, None, None, None]}
Remarquez bien que comme nous avons dépiler une pile vide, le compteur final donne quelque chose d'aberrant : la taille de la pile vaudrait -1 éléments !
Et voici le début de l'implémentation. A vous de la finir !
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83 | |
✎ 08° Voici la notation :
- Implémentation correcte : 8 points
- Avoir utiliser autant que possible les fonctions d'interface déjà réaliser, même dans le code des autres fonctions d'interface : 2 points
- Justification du type de coût en lecture, en insertion et en suppression : 2 points
- Création d'une fonction inverser() qui inverse le sommet et l'élément suivant pour une pile d'au moins 2 éléments : 2 points
- Création d'une fonction vider() qui vide la pile NON VIDE : 2 points
- Documentation des différentes fonctions d'interface : 2 points
- Réalisation d'assertion pour vérifier que les piles à gérer ne sont ni vide avant lecture ou suppression, ni pleine en cas d'insertion, que la pile contient bien au moins deux éléments avant inversion... : 2 points.
Activité publiée le 14 10 2020
Dernière modification : 16 10 2021
Auteur : ows. h.