Piles et Files 📚

Deux structures fondamentales

Deux concepts omniprésents en algorithmique :

Pile (Stack) : LIFO — Last In, First Out. Comme une pile d'assiettes : la dernière posée est la première prise.
File (Queue) : FIFO — First In, First Out. Comme une file d'attente : le premier arrivé est le premier servi.

1. La Pile (Stack) 🥞

Principe

On ne peut accéder qu'au sommet (dernier élément ajouté). Deux opérations seulement :

Empiler (push) : ajouter au sommet
Dépiler (pop) : retirer du sommet

Exécution pas à pas
pseudo
1/12
▶️STRUCTURE Pile
STRUCTURE PileLe programme exécute cette action, puis passe à la suivante.
Le programme exécute cette instruction, puis passe à la suivante.

Visualisation : [1, 2, 3] — pile.append(4) → [1, 2, 3, 4] — pile.pop() → [1, 2, 3] Le 4 entre en dernier et sort en premier !

En Python


# En Python, une liste fait office de pile
pile = []

pile.append(1)  # Empiler
pile.append(2)
pile.append(3)
print(pile)  # [1, 2, 3]

sommet = pile.pop()  # Dépiler → 3
print(sommet)        # 3
print(pile)          # [1, 2]

2. La File (Queue) 🏪

Principe

On ajoute à la queue et on retire en tête (début). Deux opérations :

Enfiler (enqueue) : ajouter à la fin
Défiler (dequeue) : retirer du début

Exécution pas à pas
pseudo
1/12
▶️STRUCTURE File
STRUCTURE FileLe programme exécute cette action, puis passe à la suivante.
Le programme exécute cette instruction, puis passe à la suivante.

Visualisation : ["A", "B", "C"] — file.append("D") → ["A", "B", "C", "D"] — file.popleft() → ["B", "C", "D"] "A" entre en premier et sort en premier !

En Python


from collections import deque

file = deque()
file.append("A")  # Enfiler
file.append("B")
file.append("C")

premier = file.popleft()  # Défiler → "A"
print(premier)            # "A"
print(file)               # deque(['B', 'C'])

3. Implémentation from scratch 🛠️

Pile avec une liste

Exécution pas à pas
pseudo
1/17
▶️CLASSE Pile
CLASSE PileLe programme exécute cette action, puis passe à la suivante.
Le programme exécute cette instruction, puis passe à la suivante.


class Pile:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[-1]
    def is_empty(self):
        return len(self.items) == 0

File avec deque

Exécution pas à pas
pseudo
1/14
▶️CLASSE File
CLASSE FileLe programme exécute cette action, puis passe à la suivante.
Le programme exécute cette instruction, puis passe à la suivante.


from collections import deque

class File:
    def __init__(self):
        self.items = deque()
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        return self.items.popleft()
    def is_empty(self):
        return len(self.items) == 0

4. Utilisations concrètes 🌍

Pile (LIFO) — quand tu as besoin de "revenir en arrière"

Usage	Exemple
Undo (Ctrl+Z)	Chaque action est empilée, Ctrl+Z la dépile
Pile d'appels	La fonction appelée en dernier se termine en premier
Parcours en profondeur (DFS)	On explore un chemin jusqu'au bout, puis on revient
Évaluation mathématique	`(3+2)×5` deviens `3 2 + 5 ×` (notation polonaise inversée)

File (FIFO) — quand l'ordre d'arrivée compte

Usage	Exemple
Imprimante	Les documents s'impriment dans l'ordre d'envoi
File d'attente	Billeterie, support client, etc.
Parcours en largeur (BFS)	Explorer niveau par niveau dans un graphe
Tâches asynchrones	Les jobs sont exécutés dans l'ordre d'arrivée

Exercices pour toi 🎯

1. Parenthèses équilibrées 🔄

Vérifier si les parenthèses ()[]{} sont correctement équilibrées. On utilise une pile : on empile les ouvrantes, on dépile quand on trouve une fermante.

Exécution pas à pas
pseudo
1/21
🧩FONCTION est_équilibrée(chaîne)
FONCTION est_équilibrée(chaîne)Le programme exécute cette action, puis passe à la suivante.
On définit une fonction appelée "est_équilibrée(chaîne)". Cette fonction contient des instructions qui seront exécutées quand on l'appelle.


def est_equilibree(s):
    pile = []
    paires = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in paires.values():      # Si c'est une ouvrante
            pile.append(c)
        elif c in paires:             # Si c'est une fermante
            if not pile or pile.pop() != paires[c]:
                return False
    return len(pile) == 0

Testez : "({[]})" → True, "({[})" → False

2. File avec deux piles 🏗️

Implémentez une file en utilisant uniquement deux piles (classique des entretiens techniques).

Exécution pas à pas
pseudo
1/16
▶️CLASSE FileAvecPiles
CLASSE FileAvecPilesLe programme exécute cette action, puis passe à la suivante.
Le programme exécute cette instruction, puis passe à la suivante.

💡 Pile et file sont les briques de base de nombreux algorithmes complexes. Un DFS = une pile implicite. Un BFS = une file explicite.

⚡ Simulateur — Piles et Files

Étape 1/12

📝 Pseudo-code

1# Pile (Stack) — LIFO

2pile = []

3pile.append(10) # push

4pile.append(20) # push

5pile.append(30) # push

6sommet = pile.pop() # pop → 30

7sommet = pile.pop() # pop → 20

9# File (Queue) — FIFO

10from collections import deque

11file = deque()

12file.append('A') # enqueue

13file.append('B') # enqueue

14file.append('C') # enqueue

15premier = file.popleft() # dequeue → A

16premier = file.popleft() # dequeue → B

📚 Pile (LIFO)

sommet

(vide)

base

💡 Principe

LIFO (Last In, First Out) : le dernier élément ajouté est le premier retiré. Comme une pile d'assiettes.

Pile vide. Principe LIFO : dernier entré, premier sorti.