Aller au contenu

📚 La pile⚓︎

Rappels sur le tableau⚓︎

Exemple de tableau : les nombres premiers inférieurs à 100.

Indice \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\) \(11\) \(12\) \(13\) \(14\) \(15\) \(16\) \(17\) \(18\) \(19\) \(20\) \(21\) \(22\) \(23\) \(24\)
Élément \(2\) \(3\) \(5\) \(7\) \(11\) \(13\) \(17\) \(19\) \(23\) \(29\) \(31\) \(37\) \(41\) \(43\) \(47\) \(53\) \(59\) \(61\) \(67\) \(71\) \(73\) \(79\) \(83\) \(89\) \(97\)

Avec Python

premiers_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Un tableau est une structure de données, abstraite et élémentaire :

  • avec des éléments de même type, et de même taille taille_élément,
  • un nombre d'éléments fixé à la création ; nb_éléments,
  • rangés de façon continue en mémoire, indicés de 0 inclus à nb_éléments exclu.

En interne, on accède, en pratique, à un élément d'indice i du tableau par son adresse mémoire qui est égale à adresse_tableau + i * taille_élément.

On peut lire et modifier un élément d'indice i. Avec un langage de programmation, on note très souvent masses[i] cet élément de masses d'indice i.

Avec cette structure de données, on a déjà résolu de nombreux problèmes, mais on peut aussi construire de nouvelles structures de données.

Concrètement, on retrouve des implémentations de cette structure abstraite, le tableau, dans la plupart des langages de programmation. Une limitation évidente est la taille d'un tableau, limitée par la capacité de mémoire disponible ; sinon, c'est assez simple.

Tableau et Python

Les objets de type list en Python ne sont pas des tableaux. On peut faire d'autres opérations. Mais si on se restreint à la création, l'accès en lecture et écriture à un élément dont l'indice est donné, alors c'est un tableau. En exercice, on pourra imposer de travailler comme avec un tableau, pour justement créer de nouvelles méthodes.

La pile⚓︎

On utilisera les notations de la POO.

  • La pile est une structure abstraite de données, linéaire (possiblement agencée en ligne en mémoire).
  • Les éléments sont de même type.
  • On dispose de méthodes :
    • Le constructeur Pile(), via la méthode .__init__(self) qui initialise une pile vide.
    • .est_vide(self) renvoie un booléen, True pour une pile vide après sa construction.
    • .empile(self, élément) ajoute un élément au sommet de la pile.
    • .dépile(self) enlève l'élément au sommet de la pile, et le renvoie.
    • Éventuellement d'autres méthodes...

Image : wikipedia, la pile

Implémentation avec tableau⚓︎

On propose ici, en Python, une implémentation qui utilise en arrière-plan une structure de type list de Python, mais en limitant volontairement l'usage, comme un tableau, sans méthode dynamique. Ainsi l'implémentation pourrait être réalisée dans de nombreux langages de programmation avec de rares ajustements.

La limitation, ici, sera que les éléments de la pile devront être de même type, et de même taille.

class Pile():
    """
    Une classe pile, de taille maximale 'taille_max',
    implémentée avec les données dans un tableau.
    """

    def __init__(self, taille_max: int):
        self.taille_max = taille_max
        self.données = [None] * taille_max  # un tableau
        self.taille = 0

    def est_vide(self) -> bool:
        return self.taille == 0

    def empile(self, élément):
        """Ajoute `élément` au sommet de la pile.
        """
        if self.taille == self.taille_max:
            raise ValueError('Pile pleine')
        self.données[self.taille] = élément
        self.taille += 1

    def dépile(self):
        """Enlève et renvoie l' `élément` du sommet de la pile.
        """
        if self.est_vide():
            raise ValueError('Pile vide')
        self.taille -= 1
        élément = self.données[self.taille]
        self.données[self.taille] = None  # optionnel
        return élément

if __name__ == '__main__':
    # tests
    test = Pile(256)  # taille de 256 éléments

    # test est_vide
    assert test.est_vide()

    # test un empile/dépile
    test.empile(42)
    élément = test.dépile()
    assert élément == 42
    assert test.est_vide()

    # test plusieurs empile / puis plusieurs dépile
    premiers = [2, 3, 5, 7, 11]

    for élément in premiers:
        test.empile(élément)
    assert [test.dépile()
            for _ in range(len(premiers))] == premiers[::-1]
    assert test.est_vide()

On pourrait ajouter une méthode .__str__(self).

    def __str__(self) -> str:
        """Pour usage interne, tests.
        """
        ans = "[Sommet de la pile] -> "
        for i in range(self.taille-1, -1, -1):
            ans += str(self.données[i])
            if i != 0:
                ans += ", "
        ans += "[Bas de la pile]"
        return ans

Exercice 1

Idéalement, il faudrait écrire les attributs taille_max, taille et données en les préfixant de __ pour les rendre privés.

Faire cela et justifier ce choix.

Exercice 2

Ajouter une méthode accesseur .taille(self). Cela donnerait une raison de plus d'avoir préfixé l'attribut !

Exercice 3

Vérifier l'utilisation avec le code suivant.

ma_pile = Pile(100)
for x in range(20):
    ma_pile.empile(x*x + 2)
print(ma_pile)

for i in range(11):
    print("valeur dépilée :", ma_pile.dépile())

print("Et ensuite")

print(ma_pile)

ma_pile.empile(1337)

print(ma_pile)

print(dir(ma_pile))
  • Tester 2000 au lieu de 20.
  • Tester 31 au lieu de 11.
  • Repérer et justifier, où dans le code on gère ces erreurs.

Implémentation avec les listes dynamiques de Python⚓︎

On peut facilement implémenter une pile de taille arbitraire avec le type list de Python et ses méthodes .append(self, élément) et .pop(self). Tous les langages de programmation ne le permettent pas aussi facilement...

class Pile():
    def __init__(self):
        self.données = []

    def __str__(self) -> str:
        return str(self.données)

    def est_vide(self) -> bool:
        return self.données == []

    def empile(self, valeur):
        self.données.append(valeur)

    def dépile(self):
        if self.est_vide():
            raise ValueError('Pile vide')
        return self.données.pop()

if __name__ == '__main__':
    # tests
    test = Pile()

    # test est_vide
    assert test.est_vide()

    # test un empile/dépile
    test.empile(42)
    élément = test.dépile()
    assert élément == 42
    assert test.est_vide()

    # test plusieurs empile / puis plusieurs dépile
    premiers = [2, 3, 5, 7, 11]

    for élément in premiers:
        test.empile(élément)
    assert [test.dépile()
            for _ in range(len(premiers))] == premiers[::-1]
    assert test.est_vide()

Pas de taille ?

On remarque que nous n'avons pas ici besoin de méthode ni d'attribut taille... Pour le type abstrait pile, on travaille sans l'avoir disponible au départ.

Exercice 4

Rendre l'attribut données privé et ajouter une méthode .taille(self).

Refaire les tests vus précédemment.

Exercice 5

Résoudre le problème Dates de péremption sur France-IOI.

Réponse

Corrigé détaillé

Exercice 6

Pour cet exercice, on supposera qu'on ne dispose que du constructeur Pile() d'une pile vide, ainsi que des méthodes .est_vide(self), .empile(self, élément) et .dépile(self).

Question 1

Que fait la méthode mystère suivante ? Donner un vrai nom et une doctring. On testera à la main sur l'exemple simple : - sommet de la pile \(\rightarrow 4, 6, 3, 9, 7 |\).

    # suite de class Pile():
    def mystère(self):
        autre = Pile()
        while not self.est_vide():
            autre.empile(self.dépile())
        return autre
Réponse
    # suite de class Pile():
    def renverse(self):
        """Renvoie une version renversée de la pile self, tout en la vidant.
        """
        autre = Pile()
        while not self.est_vide():
            autre.empile(self.dépile())
        return autre

Question 2

Proposer alors une méthode .taille(self)-> int qui renvoie la taille d'une pile, en la laissant inchangée en fin de compte. Rappel : on ne dispose pas du détail d'implémentation, et on ne peut donc pas utiliser len ; d'ailleurs sur quel objet ?!?

Réponse

On va renverser deux fois la pile et compter lors d'un des deux renversements combien d'éléments sont présents.

    # suite de class Pile():
    def taille(self) -> int:
        """Renvoie la taille de la pile,
        en la laissant intacte *in fine*.
        """
        taille = 0
        autre = Pile()
        while not self.est_vide():
            autre.empile(self.dépile())
            taille += 1
        while not autre.est_vide():
            self.empile(autre.dépile())
        return taille

Question 3

Proposer une méthode .max_pile(self, i: int) -> int qui renvoie la (plus petite) position de l'élément maximal parmi les i derniers empilés (s'ils existent). La position du sommet de la pile est, par convention ici, égale à \(1\). La pile doit être inchangée en fin de compte.

Réponse
    # suite de class Pile():
    def max_pile(self, i: int) -> int:
        """Renvoie la (plus petite) position de l'élément maximal parmi
        les `i` derniers empilés.
        La position du sommet de la pile est,
        par convention ici, égale à $1$.
        """
        # version où il y a au moins i>1 éléments, garantis dans self
        # c'est plus simple
        autre = Pile()
        pos = pos_max = 1
        maxi = self.dépile()
        autre.empile(maxi)
        for _ in range(i - 1):
            truc = self.dépile()
            pos += 1
            if truc > maxi:  # > est important, >= est faux
                maxi = truc
                pos_max = pos
            autre.empile(truc)
        for _ in range(i):
            self.empile(autre.dépile())
        return pos_max

Si on place >= au lieu de >, alors on renvoie la plus grande position du maximum.

Question 4

Proposer une méthode .retourner(self, i: int) -> None qui modifie la pile en inversant l'ordre des i derniers éléments empilés (s'ils existent). On peut utiliser deux piles auxiliaires.

Réponse

On dépile \(i\) éléments, que l'on inverse dans une seconde pile pour la remettre enfin dans self.

    # suite de class Pile():
    def retourner(self, i: int) -> None:
        """Modifie la pile en inversant l'ordre des
        `i` derniers éléments empilés.
        """
        autre = Pile()
        for _ in range(i):
            autre.empile(self.dépile())
        autre_bis = Pile()
        for _ in range(i):
            autre_bis.empile(autre.dépile())
        for _ in range(i):
            self.empile(autre_bis.dépile())

Implémentation de façon récursive⚓︎

Gardons à l'esprit qu'un programme n'a pas une vue d'ensemble d'une pile. Il ne voit que le sommet ; en effet l'accès lui est aisé, moins pour le reste. On peut alors considérer une pile comme étant :

  • Soit une pile vide.
  • Soit un sommet que l'on nomme souvent tête, et le reste caché qui est ... une pile (vide ou non), que l'on nomme souvent queue.

On devine alors une définition récursive d'une pile :

  • Pile vide, ou alors
  • un couple (tête, queue)
    • tête est un élément,
    • et queue une autre pile.

Dans l'implémentation ci-dessous, on choisit :

  • None pour la pile vide,
  • sinon, le tuple (tête, queue).
class Pile():
    def __init__(self, données=None):
        self.__données = données

    def est_vide(self):
        return self.__données is None

    def empile(self, élément):
        queue = self.__données
        tête = élément
        self.__données = (tête, queue)

    def dépile(self):
        if self.est_vide():
            raise ValueError('Pile vide')
        tête, queue = self.__données
        self.__données = queue
        return tête

if __name__ == '__main__':
    # tests
    test = Pile()

    # test est_vide
    assert test.est_vide()

    # test un empile/dépile
    test.empile(42)
    élément = test.dépile()
    assert élément == 42
    assert test.est_vide()

    # test plusieurs empile / puis plusieurs dépile
    premiers = [2, 3, 5, 7, 11]

    for élément in premiers:
        test.empile(élément)
    assert [test.dépile()
            for _ in range(len(premiers))] == premiers[::-1]
    assert test.est_vide()

On aurait pu écrire la méthode empile en une seule ligne avec self.__données = (élément, self.__données), mais c'est moins lisible, et moins pédagogique.

Attention : ici nous avons en structure interne une pile qui est soit None, soit un tuple qui n'a que deux éléments, et de types différents. Nous nous l'étions interdit pour les listes ! Acceptons l'idée qu'il s'agit en réalité de deux adresses. L'adresse de l'élément tête puis celle de queue.

Voilà un exemple de la représentation interne de cette pile :

(31, (12, (55, (20, None))))

  • Ici le sommet (la tête) de la pile est 31.
  • Et le reste (la queue) est la pile (12, (55, (20, None))

Nous reviendrons sur cette construction, c'est une bonne méthode pour construire la structure de type liste chainée ; oui, ça vient ensuite !

L'intérêt de ce genre de définition est qu'il est très commode de construire d'autres méthodes qui se prêtent bien à la récursivité. Par exemple :

    def taille(self) -> int:
        "Renvoie la taille de la pile"
        if self.est_vide():
            return 0
        tête, queue = self.__données
        return 1 + Pile(queue).taille()

Dit autrement : la taille d'une pile, c'est zéro si la pile est vide, sinon, c'est un, plus, la taille de la pile qui est sous l'élément au sommet.

Exercice 1

Proposer une méthode récursive qui renvoie la somme des valeurs d'une telle pile, en supposant qu'il ne s'agisse que de nombres entiers.

Réponse
    def somme(self):
        "Renvoie la somme de la pile"
        if self.est_vide():
            return 0
        tête, queue = self.__données
        return tête + Pile(queue).somme()

Exercice 2

Proposer une méthode récursive .contient_valeur(self, valeur) qui renvoie un booléen, True si un élément possède une certaine valeur, et False sinon.

Réponse
    def contient_valeur(self, valeur) -> bool:
        "valeur est-elle dans la pile ?"
        if self.est_vide():
            return False
        tête, queue = self.__données
        return tête == valeur or Pile(queue).contient_valeur(valeur)

Valeur ≠ élément

On rappelle au passage un point technique, la différence entre élément et valeur. Regardons l'exemple ci-dessous.

>>> 2 == 2.0 # même valeur ?
True
>>> 2 is 2.0 # même élément ?
False

On fera attention :

  • Souvent on vous demandera si un objet contient un élément d'une certaine valeur ; on pourra utiliser un test d'égalité de valeur ==.

  • Parfois on vous demandera s'il contient un élément. Dans ce second cas, il faudra utiliser le test d'identité is, et non le test d'égalité de valeur ==.

Pour aller plus loin

Un autre intérêt de cette présentation est son approche d'un style de programmation, le filtrage par motif (pattern matching).

Remarque

Cette façon de faire n'est pas idéale. On aimerait pouvoir obtenir une véritable pile dans queue et non juste ses données lorsqu'on fait :

        tête, queue = self.__données
On est ensuite obligé de d'utiliser avec Pile(queue). Avec d'autres langages de programmation, comme Ocaml, il est possible avec du filtrage par motifs d'écrire cette abstraction de manière bien plus naturelle.

Essayons encore avec Python.

class Pile():
    # Ce code est incorrect !!!
    def __init__(self):
        self.pile = None

    def est_vide(self):
        return self.pile is None

    def empile(self, élément):
        self.pile = (élément, self)  # ici !!!

    def __str__(self):
        if self.est_vide():
            return ""
        tête, queue = self.pile
        return str(tête) + "::" + queue.__str__()

    def taille(self):
        if self.est_vide():
            return 0
        tête, queue = self.pile
        return 1 + queue.taille()

Ce code est incorrect ; à la ligne commentée # ici !!!, on a self qui fait référence à lui-même dans son état actuel, mais aussi futur après l'affectation.

On verra comment contourner ce problème avec l'utilisation de deux classes. Ce sera une introduction aux listes chainées.

Cependant, cette construction se retrouve avec d'autres langages de programmation comme avec OCaml, où on retrouve du code comme :

let rec taille pile = match pile with
        | [] -> 0
        | tete :: queue  -> 1 + (taille queue)

Ce code se lit :

Définissons par récurrence, une fonction taille pour un paramètre pile par :

Suivant que pile est :

  • soit une liste vide ; on renvoie zéro,
  • soit une tête suivie d'une queue ; on renvoie 1 (la taille de la tête), plus la taille de la queue déterminée par récurrence.

On voit là tout l'intérêt de pouvoir définir une structure de données récursive et d'utiliser le filtrage par motif.

Utilisations concrètes⚓︎

  • Lors d'appels récursifs une pile d'appels est créée en mémoire.
  • Lors de l'utilisation d'un navigateur de recherche, la navigation est stockée dans une pile, pour permettre de revenir facilement en arrière.
  • Avec un éditeur de code, un traitement de texte ou bien un logiciel de traitement d'image, on peut annuler les dernières opérations ; elles sont stockées dans une pile.

Glossaire anglais - français⚓︎

push
c'est le terme qu'on retrouve le plus pour empiler, enfiler. On trouve aussi append avec Python.
pop
c'est le terme qu'on retrouve le plus pour dépiler, défiler.

Liens Wikipédia en anglais et en français pour ceux qui veulent aller plus loin :

English Français
data structure structure de données
array tableau
stack pile
queue file
pattern matching filtrage par motif
push empiler, ou enfiler
pop dépiler, ou défiler

List of data structures ; en anglais.

Retour en haut de la page