17 - Implémenter une Pile
Nous avons vu la différence entre les types abstraits et les structures de données concrètes.
Nous sommes parvenus à implémenter le type abstrait Liste sous la forme de plusieurs structures de données ayant le bon comportement.
Aujourd'hui, nous allons voir quelques implémentations possibles du type Pile et File. Nous allons donc créer les structures de données permettant de programmer des piles et des files.
Prerequis : les deux activités sur Pile et File, ainsi qu'au moins l'une des activités d'implémentation du type liste.
1 - Implémentation d'une Pile en tant que tuple
On rappelle d'abord ce qu'est le type abstrait Pile :
Type abstrait PILE - Principe LIFO
Principe général d'organisation de la PILE : LIFO
Une pile est un type abstrait de données ayant les propriétés suivantes :
- il s'agit d'une séquence finie et ordonnée de données
- on s'impose d'agir uniquement sur l'une des extrémités qu'on nomme le sommet :
- insérer un élément au sommet se nomme l'empilement
- supprimer un élément au sommet se nomme le dépilement
On désigne également la pile sous l'acronyme LIFO pour Last In First Out (à savoir), ou en français : Dernier arrivé, premier parti.

Fonctions d'interface pour une PILE (en version non mutable ici)
Voici la description des fonctions d'interface fondamentales que les algorithmes vont pouvoir effectuer sur le type Pile.

nouvellePile() -> Pile
: on crée une nouvelle pile vide. On pourra l'identifier à()
. En anglais, cela pourrait donnernewStack
.pileVide(p:Pile) -> bool
: renvoie un booléen qui vaut True si la pile p transmise est une pile vide. On peut également la nommerestVide
. En anglais, cela pourrait donnerisNil
ouisNull
.empiler(elt:Elt, p:Pile) -> Pile
: on renvoie une pile en rajoutant l'élément elt au sommet de la pile p. En anglais, ça se nommepush
. On considère qu'une bonne implémentation réalise ceci à coût constant (θ(1))depiler(p:Pile) -> Pile
: on supprime le sommet et renvoie la nouvelle pile. En anglais, ça se nommepop
. La fonction n'est définie que si la pile n'est pas vide. On considère qu'une bonne implémentation réalise ceci à coût constant (θ(1)).lireSommet(p:Pile) -> Elt
: on renvoie l'élément qui occupe le sommet. La fonction n'est définie que si la pile n'est pas vide. En anglais, ça se nommepeek
outop
Si on regarde bien cette structure, on voit qu'elle correspond à une Liste en se donnant comme restriction de ne pouvoir agir que sur la Tête, qu'on nomme ici Sommet.
On peut donc écrire cette structure en reprenant notre implémentation tuple (tete,queue)
en remplaçant les noms des éléments pour qu'ils soient ceux de la Pile.
Implémentation d'une Pile (non mutable) sous forme d'un tuple
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 |
|
J'ai rajouté ici une fonction d'interface afficherPile permettant à l'utilisateur d'avoir une vision globale des données pour vous montrer ce que contient la pile. Normalement, nous ne sommes pas censés le faire : on ne devrait pouvoir accéder à ce qu'il y a sous le Sommet qu'après avoir enlevé ce sommet. Mais c'est juste pour vous montrer qu'on peut représenter les données de la Pile comme on veut.
Remarque : si on place 5 puis 10 puis 20 dans la pile, l'utilisation de la fonction afficherPile montrera ceci dans la console :
>>> a = nouvellePile()
>>> a = empiler(5, a)
>>> a = empiler(10, a)
>>> a
(10, (5, ()))
>>> a = empiler(20, a)
>>> a
(20, (10, (5, ())))
>>> afficherPile(a)
'Pile : Sommet -> 20 -> 10 -> 5'
01° Mettre en mémoire la version ci-dessous.
Au vu du code de la fonction ci-dessous, a-t-on affaire à une version mutable ou non mutable ?
1
2
3 |
|
Conclusion : lorsqu'on veut empiler, doit-on écrire a = empiler(5, a)
ou juste empiler(5, a)
?
...CORRECTION...
La fonction empiler renvoie une donnée de type Liste, on voit bien qu'il s'agit d'une version non mutable.
Il faudra donc écrire le premier code, a = empiler(5, a)
de façon à stocker la nouvelle pile dans une nouvelle variable, portant le même nom que l'ancienne si on veut.
Mais ceci fonctionne aussi : b = empiler(5, a)
.
02° L'utilisation stricte des fonctions d'interface permet-il à l'utilisateur de connaître l'implémentation interne des données ?
...CORRECTION...
Nous l'avons déjà vu de nombreuses fois : non.
La fonction afficherPile nous permet de fournir n'importe quelle représentation des données. Cela n'a pas forçément de lien avec la façon dont les vraies données sont mémorisées.
03° Regarder les instructions ci-dessous. Demandez vous ce qui va s'afficher sur la console à chaque fois que quelque chose doit s'afficher. Vérifiez ensuite en tapant le code dans la Console.
>>> a = nouvellePile()
>>> a = empiler('bonjour', a)
>>> a = empiler('à', a)
>>> a = empiler('tous', a)
>>> a = empiler('!', a)
>>> afficherPile(a)
??? premier affichage à trouver ???
>>> x = lireSommet(a)
>>> x
??? deuxième affichage à trouver ???
>>> x = lireSommet(a)
>>> x
??? troisième affichage à trouver ???
>>> afficherPile(a)
??? quatrième affichage à trouver ???
>>> a = depiler(a)
>>> x = lireSommet(a)
>>> x
??? cinquième affichage à trouver ???
>>> afficherPile(a)
??? sixième affichage à trouver ???
...CORRECTION...
>>> a = nouvellePile()
>>> a = empiler('bonjour', a)
>>> a = empiler('à', a)
>>> a = empiler('tous', a)
>>> a = empiler('!', a)
>>> afficherPile(a)
'Pile : Sommet -> ! -> tous -> à -> bonjour'
>>> x = lireSommet(a)
>>> x
'!'
>>> x = lireSommet(a)
>>> x
'!'
>>> afficherPile(a)
'Pile : Sommet -> ! -> tous -> à -> bonjour'
>>> a = depiler(a)
>>> x = lireSommet(a)
>>> x
'tous'
>>> afficherPile(a)
'Pile : Sommet -> tous -> à -> bonjour'
04° Quel est le coût de la fonction empiler? De la fonction depiler ? De la fonction lireSommet ?
...CORRECTION...
Dans les 3 cas, il suffit d'agir sur le sommet. On a un accès constant puisqu'il suffit d'aller lire l'index 0 pour le sommet ou 1 pour le reste de la pile.
2 - Implémentation d'une pile dans un tableau dynamique
Nous pourrions implémenter la Pile comme un tableau statique ou comme une liste chaînée puisque la Pile est une sorte de cas particulier du type Liste.
En Python, les Piles ne sont pas nativement implémentées. Regardons comment réaliser une implémentation du type Pile en utilisant les méthodes natives de la structure de données tableau dynamique dont le type natif est list en Python... Je ne suis pas chef du vocabulaire. J'y suis pour rien .
Le principe est simple :
- La méthode append des objets list permet de rajouter l'élément à la fin du tableau.
- La méthode pop des objets list permet de supprimer l'élément situé à la fin du tableau, et elle le renvoie !
Implémentation du type Pile (mutable) 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 |
|
Attention : dans la version mutable, la pile est modifiée directement en mémoire. Du coup, la fonction empiler ne renvoie rien (c'est une sorte de "procédure") et la fonction depiler est souvent utilisée pour renvoyer l'élément qu'on vient de supprimer.
Quelques explications sur le contenu interne du tableau (on notera que les instructions correspondent bien à un type mutable) :
>>> a = nouvellePile()
>>> empiler(5, a)

>>> empiler(10, a)

>>> empiler(20, a)

>>> depiler(a)
20

05°Estimer le coût des trois fonctions empiler, depiler et lireSommet.
...CORRECTION...
Difficile de répondre sans connaître les codes des méthodes correspondantes.
Si on suppose que l'accès à la dernière case , le rajout d'une case en fin de tableau et la suppression de la dernière case sont à coût constant, alors les trois opérations sont à coût constant.
06° Mettre en mémoire la version ci-dessous.
Au vu du code, a-t-on affaire à une version mutable ou non mutable ?
1
2 |
|
Doit-on écrire a = empiler(5, a)
ou juste empiler(5, a)
?
...CORRECTION...
On constate que la fonction empiler ne renvoie rien et que la fonction depiler renvoie un élément, et non pas pas une nouvelle Pile. La structure de données Pile créée ici est donc une structure mutable.
Il faut donc taper empiler(5, a)
N'utilisez surtout pas la première version : vous allez juste remplir la variable a avec ... rien puisque la fonction renvoie renvoie None. Vous allez donc supprimer votre belle pile.
Si vous écrivez ceci : a = empiler(5, a)
Il se passe ceci : a = None
07° Utiliser cette version et sa fonction d'affichage 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 = nouvellePile()
>>> empiler(5, a)
>>> empiler(10, a)
>>> empiler(20, a)
>>> depiler(a)
20
>>> depiler(a)
10
>>> empiler(40, a)
>>> depiler(a)
40
>>> 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.
3 - FAQ
C'est quoi ce return pile[-1]
alternatif dans la dernière fonction ?
Un raccourci Python pour dire : le premier élément en partant de la fin.
C'est comme si on avait demandé un index valant la longeur du tableau - 1
.
C'est une Pythonnerie. Un index de -1 veut dire le dernier élément. Un index de -2 veut dire l'avant-dernier...
On ne peut donc pas utiliser ceci dans un algorithme : dans certains langages, une demande d'index de -1 va déclencher une erreur.
22
23
24 |
|
On pourait donc écrire ceci en Python :
22
23
24 |
|
Activité publiée le 14 10 2020
Dernière modification : 14 10 2020
Auteur : ows. h.