Piles et files

#Piles et filesCopier le lien

Les piles et les files sont des structures de données fondamentales qui organisent les éléments selon des principes spécifiques d'ajout et de retrait.

#Quand utiliser quoiCopier le lien

• Pile (LIFO): annulations, parcours en profondeur (DFS), analyse syntaxique (parenthèses), backtracking. Avantage: proximité avec l’exécution (pile d’appels).
• File (FIFO): files d’attente, planification équitable, parcours en largeur (BFS). Avantage: ordre de traitement naturel.

#Piles (Stack)Copier le lien

Une pile suit le principe LIFO (Last In, First Out) : le dernier élément ajouté est le premier à être retiré.

#Opérations principalesCopier le lien

• push(element) : Ajouter un élément au sommet de la pile
• pop() : Retirer et retourner l'élément du sommet
• peek()/top() : Consulter l'élément du sommet sans le retirer
• is_empty() : Vérifier si la pile est vide

#Animation interactiveCopier le lien

Pour mieux comprendre le fonctionnement d'une pile, voici une animation interactive qui illustre les opérations de push et pop :

#Implémentation en PythonCopier le lien

1class Pile:2    def __init__(self):3        self.elements = []4    5    def push(self, element):6        self.elements.append(element)7    8    def pop(self):9        if self.is_empty():10            raise IndexError("Pile vide")11        return self.elements.pop()12    13    def peek(self):14        if self.is_empty():

#Files (Queue)Copier le lien

Une file suit le principe FIFO (First In, First Out) : le premier élément ajouté est le premier à être retiré.

#Opérations principalesCopier le lien

• enqueue(element) : Ajouter un élément à la fin de la file
• dequeue() : Retirer et retourner l'élément du début
• front() : Consulter l'élément du début sans le retirer
• is_empty() : Vérifier si la file est vide

#Animation interactiveCopier le lien

#Implémentation en PythonCopier le lien

1from collections import deque2 3class File:4    def __init__(self):5        self.elements = deque()6    7    def enqueue(self, element):8        self.elements.append(element)9    10    def dequeue(self):11        if self.is_empty():12            raise IndexError("File vide")13        return self.elements.popleft()14    

#Exercice : Vérification de parenthèses équilibréesCopier le lien

Implémentez un algorithme qui utilise une pile pour vérifier si une chaîne de caractères contient des parenthèses correctement équilibrées.

#InstructionsCopier le lien

1. Utilisez une pile pour suivre les parenthèses ouvertes.
2. Pour chaque parenthèse fermante, vérifiez qu'elle correspond à la dernière parenthèse ouverte.
3. La chaîne est équilibrée si toutes les parenthèses sont correctement appariées et que la pile est vide à la fin.

#Exemple de codeCopier le lien

1class Pile:2    def __init__(self):3        self.elements = []4    5    def push(self, element):6        self.elements.append(element)7    8    def pop(self):9        if self.is_empty():10            raise IndexError("Pile vide")11        return self.elements.pop()12    13    def peek(self):14        if self.is_empty():

#Cas d'usageCopier le lien

#PilesCopier le lien

• Appels de fonctions : La pile d'appels gère les fonctions actives
• Évaluation d'expressions : Conversion et évaluation d'expressions infixées
• Backtracking : Algorithmes de parcours avec retour en arrière
• Annuler/Rétablir : Historique des actions dans les éditeurs

#FilesCopier le lien

• Ordonnancement : Files d'attente dans les systèmes d'exploitation
• Breadth-First Search : Parcours en largeur dans les graphes
• Buffering : Gestion de flux de données
• Impressions : File d'impression dans les systèmes

Objectifs d’apprentissage

• Reconnaître LIFO (pile) vs FIFO (file) et les cas d’usage.
• Connaître les complexités usuelles et structures adaptées (list vs deque).
• Éviter les anti‑patterns (pop(0) sur list, insert(0,x)).

#Mini‑quizCopier le lien