🥞 Les Piles (Stacks) et leur Utilisation

Imaginez une pile d'assiettes proprement empilées. Vous ajoutez des assiettes sur le dessus, et lorsque vous en avez besoin, vous retirez celle qui est tout en haut. C'est exactement ainsi que fonctionne une pile (stack) en informatique !

📚 Qu'est-ce qu'une Pile ?

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

Les opérations principales d'une pile sont :

• Push : Ajouter un élément au sommet de la pile.
• Pop : Retirer l'élément au sommet de la pile.

🛠️ Quand et Où Utilise-t-on une Pile ?

Les piles sont omniprésentes en informatique et sont utilisées dans de nombreux scénarios :

• 📝 Annulation d'actions : Comme dans un éditeur de texte avec la fonction "Annuler" (Ctrl + Z).
• 🌐 Historique de navigation : Les pages visitées sont empilées pour permettre de revenir en arrière.
• 🧮 Évaluation d'expressions : Conversion et calcul d'expressions mathématiques.
• 🔍 Parcours de graphes : Utilisé dans l'algorithme de parcours en profondeur (DFS).
• 💻 Gestion des appels de fonctions : La pile d'appels gère l'ordre des fonctions appelées.

📊 Analyse de Complexité

Les opérations sur une pile sont très efficaces :

💻 Implémentation en Python

Voici comment implémenter une pile en Python :

class Stack:
    def __init__(self):
        self.items = []

    # Pousser un élément sur la pile
    def push(self, item):
        self.items.append(item)
        print(f"Élément {item} ajouté à la pile")

    # Retirer un élément de la pile
    def pop(self):
        if not self.is_empty():
            popped_item = self.items.pop()
            print(f"Élément {popped_item} retiré de la pile")
            return popped_item
        else:
            print("La pile est vide")
            return None

    # Consulter l'élément au sommet sans le retirer
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            print("La pile est vide")
            return None

    # Vérifier si la pile est vide
    def is_empty(self):
        return len(self.items) == 0

    # Afficher la pile
    def display(self):
        print("Pile actuelle :", self.items)

# Utilisation de la pile
ma_pile = Stack()
ma_pile.push(10)
ma_pile.push(20)
ma_pile.push(30)
ma_pile.display()            # Affiche : Pile actuelle : [10, 20, 30]
print("Élément au sommet :", ma_pile.peek())  # Affiche : Élément au sommet : 30
ma_pile.pop()                # Retire 30 de la pile
ma_pile.display()            # Affiche : Pile actuelle : [10, 20]

Explication du Code :

• push : Ajoute un élément au sommet de la pile.
• pop : Retire l'élément au sommet de la pile.
• peek : Consulte l'élément au sommet sans le retirer.
• is_empty : Vérifie si la pile est vide.
• display : Affiche le contenu actuel de la pile.

💪 Exercices

Testez vos connaissances avec ces exercices :

# Exercices :

# 1. Implémentez une fonction qui vérifie si une expression mathématique a des parenthèses équilibrées en utilisant une pile.

# 2. Écrivez un programme qui convertit une expression infixe en notation postfixe (notation polonaise inversée) en utilisant une pile.

# 3. Créez une pile qui peut retourner le minimum actuel en temps constant.

# 4. Implémentez une fonction pour inverser une chaîne de caractères en utilisant une pile.

# 5. Écrivez un programme qui détecte si une pile est un palindrome (le même ordre en avant et en arrière).

🎉 Conclusion

Les piles sont des structures de données simples mais puissantes, essentielles en programmation. Elles vous permettent de gérer des données en suivant le principe LIFO, idéal pour des fonctionnalités comme l'annulation d'actions, la navigation dans l'historique, et bien plus encore.