Piles

Généralités sur les piles

Une « pile » (ou « stack ») est une structure de données linéaire dans laquelle les éléments sont accessibles selon une méthode LIFO (« Last-In First-Out » en anglais) : l’élément inséré en dernier est le premier à sortir.

• Ajouter un élément dans la pile est appelé « empiler » (« push » en anglais).
• Supprimer un élément de la pile est appelé « dépiler » (« pop » en anglais).

L’accès aux objets de la pile se fait grâce à un unique pointeur vers le sommet de la pile, appelé « top ».

Vidéo sur les piles

Les piles par Foxxpy : Mathématiques et algorithmie (13:23)

Primitives

Voici les primitives communément utilisées pour manipuler des piles :

• « Empiler » : ajoute un élément sur la pile (« push » en anglais).
• « Dépiler » : enlève un élément de la pile et le renvoie. (« pop » en anglais).
• « La pile est-elle vide ? » : renvoie vrai si la pile est vide, faux sinon.
• « Nombre d'éléments de la pile » : renvoie le nombre d'éléments dans la pile. Selon les implémentations, peut être fait soit en temps constant soit en temps linéaire.
• « Quel est l'élément de tête ? » : renvoie l'élément de tête sans le dépiler (« peek » ou « top » en anglais).
• « Vider la pile » : dépiler tous les éléments. Selon l'implémentation, cela peut être fait en temps constant ou linéaire (« clear » en anglais).
• « Dupliquer l'élément de tête » et « échanger les deux premiers éléments » : existe sur les calculatrices fonctionnant en notation polonaise inverse (« dup » et « swap » respectivement en anglais).

Il n'existe pas de normalisation pour les primitives de manipulation de pile : leurs noms sont donc indiqués de manière informelle. Seules les trois premières sont réellement indispensables, les autres pouvant s'en déduire.

Exemple d'implémentation en Python

🐍 Editeur

class Pile:
    """Définit un objet de type Pile"""

    def __init__(self: object) -> None:
        """Constructeur"""
        self.tab = []  # Utilisation d'un tableau Python

    def __repr__(self: object) -> str:
        """Méthode pour afficher le contenu de la pile"""
        return str(self.tab)

    def est_vide(self: object) -> bool:
        """Méthode pour tester si la pile est vide"""
        return len(self.tab) == 0

    def depiler(self: object) -> int:
        """"Méthode pour dépiler le sommet de la pile"""
        if self.tab != []:
            return self.tab.pop()

    def empiler(self: object, n: int) -> None:
        """Méthode pour empiler un entier"""
        self.tab.append(n)


if __name__ == "__main__":
    p = Pile()
    p.empiler(1)
    p.empiler(3)
    p.empiler(5)
    p.empiler(2)
    print(p)
    p.empiler(7)
    print(p)
    print(p.depiler())
    print(p)

L'exécution de ce programme donne :

▶️ Console

>>>
[1, 3, 5, 2]
[1, 3, 5, 2, 7]
7
[1, 3, 5, 2]
>>>

Applications

• Les algorithmes récursifs utilisent une pile d'appel. Dans un langage non récursif (Fortran par exemple), on peut simuler la récursivité en créant les primitives de gestion d'une pile.
• Dans un navigateur web, une pile sert à mémoriser les pages Web visitées. L'adresse de chaque nouvelle page visitée est empilée et l'utilisateur dépile l'adresse courante pour accéder à la page précédente en cliquant le bouton « Afficher la page précédente ».
• L'évaluation des expressions mathématiques en notation post-fixée (ou polonaise inverse) utilise une pile.
• La fonction « Annuler la frappe » (en anglais « Undo » d'un traitement de texte mémorise les modifications apportées au texte dans une pile.
• Un algorithme de recherche en profondeur utilise une pile pour mémoriser les noeuds visités. Par exemple, on peut inverser un tableau ou une chaîne de caractères en utilisant une pile. Il suffit d'empiler les éléments sur une pile puis de reconstituer le tableau (ou la chaîne) inverse en dépilant les éléments.

Pile (animations en ligne)

Pile simple

Pile implémentée avec un tableau

Pile implémentée avec une liste chaînée

Utilisation d'une pile pour calculer

Calculatrice HP48G utilisant la Notation Polonaise Inverse