Pour beaucoup d'applications, les insertions et les suppressions se font du même côté des données : la gestion du bouton "Reculer d'une page" dans les navigateurs Web par exemple.
Voyons une structure linéaire spécialisée dans cette tâche : la Pile.
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 linéaire 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
Les primitives font partie des fonctions de base disponibles pour ce type abstrait de données.
En utilisant les primitives, on doit pouvoir construire toutes les autres fonctionnalités voulues.
Les futures implémentations des primitives devront donc avoir le coût le plus faible possible (puisqu'elles sont utilisées par les autres fonctionnalités).
C - Les primitives d'une Pile
nouvellePile() -> Pile VIDE : on crée une nouvelle pile vide. On pourra l'identifier à () par exemple.
newStack() en anglais.
estPileVide(p:Pile) -> bool ou juste estVide() : renvoie un booléen qui vaut True si la pile p transmise est une pile vide.
isEmpty() en anglais.
empiler(elt:Elt, p:Pile) -> Pile NON VIDE : on renvoie une pile en rajoutant l'élément elt au sommet p.
push() en anglais.
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.
pop() en anglais.
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.
peek() ou top() en anglais
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'accède qu'au sommet.
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/mutable
Pour les implémentations qui utilisent une structure muable/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 primitives 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 Fonctions optionnelles
Les primitives précédentes permettent 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) -> Rien en muable : on vide la pile. 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. Pour une pile immuable, on suffit de créer une pile vide.
clear() en anglais.
echanger(p:Pile DE DEUX ELEMENTS AU MOINS) -> Pile DE DEUX ELEMENTS AU MOINS en immuable
echanger(p:Pile DE DEUX ELEMENTS AU MOINS) -> Rien en muable
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 en considérant une Pile immuable (vous avez donc droit à POUR, TANT QUE, SI, SINON SI, SINON et aux variables) :
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 suivantes en considérant une Pile mutable :
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[Parenthèse d'ouverture a]
On tombe sur une parenthèse de fermeture : ()(()). On dépile puisque la pile n'est pas vide.
graph TD
V[Pile vide]
On tombe sur une ouverture : ()(()). On empile cette ouverture.
graph TD
A[Parenthèse d'ouverture b]
On tombe sur une ouverture : ()(()). On empile cette ouverture.
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
V[Pile vide]
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 dans cet ordre
entre les indices 0 et 4, puis
entre 7 et 11, puis
entre 6 et 14, et finalement
il pourra alors évaluer l'expression entre 0 et 14.
07° Fournir les différentes étapes d'évolution de la pile et du tableau lorsqu'on applique cette méthode sur l'expression suivante (5*((5+9)+3)).
08° (Rédaction) Si on transforme la notion de parenthèses ouvrantes-fermantes en balises ouvrantes-fermantes, n'importe quelle balise fermante est-elle compatible avec n'importe quelle balise ouvrante ? Comment valider une page HTML dont les balises sont fournies dans cet ordre ? Fournir l'algorithme permettant de répondre par Oui ou Non à la question de la bonne structure d'une page HTML.
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 polonaise 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 polonaise 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 ?
CONCLUSION : point important et subtil
Une Pile est-elle simplement 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 sait qu'on ne va pas lire régulièrement un élément autre que le sommet. De la même façon, on ne va pas avoir besoin d'insérer régulièrement ailleurs qu'au sommet.
Nous n'allons donc pas chercher à optimiser les accès internes.
Regardons l'exemple des assiettes :
Si vous devez trier les assiettes de la moins sale à la plus sale, autant les poser les unes à côté des autres sur la table : vous utilisez une Liste.
Sinon, on peut les empiler : c'est une Pile.
Quel est l'intérêt ?
La Liste est plus polyvalente qu'une Pile mais elle est plus complexe et elle est donc souvent moins rapide : 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 ?
Ok si c'est rare.
Et si je dois souvent lire l'intérieur de ma Pile ?
Les performances seront mauvaises. Vous auriez dû travailler avec une Liste !
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.
