Pile (Stack) — LIFO
DéfinitionLIFO = Last In, First Out (dernier entré, premier sorti)
Opérations :
• push : empiler (ajouter au sommet)
• pop : dépiler (retirer du sommet)
• peek : lire le sommet sans retirer
• est_vide : tester si vide
Implémentation Python (liste) :
pile = []
pile.append(5) # push → [5]
pile.append(3) # push → [5, 3]
x = pile.pop() # pop → x=3, pile=[5]
COMPLEXITÉ : push et pop en O(1)
APPLICATIONS :
• Ctrl+Z (undo/redo)
• Appels de fonctions (call stack)
• Vérification d'équilibre des parenthèses
• Évaluation d'expressions
⚡ La liste Python est naturellement une pile : append() = push, pop() = pop. Complexité O(1) amortie.
File (Queue) — FIFO
DéfinitionFIFO = First In, First Out (premier entré, premier sorti)
Opérations :
• enqueue : enfiler (ajouter en queue)
• dequeue : défiler (retirer en tête)
Implémentation Python (collections.deque) :
from collections import deque
file = deque()
file.appendleft(5) # enqueue → deque([5])
file.appendleft(3) # enqueue → deque([3, 5])
x = file.pop() # dequeue → x=5, deque([3])
COMPLEXITÉ : O(1) pour appendleft et pop
APPLICATIONS :
• File d'attente (print queue, CPU scheduling)
• Parcours BFS de graphe
• Traitement de messages (chat, serveur web)
⚡ Toujours préférer collections.deque à la liste Python pour les files : insert(0, x) sur une liste est O(n) alors que appendleft sur deque est O(1).