Données Pile

Identification

Infoforall

15 - type abstrait Pile LIFO


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.

Documents de cours : open document ou pdf

Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)

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
Un empilement possède un sommet
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.

LIFO

Exemple

Trois façons de voir graphiquement une pile contenant un sommet valant 5 suivi du reste de la pile.

  • 5279
  • 9725
  • 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.

Principe de l'interface d'une pile
  1. nouvellePile() -> Pile : on crée une nouvelle pile vide. On pourra l'identifier à (). En anglais, cela pourrait donner newStack.
  2. estVide(p:Pile) -> bool : renvoie un booléen qui vaut True si la pile p transmise est une pile vide. En anglais, cela pourrait donner isNil ou isNull.
  3. 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. On considère qu'une bonne implémentation réalise ceci à coût constant (θ(1))
  4. depiler(p:Pile) -> Pile  : on supprime le sommet et renvoie la nouvelle pile p. En anglais, ça se nomme pop. 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)).
  5. 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 qui ne soit pas le sommet et qu'on ne va pas non plus avoir besoi n régulièrement d'insérer un élément ailleurs qu'au sommet.

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, l'action risque d'être plus longue qu'avec une LISTE (qui elle est faite pour ça) 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.

Insertion 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 :

    p1nouvellePile()

    p1empiler(5, p1)

    p1empiler(7, p1)

    xlireSommet(p1)

    p1empiler(x, p1)

    p1empiler(4, p1)

    p1depiler(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.

    p1nouvellePile()

    La variable p1 est une pile vide.

    p1empiler(5, p1)

    5 Sommet

    p1empiler(7, p1)

    7 Sommet

    5

    xlireSommet(p1)

    7 Sommet

    5

    Aucun changement mais la variable x est affectée à la valeur 7.

    p1empiler(x, p1)

    7 Sommet

    7

    5

    p1empiler(4, p1)

    4 Sommet

    7

    7

    5

    p1depiler(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...

    p2nouvellePile()

    p2empiler(1, p2)

    p2empiler(2, p2)

    p2empiler(3, p2)

    xlireSommet(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 et qui renvoie le sommet qu'on vient de supprimer.

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.

    p3nouvellePile()

    empiler(5, p3)

    empiler(7, p3)

    xdepiler(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.

    p3nouvellePile()

    La variable p3 est une pile vide.

    empiler(5, p3)

    5

    empiler(7, p3)

    7

    5

    xdepiler(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. Dans ce cas précis, un pile mutable est préférable... 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. On est déjà à la limite limite de l'utilisation d'une PILE puisqu'on accède au second élément.

Nous allons devoir utiliser certaines de ces fonctions pour résoudre l'exercice suivant.

04° Imaginer l'algorithme gérant la réception et l'émission de paquets IP par un routeur utilisant une mise en mémoire des requêtes via 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. Processus monotâche, pas d'interruption. Rudimentaire, rudimentaire, tout en séquentiel.

On considère qu'on peut lire le paquet IP d'entrée avec la fonction lireEntree() -> PAQUET_IP et qu'on peut traiter le routage d'un paquet IP avec la fonction routerPaquet(paquet:PAQUET_IP) -> None

Le schéma du routeur avec l'entrée et la sortie

...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.

    pnouvellePile()

    TANT QUE routeur en marche

      paquetlireEntree()

      SI paquet IP n'est pas VIDE

        SI taille(p) < 5

          pempiler(paquet, p)

        SINON

          pvider(p)

          pempiler(paquet, p)

        Fin du Si

      Fin du Si

      SI taille(p) > 0

        paquetlireSommet(p)

        pdepiler(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 ?

Nous verrons dans les activités suivantes que les routages peuvent possèder 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

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 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.

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.

La pile avec f(5) à f(0)

Et le schéma global de l'empilement et du dépilement :

Empilement et 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 04 10 2020
Dernière modification : 25 10 2020
Auteur : ows. h.