Introduction à la structure de données « pile »

Une pile est une structure de données linéaire qui suit le principe LIFO (Last In, First Out), ce qui signifie que le dernier élément ajouté est le premier à être retiré.

La pile fonctionne comme une pile d'assiettes dans un restaurant : on ajoute les nouvelles assiettes par le haut, et on les retire aussi par le haut.

Opérations fondamentales d’une pile

push(x) : ajoute un élément x au sommet de la pile.
pop() : retire et renvoie l’élément au sommet.
peek() ou top() : affiche l’élément au sommet sans le retirer.
is_empty() : retourne un booléen indiquant si la pile est vide.

Implémentation en Python

Voici une implémentation simple d'une pile en Python à l’aide d’une liste :

class Pile:
    def __init__(self):
        self.elements = []

    def push(self, x):
        self.elements.append(x)

    def pop(self):
        if self.is_empty():
            raise IndexError("La pile est vide")
        return self.elements.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("La pile est vide")
        return self.elements[-1]

    def is_empty(self):
        return len(self.elements) == 0

Exemple d’utilisation

ma_pile = Pile()
ma_pile.push(10)
ma_pile.push(20)
print(ma_pile.pop())   # Affiche 20
print(ma_pile.peek())  # Affiche 10

Exemple d'application: Vérification des parenthèses équilibrées

Cet exemple montre comment utiliser une pile pour valider l’équilibre des parenthèses dans une expression :

def parenthèses_équilibrées(expression):
    pile = Pile()
    correspondance = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in "([{":
            pile.push(char)
        elif char in ")]}":
            if pile.is_empty() or pile.pop() != correspondance[char]:
                return False
    return pile.is_empty()

# Tests
print(parenthèses_équilibrées("({[]})"))  # True
print(parenthèses_équilibrées("([)]"))    # False

Avantages et limites des piles

Avantages

Structure simple à implémenter.
Rapidité : les opérations push et pop s’exécutent en temps constant O(1).

Limites

Taille fixe si elle repose sur un tableau statique.
Non adaptée aux recherches complexes ou aux modifications internes.
Accès limité uniquement à l’élément du sommet.

Les piles

All work licensed under CC BY-NC-SA 4.0