Pile - TD Cours et applications simples
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 la tâche qu'on lui demande.
Plutôt que d'utiliser le couteau-suisse LISTE, nous allons voir qu'on peut utiliser un outil spécialisé PILE ou FILE.
Aujourd'hui, on voit la PILE.
1 - La Pile en tant que type abstrait de données
Nous allons voir ici qu'on peut travailler sur des données organisées de façon purement théorique, répondant à des contraintes théoriques, sans se soucier de la façon dont elles vont être concrétement programmées en interne par votre programme.
Pile, comme pile d'assiettes en gros : on ne peut prendre que l'assiette au sommet et si on en rajoute une, ce sera aussi au sommet.
Définition du type abstrait de données PILE
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 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
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.
Exemple
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
- Mais en réalité, nous allons plutôt la représenter ainsi, car c'est très proche de l'idée même d'une pile d'assiette ou d'une pile de livre :
5 Sommet
2
7
9
Fonctions d'interface pour une PILE
Les fonction d'interface définissent l'interaction basique qu'un utilisateur doit pouvoir effectuer avec les données si elles sont du type abstrait considéré.
On les nomme également fonctions primitives ou opérations fondamentales ou même primitives tout court.
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 donner 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, cela pourrait donner isNil(). - empiler(elt:Elt, p:Pile) -> Pile : on renvoie une pile en rajoutant l'élément elt au sommet p.
En anglais, ça se nomme push().
Nous verrons qu'on considère qu'une bonne implémentation de PILE réalise ceci à coût constant (𝞗(1)) - depiler(p:Pile) -> 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.
En anglais, ça se nomme pop().
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 nomme peek() ou top()
Point important mais plein de subtilité
Une PILE c'est donc une LISTE définie avec l'interface "stricte" que ne gère que la tête ?
Non, pas vraiment.
Dans l'idée, la PILE se distingue de la LISTE par le fait qu'on sait 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 un élément ailleurs qu'au sommet (de façon régulière).
C'est comme la pile d'assiettes : si vous savez que vous allez devoir les trier ou les classer 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. 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 liberée.
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 ? On peut se le demander. Voici la réponse :
La LISTE est plus polyvalente qu'une PILE mais lorsqu'on va implémenter réellement la PILE en machine, nous allons pouvoir optimiser son code : pas besoin de créer un code complexe qui gère les insertions et les lectures dans les données. Il devrait donc être plus rapide car moins complexe.
Et si on veut lire les éléments de la PILE à titre exceptionnel ?
Ce n'est pas grave. Si cette situation n'arrive que de façon exceptionnelle, cette action rare risque d'être plus longue qu'avec une LISTE mais, en moyenne, le programme restera plus performant que si on avait utilisé une LISTE.
Et si je dois faire cela souvent sur ma PILE ?
Là, c'est que vous auriez dû travailler sur le type abstrait LISTE.
Accès courant en lecture ou en modification d'un élément quelconque : prendre une LISTE sous forme d'un TABLEAU-LISTE CONTIGUË.
Insertion ou concaténation courante dans les données : prendre une LISTE sous forme LISTE CHAINEE.
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)
5 Sommet
p1 ← empiler(7, p1)
7 Sommet
5
x ← lireSommet(p1)
7 Sommet
5
Aucun changement mais la variable x est affectée à la valeur 7.
p1 ← empiler(x, p1)
7 Sommet
7
5
p1 ← empiler(4, p1)
4 Sommet
7
7
5
p1 ← depiler(p1)
7 Sommet
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 :
3 Sommet
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.
Type mutable
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) -> 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 mutable p3 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.
Fonctions d'interface optionnelles
Les fonctions précédentes permettent de créer celles qui sont présentées ici. Selon les applications, nous en auront besoin ou pas, contrairement aux premières qui sont nécessaires pour manipuler les piles.
- taille(p:Pile) -> int : on renvoie le nombre d'éléments dans la Pile. Cela peut être pratique pour éviter de dépasser la taile limite (erreur de dépassement de la mémoire allouée à la pile, stack overflow en anglais, voir la FAQ).
- vider(p:Pile) -> Pile : on vide la pile. Pour une pile non-mutable, 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, ça se nomme clear(). - echanger(p:Pile) -> Pile : on inverse le sommet et l'élément juste en dessous.
En anglais, ça se nomme swap().
Nous allons devoir utiliser certaines de ces fonctions pour résoudre l'exercice suivant.
04° Imaginer un algorithme qui pourait gérer la réception et l'émission de paquets IP par un routeur utilisant une mise en mémoire des requêtes dans une pile unique. On considérera un routeur dont la pile ne peut contenir que 5 paquets IP. Le routeur doit pouvoir vider sa mémoire si il sature : de toutes manières, avec le protocole TCP, les paquets disparus seront émis à nouveau par l'émetteur.
Cela consiste donc à faire une alternance entre tentative de réception et tentative d'émission.
p ← nouvellePile()
TANT QUE routeur en marche
# A vous de faire une tentative de lecture
# A vous de faire une tentative d'émission
Fin du TANT QUE
C'est donc très rudimentaire et pas très efficace.
On considère les deux fonctions d'interface supplémentaires suivantes :
- on peut lire le paquet IP d'entrée avec la fonction lireEntree() -> PAQUET_IP.
- on peut traiter le routage d'un paquet IP avec la fonction routerPaquet(paquet:PAQUET_IP) -> None
...CORRECTION...
Sans multitâche et avec un processus unique et séquentiel, on peut imaginer plusieurs fonctionnements, aucun ne sera vraiment efficace car il faudra faire des choix et des priorités !
Ici, je fais le choix d'une tentative de réception (on considère que les données qui arrivent sont dans un buffer), une tentative d'émission.
p ← nouvellePile()
TANT QUE routeur en marche
paquet ← lireEntree() (on tente de recevoir)
SI paquet n'est pas VIDE
SI taille(p) < 5
p ← empiler(paquet, p)
SINON
p ← vider(p)
p ← empiler(paquet, p)
Fin du Si
Fin du Si
SI ( NON estPileVide(p) ) (si la pile n'est pas vide, on tente d'émettre)
paquet ← lireSommet(p)
p ← depiler(p)
routerPaquet(paquet)
Fin du Si
Fin du TANT QUE
Je suis parti ici sur le principe d'une liste non mutable : lire le sommet ne le supprime pas automatiquement de la pile. Du coup, il faut lire puis supprimer le sommet traité.
Il peut sembler bizarre de gérer les paquets avec une PILE, non ?
C'est vrai : ce n'est pas la bonne structure de données sur le principe : cela revient à traiter en priorité le paquet IP le plus récent ! Mais bon, ça peut être un concept viable en l'alliant avec TCP.
Nous verrons néanmoins dans les activités suivantes que les routeurs possèdent deux piles :
- une d'entrée pour les paquets qui arrivent et
- une de sortie pour les paquets qui doivent être envoyés.
Nous verrons que cette association de 2 PILES, bien utilisée, forme une FILE d'attente.
2 - Choix d'utilisation d'une pile
Gestion des parenthèses ouvertes-fermantes.
C'est un classique : on veut savoir si l'expression arithmétique (5*2)+((5+2)*6) est correctement parenthésée.
On transforme alors l'expression en ne gardant que les parenthèses : ()(()).
A chaque parenthèse, on rajoute la parenthèse dans la pile.
On utilise un compteur qui part de 0.
Si on rajoute une parenthèse ouvrante, on rajoute 1 au compteur.
Si on rajoute une parenthèse fermante, on diminue le compteur de 1.
Si le compteur devient négatif, c'est que l'expression n'est pas correctement formulée.
Si le compteur n'est pas nul une fois toutes les parenthèses insérées, c'est que l'expression n'est pas correctement formulée.
Un exemple de déroulé :
- ()(()) et un compteur à 0
- On insère la première parenthèse ()(()) et le compteur passe à 1.
- On insère la 2e parenthèse ()(()) et le compteur passe à 0.
- On insère la 3e parenthèse ()(()) et le compteur passe à 1.
- On insère la 4e parenthèse ()(()) et le compteur passe à 2.
- On insère la 5e parenthèse ()(()) et le compteur passe à 1.
- On insère la 6e parenthèse ()(()) et le compteur passe à 0.
05° Que donne la séquence suivante (()))() ?
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.
Comment faire ?
En plaçant dans une PILE les indices des parenthèse ouvrantes qu'on découvre.
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 dans une FILE d'attente.
Exemple avec l'expression arithmétique (5*2)+((5+2)*6).
On détecte une première parenthèse ouvrante à l'indice 0 : (5*2)+((5+2)*6).
- PILE des parenthèses d'ouverture : 0
- FILE des parenthèses : vide
On détecte une deuxième parenthèse (fermante) à l'indice 4 : (5*2)+((5+2)*6). On dépile la PILE et on rajoute le tuple (0,4) dans la FILE.
- PILE des parenthèses d'ouverture : vide
- FILE des parenthèses : (0,4)
On détecte une parenthèse (ouvrante) à l'indice 6 : (5*2)+((5+2)*6). On empile ce 6 dans la PILE.
- PILE des parenthèses d'ouverture : 6
- FILE des parenthèses : (0,4)
On détecte une parenthèse (ouvrante) à l'indice 7 : (5*2)+((5+2)*6). On empile ce 7 dans la PILE.
- PILE des parenthèses d'ouverture : 7 → 6
- FILE des parenthèses : (0,4)
On détecte une parenthèse (fermante) à l'indice 11 : (5*2)+((5+2)*6). On dépile la PILE et on rajoute le tuple (7,11) dans la FILE.
- PILE des parenthèses d'ouverture : 6
- FILE des parenthèses : (7,11) → (0,4)
On détecte une parenthèse (fermante) à l'indice 14 : (5*2)+((5+2)*6). On dépile la PILE et on rajoute le tuple (6,14) dans la FILE.
- PILE des parenthèses d'ouverture : vide
- FILE des parenthèses : (6,14) → (7,11) → (0,4)
06° Que donne la séquence suivante (5*((5+9)+3)) ?
3 - Récursivité
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 :
4 - FAQ
Un peu d'architecture ?
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 25 09 2022
Dernière modification : 25 09 2022
Auteur : ows. h.
Modification : Andjekel