Pour beaucoup d'applications, les seules insertions ou suppressions à effectuer sont celles qui doivent se faire sur le dernier élément inséré : la gestion du bouton "Reculer d'une page" dans les navigateurs Web par exemple.
Nous pourrions utiliser des Listes. Mais les Listes font trop de choses par rapport à ce que demandent les utilisations précédentes. Nous allons donc définir un nouveau type abstrait afin d'implémenter ensuite une structure de données dont les performances seront optimisées pour réaliser les tâches voulues, celles qui nous semblent utiles. Nous avons vu qu'optimiser une liste pour qu'elle sache tout bien faire était impossible.
Plutôt que d'utiliser le couteau-suisse Liste, nous allons voir qu'on peut utiliser un outil spécialisé : la Pile ou la File, en fonction des besoins.
Pile, comme pile d'assiettes : on ne peut prendre que l'assiette qui est au sommet ou rajouter une nouvelle assiette au sommet.
1.1 Première partie de la définition de Pile : l'idée générale d'organisation (LIFO)
A Propriétés générales d'organisation
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 strictement de n'agir que 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
PILE : on doit d'abord gérer l'assiette rouge avant de pouvoir accéder à celles en dessus
On désigne également la pile sous l'acronyme LIFO pour Last In First Out (à savoir), ou en français : Dernier arrivé, premier parti. Comme lorsqu'on doit laver une pile d'assiettes.
B - Exemples de visualisation
Trois façons de voir graphiquement une pile contenant un sommet valant 5 suivi du reste de la pile.
5 → 2 → 7 → 9
9 ← 7 ← 2 ← 5
Nous allons plutôt la représenter ainsi, car c'est très proche de l'idée même d'une pile d'assiettes ou d'une pile de livres :
5Sommet
2
7
9
1.2 Primitives d'une Pile
A (RAPPEL) Fonctions d'interface
Fonctions d'interface d'un module : en informatique, les fonctions d'interface caractérisent les fonctions qui sont utilisables par l'utilisateur d'un module.
B (RAPPEL) Primitives
Trois idées caractérisent ces fonctions particulières :
Les opérations primitives font partie des fonctions d'interface disponibles pour ce type abstrait de données.
Les opérations primitives sont les briques d'actions fondamentales permettant d'agir sur ce type de données.
Les futures implémentations des primitives devront avoir le coût le plus faible possible (se rapprochant d'un coût constant si possible).
C - Les primitives d'une Pile
nouvellePile() -> Pile VIDE : on crée une nouvelle pile vide. On pourra l'identifier à () par exemple.
En anglais, on la nomme newStack().
estPileVide(p:Pile) -> bool ou juste estVide() : renvoie un booléen qui vaut True si la pile p transmise est une pile vide.
En anglais, isEmpty().
empiler(elt:Elt, p:Pile) -> Pile NON VIDE : on renvoie une pile en rajoutant l'élément elt au sommet p. En anglais, push(). Une bonne implémentation de Pile réalise donc cela à coût constant (𝞗(1))
depiler(p:Pile NON VIDE) -> Pile : on supprime le sommet et renvoie la nouvelle pile p.
PRECONDITION : la fonction n'est définie que si la pile n'est pas vide.
En anglais, pop().
Une bonne implémentation de Pile réalise donc cela à coût constant (𝞗(1))
lireSommet(p:Pile NON VIDE) -> Elt : on renvoie l'élément qui occupe le sommet.
PRECONDITION : la fonction n'est définie que si la pile n'est pas vide.
En anglais, peek() ou top()
Contrairement à la Liste, il n'y a pas de primitives liées au type intermédiaire Place : pas de fonctions acces(), successeur() ou contenu() nécessaires puisque l'utilisateur n'a le droit que d'accéder au sommet. On lui simplifie le travail en ne lui fournissant que les outils nécessaires à la gestion de ce type de structure.
Point important mais plein de subtilité
Une Pile est-elle finalement une Liste définie avec une interface qui ne gère que la tête ?
Non, la Pile se distingue de la Liste par le fait qu'on ne va pas avoir besoin de lire (régulièrement) un élément interne et qu'on ne va pas avoir besoin d'insérer (régulièrement) un élément ailleurs qu'au sommet.
On ne va donc pas chercher à optimiser quoi que ce soit dans la gestion des éléments internes, contrairement à la Liste où ces opérations sont censées pouvoir être faites assez souvent.
Regardons l'exemple des assiettes :
Si vous savez que vous allez devoir les trier d'une façon ou d'une autre, autant les poser les unes à côté des autres sur la table : vous utilisez l'idée d'une Liste. Ainsi, si vous avez besoin de lire le numéro sous une assiette, vous y avez accès directement. Si vous voulez insérer une assiette entre deux autres, il suffit de légèrement en pousser deux et d'insérer la nouvelle dans l'espace libéré.
Si vous ne voulez pas faire cela, on peut les empiler : c'est l'idée d'une Pile.
Quel est l'intérêt ? Si on peut faire la même chose, autant prendre l'outil le plus polyvalent, non ?
Et bien non : La Liste est plus polyvalente qu'une Pile mais suppressions internes. Plus de lignes, plus de vérifications, plus de risques d'erreur en cas de modification du code.
Et si on veut lire les éléments de la PILE à titre exceptionnel ?
Ce n'est pas grave si c'est rare. Le coût amorti sera toujours bon.
Et si je dois faire cela souvent sur ma Pile ?
C'est que vous auriez dû travailler avec Liste, pas avec Pile.
01° Fournir les contenus successifs de la pile p1 après exécution de chacune des instructions de l'algorithme suivant :
p1 ← nouvellePile()
p1 ← empiler(5, p1)
p1 ← empiler(7, p1)
x ← lireSommet(p1)
p1 ← empiler(x, p1)
p1 ← empiler(4, p1)
p1 ← depiler(p1)
...CORRECTION...
La forme de la représentation n'a que peu d'importance. On peut la faire en ligne ou en colonne. Cela ne change rien aux données.
S'agissant de pile, je prendrai ici la représentation verticale, mais on pourrait aussi bien le faire en représentation horizontale.
p1 ← nouvellePile()
La variable p1 est une pile vide.
p1 ← empiler(5, p1)
5Sommet
p1 ← empiler(7, p1)
7Sommet
5
x ← lireSommet(p1)
7Sommet
5
Aucun changement mais la variable x est affectée à la valeur 7.
p1 ← empiler(x, p1)
7Sommet
7
5
p1 ← empiler(4, p1)
4Sommet
7
7
5
p1 ← depiler(p1)
7Sommet
7
5
Attention, le 4 aura totalement disparu car on ne l'a pas stocké ailleurs.
02° On veut stocker séquentiellement 1, 2, 3 dans une pile. Donner l'algorithme à utiliser et fournir la représentation finale de la pile. Que va renvoyer la fonction lireSommet() ? La pile est-elle modifiée après cette lecture ?
...CORRECTION...
p2 ← nouvellePile()
p2 ← empiler(1, p2)
p2 ← empiler(2, p2)
p2 ← empiler(3, p2)
x ← lireSommet(p2)
Ceci donne :
3Sommet
2
1
La variable x va alors contenir la valeur 3.
D'après la description de la fonction lireSommet(), il n'y a pas modification de la pile : il s'agit juste de lecture.
1.3 En version muable
Pour les implémentations qui utilisent une structure mutable, on trouve souvent les fonctions depiler() et lireSommet() regroupées dans une seule et même fonction
qui va modifier la pile sur place (sans nécessité de renvoyer les données donc) et
qui renvoie le sommet qu'on vient de supprimer, plutôt que de renvoyer None.
De même, la fonction empiler() ne renvoie rien : elle modifie sur place le tableau par effet de bord.
Les prototypes de ces fonctions d'interface sont alors :
empiler(x:Elt, p:Pile) -> None : on rajoute un élément au sommet en modifiant la pile en place. On ne renvoie donc rien.
depiler(p:Pile NON VIDE) -> Elt : on supprime le sommet en modifiant la pile en place et on renvoie l'ancien sommet.
03° Fournir les contenus successifs de la pile mutablep3 après exécution de chacune des instructions de l'algorithme suivant :
Attention, pensez à bien appliquer le nouveau prototype des fonctions : elles ne réagissent pas de la même façon que celles des questions 1 et 2 puisque nous travaillons avec une version mutable de pile.
p3 ← nouvellePile()
empiler(5, p3)
empiler(7, p3)
x ← depiler(p3)
empiler(x, p3)
empiler(4, p3)
depiler(p3)
...CORRECTION...
La forme de la représentation n'a que peu d'importance. On peut la faire en ligne ou en colonne. Cela ne change rien aux données.
S'agissant de pile, je prendrai ici la représentation verticale, mais on pourrait aussi bien le faire en représentation horizontale.
p3 ← nouvellePile()
La variable p3 est une pile vide.
empiler(5, p3)
5
empiler(7, p3)
7
5
x ← depiler(p3)
5
Cette fois, la fonction supprime le sommet et le renvoie, ce qui permet de le stocker dans la variable x qui est affectée à la valeur 7.
empiler(x, p3)
7
5
empiler(4, p3)
4
7
5
depiler(p3)
7
5
Attention, ici on dépile mais on ne stocke pas le 4 : il a donc juste disparu à jamais.
1.4 Primitives optionnelles
Les primitives précédentes permettent bien entendu de créer de nouvelles fonctionnalités. Selon les applications, nous aurons besoin d'en créer ou pas.
taille(p:Pile) -> Entier : on renvoie le nombre d'éléments dans la Pile. Cela peut être pratique pour éviter de dépasser la taille limite (erreur de dépassement de la mémoire allouée à la pile, stack overflow en anglais, voir la FAQ).
vider(p:Pile) -> Pile VIDE en immuable ou vider(p:Pile) -> Rien en muable : on vide la pile. Pour une pile immuable, on renvoie donc une pile vide. Cela peut être utile pour signaler qu'on se sépare d'éléments pourtant non traités (et qui ne le seront jamais du coup !). Par exemple, annuler les anciens documents envoyés à l'imprimante et pas encore imprimés.
En anglais, clear().
echanger(p:Pile DE DEUX ELEMENTS AU MOINS) -> Pile DE DEUX ELEMENTS AU MOINS : on inverse le sommet et l'élément juste en dessous. En anglais, swap().
Encore une fois, le prototype sur une Pile muable serait plutôt echanger(p:Pile DE DEUX ELEMENTS AU MOINS) -> Rien.
Nous allons devoir utiliser certaines de ces fonctions pour résoudre l'exercice suivant.
04-A° Réaliser les trois algorithmes correspondant aux fonctions suivantes (vous avez donc droit à POUR, TANT QUE, SI, SINON SI, SINON et aux variables) en considérant une Pile immuable :
taille(p:Pile) -> Entier : on renvoie le nombre d'éléments dans la Pile.
vider(p:Pile) -> Pile : on vide la pile.
echanger(p:Pile DE DEUX ELEMENTS AU MOINS) -> Pile DE DEUX ELEMENTS AU MOINS : on inverse le sommet et l'élément juste en dessous.
04-B° Réaliser les trois algorithmes correspondant aux fonctions suivantesn considérant une Pile muable :
taille(p:Pile) -> Entier : on renvoie le nombre d'éléments dans la Pile.
vider(p:Pile) -> Rien : on vide la pile.
echanger(p:Pile DE DEUX ELEMENTS AU MOINS) -> Rien : on inverse le sommet et l'élément juste en dessous.
Au vu du coût de taille(), que devrait-t-on faire lorsqu'on implémentera réellement cette Pile ?
05° Nous présentons ici plusieurs problèmes. Pour chacun des problèmes, dire si l'utilisation d'une pile est adaptée, ou pas. Si la pile n'est pas adaptée, expliquer le problème qu'on va rencontrer en résolvant le problème avec ce type de gestion.
A - Annulation des actions dans un logiciel.
On stocke les actions avec un empilement. On utilise un dépilement pour savoir ce qu'on doit annuler.
B - Réception et gestion des requêtes HTTP sur un serveur
La réception sera gérée par un empilement. La gestion se fait progressivement avec un dépilement.
C - Réception et gestion des demandes d'impression sur une imprimante partagée
La réception sera gérée par un empilement. La gestion se fait progressivement avec un dépilement.
D - Inversion des éléments d'un tableau
On stocke les éléments avec un empilement en commençant par l'index 0. Une fois tout le tableau lu, on dépile les éléments stockés un par un pour créer le nouveau tableau en commençant par l'index 0.
E - Classement des produits les plus vendus
On désire obtenir tous les mois une mise à jour des produits les plus vendus dans un magasin.
F - Gestion des clients arrivant dans un magasin
On empile le client lorsqu'il rentre dans la boutique. On dépile pour savoir qui servir.
G - Stockage des fonctions lors des appels
On stocke en mémoire les fonctions avec un empilement lorsque le programme en a besoin. On dépile lorsqu'elles répondent.
H - Questions et réponses d'un prof lors d'un cours
Les questions sont stockées avec un empilement. La réponse à la question se fait progressivement avec un dépilement.
I - Gestion des stocks
On empile un produit lorsqu'il rentre en magasin. On doit le supprimer lorsqu'il sort.
Exemple 1 : gestion des parenthèses ouvertes-fermantes
C'est un classique : comment savoir si l'expression arithmétique (5*2)+((5+2)*6) est correctement parenthésée ou si il y a un problème de syntaxe ?
Déroulé :
On transforme l'expression en ne gardant que les parenthèses : ()(()).
Pour toutes les parenthèses de la séquence :
lorsqu'on tombe sur une parenthèse ouvrante, on l'empile.
Lorsqu'on tombe sur une parenthèse fermante :
Si la pile est vide, on répond FAUX pour signaler un problème.
Sinon, on dépile la balise d'ouverture qui se trouve au sommet
Une fois toute la séquence lue :
Si la pile est vide, on répond VRAI pour signaler qu'il a bien eu autant de parenthèses ouvertes que fermées.
Sinon, on répond FAUX.
Un exemple de déroulé :
()(()).
On tombe sur une ouverture : ()(()). On empile cette ouverture.
graph TD
A[Ouverture a]
On tombe sur une parenthèse de fermeture : ()(()). On dépile puisque la pile n'est pas vide.
graph TD
-
On tombe sur une ouverture : ()(()). On empile cette ouverture.
graph TD
A[Ouverture b]
On tombe sur une ouverture : ()(()). On empile cette ouverture.
graph TD
D[Ouverture c] --> C[Ouverture b]
On tombe sur une fermeture : ()(()). On dépile puisque la pile n'est pas vide.
graph TD
A[Ouverture b]
On tombe sur une fermeture : ()(()). On dépile puisque la pile n'est pas vide.
graph TD
-
Après la lecture de la séquence, on constate que la Pile est vide : le parenthésage est donc bon.
06° Réaliser l'empilement et le calcul du compteur pour la séquence suivante (()))() ? Que peut-on en conclure vis à vis du parenthèsage ?
Une fois qu'on sait qu'une expression est bien parenthèsée, on peut essayer de l'évaluer. Pour cela, nous avons besoin de savoir ce qu'on doit évaluer.
Exemple 2 - Evaluation d'une expression correctement parenthèsée
L'algortihme précédent nous permet de savoir que l'expression est correctement parenthèsée.
Comment réaliser l'évaluation de cette expression cette fois ?
On place dans une PILE les indices des parenthèse ouvrantes qu'on découvre dans l'expression.
Lorsqu'on découvre une parenthèse fermante, on lit le sommet de la pile et on crée un tuple (indice ouverture, indice fermeture) qu'on peut placer à la fin d'un tableau dynamique.
Exemple avec l'expression arithmétique (5*2)+((5+2)*6)
On dépile (on récupère 6) et on rajoute le tuple (6, 14) en fin de tableau.
PILE : VIDE
TABLEAU : [(0, 4), (7, 11), (6, 14)]
Et voilà : l'interpréteur sait donc maintenant qu'il doit commencer par évaluer l'expression entre les indices 0 et 4, puis entre 7 et 11 et finalement entre 6 et 14. Il pourra alors évaluer l'expression entre 0 et 14.
07° Recherche en utilisant cette méthode le tableau des évaluations à faire pour l'expression suivante (5*((5+9)+3)).
08° Si on transforme la notion de parenthèses ouvrantes-fermantes en balises ouvrantes-fermantes, comment valider une page HTML dont les balises sont fournies dans cet ordre ?
09° Comment invalider une page HTML dont les balises sont fournies dans cet ordre ? Vous pourrez vous demander sous quelle condition on peut rajouter une balise de fermeture.
Imaginons qu'on veuille écrire e = (5 + 2) * 10. On voit bien qu'on a besoin d'utiliser des parenthèses.
Regardons comment écrire cette expression en remplaçant les opérateurs + * en utilisant plutôt les fonctions à deux arguments addition() multiplication().
On peut alors écrire e = multiplication(addition(5, 2), 10)).
On voit bien que
multiplication possède deux arguments : addition(5, 2) et 10.
addition possède deux arguments : 5 et 2.
En Python, les arguments des fonctions sont transmis via des parenthèses. Il existe des langages sans parenthèses pour les fonctions. On écrira ainsi juste :
e = multiplicationaddition 5 2 10
On voit ainsi que addition travaille avec 5 et 2 puisqu'il s'agit d'une fonction à deux arguments. De la même façon, l'interpréteur sera capable de comprendre que multiplication travaille avec les arguments addition 5 2 d'un côté et 10 de l'autre.
Si on remplace les noms des fonctions addition et multiplication par juste + et *, on obtient ceci :
e = *+ 5 2 10
Cela veut bien dire qu'on applique
+ sur 5 2
* sur + 5 2 et 10
Et bien voilà ce qu'est la notation polonaise inverse : on donne les opérateurs (dont on connait le nombre d'arguments, 2 ici) et leurs arguments sans parenthèse et... on écrit dans l'ordre inverse.
e = 10 2 5 +*
Utilisation de cette notation
Nous allons maintenant voir l'intérêt profond de cette notation : elle permet très facilement d'évaluer l'expression.
On lit l'expression de la gauche vers la droite.
Lorsqu'on obtient une valeur, on l'insère dans une Pile.
Lorsqu'on obtient un opérateur 2-aire, on dépile deux valeurs, on réalise le calcul et on empile le résultat dans la Pile.
Exemple avec e = 10 2 5 +*
e = 10 2 5 +*. On empile 10.
graph TD
C[10]
e = 10 2 5 +*.On empile 2.
graph TD
B[2] --> C[10]
e = 10 2 5+*. On empile 5.
graph TD
A[5] --> B[2] --> C[10]
e = 10 2 5 +*. On tombe maintenant sur un opérateur 2-aire +.
On dépile 5 puis 2 et on réalise le calcul 5 + 2 et on empile le résultat 7 dans la Pile.
graph TD
B[7] --> C[10]
e = 10 2 5 +*. On tombe maintenant sur un opérateur 2-aire *.
On dépile 7 puis 10 et on réalise le calcul 7 * 10 et on empile le résultat 70 dans la Pile.
graph TD
B[70]
10° Ecrire la formule (8 + 2) * 5 sous forme polonaire inverse.
...CORRECTION...
5 8 2 + *
Ou encore
8 2 + 5 *
11° Réaliser l'interprétation progressive de cette notation.
...CORRECTION...
5 8 2 + *
On empile 5, on empile 8, on empile 2.
graph TD
A[2] --> B[8] --> C[5]
5 8 2 + *
On tombe sur l'opérateur 2-aire +.
On dépile 2 et 8, on calcule 2+8 et on empile 10 dans la Pile.
graph TD
A[10] --> C[5]
5 8 2 + *
On tombe sur l'opérateur 2-aire *.
On dépile 10 et 5, on calcule 10*5 et on empile 50 dans la Pile.
graph TD
A[50]
12° Comment écrire sous forme parenthèsée normale la forme polonaire inversée 3 8 + 4 * ?
...CORRECTION...
(3 + 8) * 4
13° Réaliser l'interprétation progressive de 3 8 + 4 *.
...CORRECTION...
3 8 + 4 *.
On empile 3, on empile 8 puis on récupère + : on dépile 8 et 3, puis on calcule 3 + 8 = 11 qu'on empile dans la Pile.
3 8 +4 *.
On empile ensuite 4 puis on récupère * : on dépile donc le 4 et le 11, on calcule 4*11 et on empile 44.
Maintenant que vous avez vu la PILE et la récursivité, vous voyez pourquoi on présente souvent les appels récursifs de cette façon
Une pile d'exécution qui se remplit progressivement.
Et le schéma global de l'empilement et du dépilement :
14° En se basant sur l'empilement-dépilement des fonctions, une fois qu'on a dépilé une fonction qui répond, comment savoir à qui transmettre la réponse ?
Les processeurs gèrent naturellement les piles car une partie de la mémoire est gérée de cette façon. On y empile les données et le processeur ne retient que l'adresse de la dernière donnée rentrée.
Sur le processeur d'architecure X86, le registre qui contient l'adresse du registre stockant l'adresse du sommet de la pile d'exécution se nomme ESP.
Qu'est-ce qu'un Stack Overflow ?
PILE en français, STACK en anglais
On notera que la traduction anglaise de pile est STACK.
Cette pile dispose d'une certaine taille limite en mémoire.
Qu'est-ce que l'erreur de stack overflow ?
C'est l'erreur provoquée par le fait de vouloir continuer à empiler des éléments dans votre pile alors qu'on a atteint la taille mémoire limite qu'on lui a attribué. Pour stocker le nouvel élément, il faudrait donc écraser des données hors de la mémoire légalement attribuée à la pile !
Activité publiée le 04 10 2020
Dernière modification : 25 10 2020
Auteur : ows. h.
