La notion de pile

Cette structure de pile est utilisée pour plein de problèmes en informatique.

Définition d'une pile

En informatique, une pile est une structure de données qui est définie par les opérations suivantes :

• On peut créer une pile vide
• On peut ajouter un élément au sommet de la pile (empiler)
• On peut enlever l'élément au sommet de la pile et avoir son contenu (dépiler)
• On peut savoir si une pile est vide

La représentation concrête correspondant à cette notion informatique est la pile d'assiette. Vous ajoutez les assiettes sur le dessus de la pile, et vous dépiler à partir du sommet de la pile.

Implémenter une pile en programmation objet

La programmation objet peut nous permette d'implémenter des piles assez facilement. Nous allons avoir besoin pour cela de définir deux classes. Tout d'abord une classe pour chaque élément de la pile, que l'on appellera la cellule. Cette classe comprend deux attributs : le contenu et l'élément suivant. Si il n'y a pas d'élément suivant, c'est None. La définition de la cellule sera très simple. Il y a besoin de deux attributs :

• le contenu, qui sera donné comme paramètre à la création
• le suivant, qui sera défini à None à la création

class cellule:
    """ Classe qui modélise une cellule dans une structure linéaire """
    def __init__(self,element):
        self.contenu = element
        self.suivant = None

Cette classe peut être schématisée avec le schéma ci-dessous

Une classe pour la pile elle même, qui comprend un seul attribut : le sommet de la pile, qui est None si la pile est vide, et une cellule sinon. Outre l'initialisation, la classe pile implémentera les méthodes suivantes :

• estVide() qui retourne un booléen valant True si la pile est vide, False sinon
• empiler(element) qui empile un élement au sommet de la pile
• depiler() qui enleve le sommet de la pile et renvoi son contenu

On peut schématiser l'initialisation, l'empilement et le dépilement avec la figure ci-dessous

Le code de base de la classe pile, pour l'initialisation, sera simple

class pile:
    """ Classe qui implémente une pile"""
    def __init__(self):
        self.sommet = None

La méthode qui permet de savoir si la pile est vide est assez évidente à écrire

    def estVide(self):
        return self.sommet == None

La méthode pour empiler un élément s'appuye sur la classe cellule. On crée la cellule. Le suivant de la nouvelle cellule est ce qui correspond au sommet actuel de la pile. Puis le sommet de la pile est mis sur la cellule

  def empile(self,element):
        nouveau = cellule(element)
        nouveau.suivant = self.sommet
        self.sommet = nouveau

Pour dépiler, on doit mémoriser le contenu du sommet, puis renvoyer ce contenu à la fin. On doit aussi mettre le pointeur du sommet sur le suivant du sommet actuel

    def depile(self):
        valeur = self.sommet.contenu
        self.sommet = self.sommet.suivant
        return valeur

En pratique

Nous avons maintenant défini un classe complête pour une pile. Nous allons pouvoir tester notre classe. Ouvrez l'éditeur Python en cliquant sur le bouton ci dessous et exécutez les consignes. Pour faciliter le travail, une méthode affiche() a été ajoutée, qui permet d'afficher le contenu de la pile, en partant du sommet.

Exemple d'utilisation d'une pile : la pile d'exécution

Il y a un domaine où la pile est utilisée en informatique : la pile d'éxécution. Lorsqu'un programme s'exécute, c'est le corps principal du programme qui s'exécute. Dès qu'il appelle une fonction, l'état du programme est préservé, et la fonction appellée est positionnée dans la pile d'éxécution. Cette fonction peut elle même en appeler une autre et ainsi de suite. Lorsque la fonction a fini, elle est dépilée de la pile d'éxécution et le programme retourne là où il était au moment de l'appel. La vidéo ci ci-dessous illustre la notion de pile d'éxécution dans le cadre d'une fonction récursive