Piles et files#
Introduction#
Les piles et les files sont des structures de données linéaires à accès restreint : contrairement aux tableaux et aux listes qui permettent l’accès à tout élément par son indice, elles définissent une politique stricte sur l’ordre dans lequel les éléments peuvent être insérés et extraits. Cette restriction, loin d’être une limitation, est précisément ce qui rend ces structures si utiles : elle modélise naturellement de nombreuses situations réelles et algorithmiques.
Définition 34 (Structure de données abstraite)
Une structure de données abstraite (abstract data type, ADT) est définie par un ensemble d’opérations et leur sémantique, indépendamment de toute implémentation concrète. Par exemple, la pile est définie par ses opérations push, pop et peek, et par la garantie que les éléments sont retournés dans l’ordre LIFO. L’ADT décrit le quoi; l’implémentation décrit le comment.
La pile (stack, LIFO)#
Définition 35 (Pile)
Une pile (stack) est une structure de données linéaire qui suit le principe LIFO (Last In, First Out — dernier entré, premier sorti) : le dernier élément inséré est le premier à être retiré.
Les opérations fondamentales d’une pile sont :
push(\(x\)) : empile l’élément \(x\) au sommet de la pile.
pop() : dépile et retourne l’élément au sommet.
peek() (ou top) : consulte l’élément au sommet sans le retirer.
is_empty() : teste si la pile est vide.
Toutes ces opérations sont en \(O(1)\).
La métaphore la plus parlante est une pile d’assiettes : on pose toujours une nouvelle assiette au sommet, et on reprend toujours celle du dessus. Il est impossible d’accéder directement à une assiette au milieu sans d’abord enlever celles du dessus.
Applications des piles#
Les piles apparaissent dans un nombre remarquable de contextes algorithmiques.
Remarque 13
Applications fondamentales des piles :
Pile d’appels de fonctions. Toute exécution d’un programme utilise une pile pour gérer les appels de fonctions : lorsqu’une fonction \(f\) appelle \(g\), le cadre de \(f\) est empilé ; quand \(g\) retourne, son cadre est dépilé et l’exécution de \(f\) reprend.
Vérification de parenthèses. Pour vérifier qu’une expression est bien parenthésée (
(),[],{}), on empile les ouvrants et on vérifie que chaque fermant correspond au dernier ouvrant empilé.Notation polonaise inverse (Reverse Polish Notation, RPN). L’évaluation d’expressions arithmétiques en notation postfixe utilise une pile : on empile les opérandes, et chaque opérateur dépile ses opérandes, calcule le résultat et l’empile.
Parcours en profondeur (DFS, Depth-First Search). L’exploration d’un graphe ou d’un arbre en profondeur utilise une pile (explicite ou via la pile d’appels de la récursion).
Algorithme de Shunting-Yard (conversion infixe → postfixe). Cet algorithme de Dijkstra utilise une pile pour gérer la priorité des opérateurs.
Annulation / rétablissement (undo/redo). Les éditeurs de texte maintiennent une pile des actions effectuées pour permettre l’annulation.
Implémentation avec list Python#
from typing import TypeVar, Generic, Optional
T = TypeVar('T')
class Pile(Generic[T]):
"""
Pile implémentée avec une liste Python.
La liste Python utilise son extrémité droite comme sommet de pile :
- append() → push en O(1) amorti
- pop() → pop en O(1)
- [-1] → peek en O(1)
Complexité de toutes les opérations : O(1) amorti.
"""
def __init__(self):
self._donnees: list[T] = []
def empiler(self, element: T) -> None:
"""Push : empile l'élément au sommet."""
self._donnees.append(element)
def depiler(self) -> T:
"""Pop : dépile et retourne l'élément au sommet."""
if self.est_vide():
raise IndexError("Dépilage sur pile vide.")
return self._donnees.pop()
def sommet(self) -> T:
"""Peek : retourne l'élément au sommet sans le retirer."""
if self.est_vide():
raise IndexError("Pile vide.")
return self._donnees[-1]
def est_vide(self) -> bool:
return len(self._donnees) == 0
def __len__(self) -> int:
return len(self._donnees)
def __repr__(self) -> str:
if self.est_vide():
return 'Pile(vide)'
return f'Pile(sommet={self._donnees[-1]!r}, taille={len(self)})'
# Démonstration
pile = Pile()
print("Pile vide :", pile.est_vide())
for val in [10, 20, 30, 40, 50]:
pile.empiler(val)
print(f" empiler({val:2d}) → sommet={pile.sommet()}, taille={len(pile)}")
print()
while not pile.est_vide():
val = pile.depiler()
print(f" dépiler() → {val:2d}, taille restante={len(pile)}")
Pile vide : True
empiler(10) → sommet=10, taille=1
empiler(20) → sommet=20, taille=2
empiler(30) → sommet=30, taille=3
empiler(40) → sommet=40, taille=4
empiler(50) → sommet=50, taille=5
dépiler() → 50, taille restante=4
dépiler() → 40, taille restante=3
dépiler() → 30, taille restante=2
dépiler() → 20, taille restante=1
dépiler() → 10, taille restante=0
Implémentation avec collections.deque#
from collections import deque
class PileDeque(Generic[T]):
"""
Pile implémentée avec collections.deque.
Préférable à list pour des piles très grandes (meilleure performance
sur certaines plateformes) et pour une sémantique plus explicite.
"""
def __init__(self):
self._donnees: deque[T] = deque()
def empiler(self, element: T) -> None:
self._donnees.append(element)
def depiler(self) -> T:
if not self._donnees:
raise IndexError("Dépilage sur pile vide.")
return self._donnees.pop()
def sommet(self) -> T:
if not self._donnees:
raise IndexError("Pile vide.")
return self._donnees[-1]
def est_vide(self) -> bool:
return len(self._donnees) == 0
def __len__(self) -> int:
return len(self._donnees)
Application 1 : vérification de parenthèses#
def verifier_parentheses(expression: str) -> tuple[bool, str]:
"""
Vérifie que les parenthèses, crochets et accolades sont bien équilibrés.
Algorithme :
- Parcourir l'expression de gauche à droite.
- Pour chaque ouvrant '(', '[', '{' : empiler.
- Pour chaque fermant ')' ']', '}' : dépiler et vérifier la correspondance.
- À la fin, la pile doit être vide.
Complexité : O(n) en temps, O(n) en espace.
"""
correspondances = {')': '(', ']': '[', '}': '{'}
ouvrants = set(correspondances.values())
fermants = set(correspondances.keys())
pile = Pile()
for i, char in enumerate(expression):
if char in ouvrants:
pile.empiler(char)
elif char in fermants:
if pile.est_vide():
return False, f"Fermant '{char}' à la position {i} sans ouvrant correspondant."
sommet = pile.depiler()
if correspondances[char] != sommet:
return False, (f"Erreur à la position {i} : '{char}' ferme "
f"'{sommet}' au lieu de '{correspondances[char]}'.")
if not pile.est_vide():
return False, f"Il reste {len(pile)} ouvrant(s) non fermé(s)."
return True, "Expression bien parenthésée."
# Tests
expressions = [
"(a + b) * (c - d)",
"{[(1 + 2) * 3] / 4}",
"((a + b)",
"(a + b])",
"[[{()}]]",
"])",
"",
]
for expr in expressions:
ok, msg = verifier_parentheses(expr)
statut = "✓" if ok else "✗"
print(f" {statut} '{expr}'\n → {msg}")
✓ '(a + b) * (c - d)'
→ Expression bien parenthésée.
✓ '{[(1 + 2) * 3] / 4}'
→ Expression bien parenthésée.
✗ '((a + b)'
→ Il reste 1 ouvrant(s) non fermé(s).
✗ '(a + b])'
→ Erreur à la position 6 : ']' ferme '(' au lieu de '['.
✓ '[[{()}]]'
→ Expression bien parenthésée.
✗ '])'
→ Fermant ']' à la position 0 sans ouvrant correspondant.
✓ ''
→ Expression bien parenthésée.
Application 2 : notation polonaise inverse (RPN)#
def evaluer_rpn(expression: str) -> float:
"""
Évalue une expression en notation polonaise inverse (postfixe).
Exemples :
- "3 4 +" → 7 (= 3 + 4)
- "3 4 + 2 *" → 14 (= (3 + 4) × 2)
- "5 1 2 + 4 * + 3 -" → 14 (= 5 + ((1 + 2) × 4) - 3)
Algorithme :
- Pour chaque token :
- Si nombre : empiler.
- Si opérateur : dépiler deux opérandes, calculer, empiler le résultat.
- Le résultat final est le seul élément restant dans la pile.
Complexité : O(n) en temps, O(n) en espace.
"""
operateurs = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: a / b,
'**': lambda a, b: a ** b,
}
pile = Pile()
for token in expression.split():
if token in operateurs:
if len(pile) < 2:
raise ValueError(f"Opérateur '{token}' avec insuffisamment d'opérandes.")
b = pile.depiler()
a = pile.depiler()
resultat = operateurs[token](a, b)
pile.empiler(resultat)
else:
try:
pile.empiler(float(token))
except ValueError:
raise ValueError(f"Token invalide : '{token}'")
if len(pile) != 1:
raise ValueError(f"Expression invalide : {len(pile)} valeur(s) restante(s).")
return pile.depiler()
# Tests
cas_de_test = [
("3 4 +", 7.0),
("3 4 + 2 *", 14.0),
("5 1 2 + 4 * + 3 -", 14.0),
("2 3 ** 1 -", 7.0),
("15 7 1 1 + - / 3 * 2 1 1 + + -", 5.0),
]
print("Évaluation RPN :")
for expr, attendu in cas_de_test:
resultat = evaluer_rpn(expr)
statut = "✓" if abs(resultat - attendu) < 1e-9 else "✗"
print(f" {statut} '{expr}' = {resultat} (attendu : {attendu})")
Évaluation RPN :
✓ '3 4 +' = 7.0 (attendu : 7.0)
✓ '3 4 + 2 *' = 14.0 (attendu : 14.0)
✓ '5 1 2 + 4 * + 3 -' = 14.0 (attendu : 14.0)
✓ '2 3 ** 1 -' = 7.0 (attendu : 7.0)
✓ '15 7 1 1 + - / 3 * 2 1 1 + + -' = 5.0 (attendu : 5.0)
La file (queue, FIFO)#
Définition 36 (File)
Une file (queue) est une structure de données linéaire qui suit le principe FIFO (First In, First Out — premier entré, premier sorti) : le premier élément inséré est le premier à être retiré.
Les opérations fondamentales d’une file sont :
enqueue(\(x\)) (ou enfiler) : ajoute l’élément \(x\) à l’arrière de la file (rear ou tail).
dequeue() (ou défiler) : retire et retourne l’élément à l’avant de la file (front ou head).
front() : consulte l’élément à l’avant sans le retirer.
is_empty() : teste si la file est vide.
Toutes ces opérations sont en \(O(1)\).
La métaphore est une file d’attente à la caisse : le premier arrivé est le premier servi.
Applications des files#
Remarque 14
Applications fondamentales des files :
Parcours en largeur (BFS, Breadth-First Search). L’exploration d’un graphe ou d’un arbre en largeur utilise une file : on enfile les voisins non visités et on défile pour traiter le prochain nœud.
Systèmes de messagerie et files de tâches. Les systèmes de traitement de tâches asynchrones (files de messages, worker queues) utilisent une sémantique FIFO pour garantir l’ordre de traitement.
Planification de processus. Les systèmes d’exploitation maintiennent des files de processus prêts à exécuter (politique round-robin).
Simulation d’événements discrets. Les simulations de systèmes à événements (clients dans un magasin, paquets réseau) utilisent des files pour modéliser l’ordre d’arrivée.
Tampon de flux (stream buffer). La transmission de données entre un producteur et un consommateur à vitesses différentes utilise un tampon FIFO.
Implémentation avec collections.deque#
class File(Generic[T]):
"""
File FIFO implémentée avec collections.deque.
Enfilage à droite (append), défilage à gauche (popleft) : O(1) chacun.
Une list Python ne convient PAS pour une file : list.pop(0) est O(n).
"""
def __init__(self):
self._donnees: deque[T] = deque()
def enfiler(self, element: T) -> None:
"""Enqueue : ajoute à l'arrière. O(1)."""
self._donnees.append(element)
def defiler(self) -> T:
"""Dequeue : retire et retourne l'avant. O(1)."""
if self.est_vide():
raise IndexError("Défilage sur file vide.")
return self._donnees.popleft()
def avant(self) -> T:
"""Front : retourne l'avant sans le retirer. O(1)."""
if self.est_vide():
raise IndexError("File vide.")
return self._donnees[0]
def est_vide(self) -> bool:
return len(self._donnees) == 0
def __len__(self) -> int:
return len(self._donnees)
def __repr__(self) -> str:
if self.est_vide():
return 'File(vide)'
return f'File(avant={self._donnees[0]!r}, taille={len(self)})'
# Simulation d'une file de service
file_service = File()
print("Simulation d'une file de service :\n")
arrivees = ['Client A', 'Client B', 'Client C', 'Client D', 'Client E']
for client in arrivees:
file_service.enfiler(client)
print(f" Arrivée de {client:<10} → file : {list(file_service._donnees)}")
print()
while not file_service.est_vide():
client = file_service.defiler()
print(f" Service de {client:<10} → file restante : {list(file_service._donnees)}")
Simulation d'une file de service :
Arrivée de Client A → file : ['Client A']
Arrivée de Client B → file : ['Client A', 'Client B']
Arrivée de Client C → file : ['Client A', 'Client B', 'Client C']
Arrivée de Client D → file : ['Client A', 'Client B', 'Client C', 'Client D']
Arrivée de Client E → file : ['Client A', 'Client B', 'Client C', 'Client D', 'Client E']
Service de Client A → file restante : ['Client B', 'Client C', 'Client D', 'Client E']
Service de Client B → file restante : ['Client C', 'Client D', 'Client E']
Service de Client C → file restante : ['Client D', 'Client E']
Service de Client D → file restante : ['Client E']
Service de Client E → file restante : []
Application : parcours en largeur (BFS)#
from collections import deque
def bfs(graphe: dict[str, list[str]], depart: str) -> list[str]:
"""
Parcours en largeur d'un graphe non orienté représenté par liste d'adjacence.
Retourne la liste des sommets visités dans l'ordre BFS.
Complexité : O(V + E) où V = nombre de sommets, E = nombre d'arêtes.
"""
visites = set()
ordre_visite = []
file = deque([depart])
visites.add(depart)
while file:
sommet = file.popleft()
ordre_visite.append(sommet)
for voisin in graphe.get(sommet, []):
if voisin not in visites:
visites.add(voisin)
file.append(voisin)
return ordre_visite
# Exemple de graphe : réseau social simplifié
graphe = {
'Alice': ['Bob', 'Charlie', 'David'],
'Bob': ['Alice', 'Eve', 'Frank'],
'Charlie': ['Alice', 'George'],
'David': ['Alice'],
'Eve': ['Bob'],
'Frank': ['Bob', 'George'],
'George': ['Charlie', 'Frank'],
}
ordre = bfs(graphe, 'Alice')
print("Parcours BFS depuis Alice :")
for i, sommet in enumerate(ordre):
print(f" Étape {i+1} : {sommet}")
Parcours BFS depuis Alice :
Étape 1 : Alice
Étape 2 : Bob
Étape 3 : Charlie
Étape 4 : David
Étape 5 : Eve
Étape 6 : Frank
Étape 7 : George
La file de priorité (priority queue)#
Définition 37 (File de priorité)
Une file de priorité (priority queue) est une structure de données dans laquelle chaque élément possède une priorité. L’opération de défilage extrait toujours l’élément de priorité minimale (ou maximale selon la convention). Contrairement à une file FIFO, l’ordre d’extraction ne dépend pas de l’ordre d’insertion.
Les opérations fondamentales sont :
push(\(x\), \(p\)) : insère l’élément \(x\) avec la priorité \(p\).
pop() : extrait et retourne l’élément de priorité minimale.
peek() : consulte l’élément de priorité minimale sans l’extraire.
Définition 38 (Tas (heap))
Un tas (heap) est un arbre binaire presque complet qui satisfait la propriété de tas :
Dans un tas min (min-heap) : la valeur de chaque nœud est inférieure ou égale à celles de ses fils. La racine est donc le minimum.
Dans un tas max (max-heap) : la valeur de chaque nœud est supérieure ou égale à celles de ses fils.
Les opérations d’insertion et d’extraction sont en \(O(\log n)\).
Le module heapq de Python implémente un tas min.
import heapq
class FilePriorite(Generic[T]):
"""
File de priorité min implémentée avec heapq.
heapq maintient invariant : heap[0] est toujours le plus petit élément.
Pour les éléments de même priorité, on utilise un compteur pour éviter
de comparer des éléments T qui pourraient ne pas être comparables.
Complexités :
- push : O(log n)
- pop : O(log n)
- peek : O(1)
"""
def __init__(self):
self._tas: list = []
self._compteur: int = 0 # brise les égalités de priorité
def pousser(self, element: T, priorite: float) -> None:
"""Insère un élément avec la priorité donnée."""
heapq.heappush(self._tas, (priorite, self._compteur, element))
self._compteur += 1
def extraire(self) -> tuple[T, float]:
"""Extrait l'élément de priorité minimale. Retourne (element, priorité)."""
if self.est_vide():
raise IndexError("Extraction sur file de priorité vide.")
priorite, _, element = heapq.heappop(self._tas)
return element, priorite
def minimum(self) -> tuple[T, float]:
"""Retourne (element, priorité) du minimum sans l'extraire."""
if self.est_vide():
raise IndexError("File de priorité vide.")
priorite, _, element = self._tas[0]
return element, priorite
def est_vide(self) -> bool:
return len(self._tas) == 0
def __len__(self) -> int:
return len(self._tas)
# Application : planification de tâches par priorité
fp = FilePriorite()
taches = [
("Répondre aux emails", 3),
("Corriger le bug critique", 1),
("Rédiger la documentation", 5),
("Code review", 2),
("Réunion hebdomadaire", 4),
]
print("Ajout des tâches :")
for tache, prio in taches:
fp.pousser(tache, prio)
print(f" Priorité {prio} : {tache}")
print("\nExécution par priorité :")
while not fp.est_vide():
tache, prio = fp.extraire()
print(f" [Priorité {prio:.0f}] {tache}")
Ajout des tâches :
Priorité 3 : Répondre aux emails
Priorité 1 : Corriger le bug critique
Priorité 5 : Rédiger la documentation
Priorité 2 : Code review
Priorité 4 : Réunion hebdomadaire
Exécution par priorité :
[Priorité 1] Corriger le bug critique
[Priorité 2] Code review
[Priorité 3] Répondre aux emails
[Priorité 4] Réunion hebdomadaire
[Priorité 5] Rédiger la documentation
# heapq : API bas niveau de Python
import heapq
# Tas min avec heapq directement
tas = []
valeurs = [5, 3, 8, 1, 9, 2, 7, 4, 6]
for v in valeurs:
heapq.heappush(tas, v)
print("Tas min :", tas)
print("Extraction des éléments dans l'ordre croissant :")
triee = []
while tas:
triee.append(heapq.heappop(tas))
print(" →", triee)
# Tas max : inverser le signe
tas_max = []
for v in valeurs:
heapq.heappush(tas_max, -v)
print("\nExtraction des éléments dans l'ordre décroissant (tas max) :")
print(" →", [-heapq.heappop(tas_max) for _ in range(len(valeurs))])
# heapq.nlargest et nsmallest
print("\nLes 3 plus grands :", heapq.nlargest(3, valeurs))
print("Les 3 plus petits :", heapq.nsmallest(3, valeurs))
Tas min : [1, 3, 2, 4, 9, 8, 7, 5, 6]
Extraction des éléments dans l'ordre croissant :
→ [1, 2, 3, 4, 5, 6, 7, 8, 9]
Extraction des éléments dans l'ordre décroissant (tas max) :
→ [9, 8, 7, 6, 5, 4, 3, 2, 1]
Les 3 plus grands : [9, 8, 7]
Les 3 plus petits : [1, 2, 3]
La file à deux extrémités (deque)#
Définition 39 (File à deux extrémités (deque))
Une file à deux extrémités (double-ended queue, deque) est une structure de données qui généralise à la fois la pile et la file : elle permet l’insertion et la suppression aux deux extrémités (avant et arrière) en \(O(1)\).
collections.deque de Python est l’implémentation standard. Elle offre :
append(x)/appendleft(x): insertion à droite/gauche en \(O(1)\).pop()/popleft(): suppression à droite/gauche en \(O(1)\).rotate(k): rotation de \(k\) positions en \(O(k)\).maxlen: deque de taille bornée (buffer circulaire).
from collections import deque
# Buffer circulaire borné : enregistre les N derniers événements
historique = deque(maxlen=5)
evenements = ['login', 'page_accueil', 'panier', 'paiement',
'confirmation', 'déconnexion', 'login', 'profil']
print("Historique des 5 derniers événements (buffer circulaire maxlen=5) :")
for evt in evenements:
historique.append(evt)
print(f" Après '{evt:<15}' : {list(historique)}")
# Déque comme palindrome checker
def est_palindrome(chaine: str) -> bool:
"""
Vérifie si une chaîne est un palindrome en utilisant un deque.
On compare simultanément les deux extrémités. O(n).
"""
d = deque(c.lower() for c in chaine if c.isalnum())
while len(d) > 1:
if d.popleft() != d.pop():
return False
return True
tests_palindrome = [
("radar", True),
("kayak", True),
("A man a plan a canal Panama", True),
("Madam Im Adam", True),
("algorithmique", False),
("racecar", True),
("hello", False),
]
print("\nTest de palindromes avec deque :")
for chaine, attendu in tests_palindrome:
resultat = est_palindrome(chaine)
statut = "✓" if resultat == attendu else "✗"
print(f" {statut} '{chaine}' → {resultat}")
Historique des 5 derniers événements (buffer circulaire maxlen=5) :
Après 'login ' : ['login']
Après 'page_accueil ' : ['login', 'page_accueil']
Après 'panier ' : ['login', 'page_accueil', 'panier']
Après 'paiement ' : ['login', 'page_accueil', 'panier', 'paiement']
Après 'confirmation ' : ['login', 'page_accueil', 'panier', 'paiement', 'confirmation']
Après 'déconnexion ' : ['page_accueil', 'panier', 'paiement', 'confirmation', 'déconnexion']
Après 'login ' : ['panier', 'paiement', 'confirmation', 'déconnexion', 'login']
Après 'profil ' : ['paiement', 'confirmation', 'déconnexion', 'login', 'profil']
Test de palindromes avec deque :
✓ 'radar' → True
✓ 'kayak' → True
✓ 'A man a plan a canal Panama' → True
✓ 'Madam Im Adam' → True
✓ 'algorithmique' → False
✓ 'racecar' → True
✓ 'hello' → False
Implémentation Rust#
use std::collections::{VecDeque, BinaryHeap};
use std::cmp::Reverse;
// ============================================================
// Pile avec Vec<T>
// ============================================================
struct Pile<T> {
donnees: Vec<T>,
}
impl<T> Pile<T> {
fn new() -> Self {
Pile { donnees: Vec::new() }
}
/// Push en fin de vecteur : O(1) amorti.
fn empiler(&mut self, element: T) {
self.donnees.push(element);
}
/// Pop en fin de vecteur : O(1).
fn depiler(&mut self) -> Option<T> {
self.donnees.pop()
}
/// Peek : dernier élément. O(1).
fn sommet(&self) -> Option<&T> {
self.donnees.last()
}
fn est_vide(&self) -> bool {
self.donnees.is_empty()
}
fn taille(&self) -> usize {
self.donnees.len()
}
}
// ============================================================
// File avec VecDeque<T>
// ============================================================
// VecDeque est un deque basé sur un buffer circulaire.
// push_back et pop_front sont tous les deux O(1) amorti.
struct File<T> {
donnees: VecDeque<T>,
}
impl<T> File<T> {
fn new() -> Self {
File { donnees: VecDeque::new() }
}
fn enfiler(&mut self, element: T) {
self.donnees.push_back(element);
}
fn defiler(&mut self) -> Option<T> {
self.donnees.pop_front()
}
fn avant(&self) -> Option<&T> {
self.donnees.front()
}
fn est_vide(&self) -> bool {
self.donnees.is_empty()
}
}
// ============================================================
// File de priorité avec BinaryHeap
// ============================================================
// BinaryHeap de Rust est un tas MAX.
// Pour un tas min, on enveloppe dans Reverse<T>.
fn exemple_file_priorite() {
// Tas max (comportement par défaut)
let mut tas_max: BinaryHeap<i32> = BinaryHeap::new();
for val in [3, 1, 4, 1, 5, 9, 2, 6] {
tas_max.push(val);
}
println!("Extraction ordre décroissant :");
while let Some(val) = tas_max.pop() {
print!("{} ", val);
}
println!();
// Tas min avec Reverse
let mut tas_min: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
for val in [3, 1, 4, 1, 5, 9, 2, 6] {
tas_min.push(Reverse(val));
}
println!("Extraction ordre croissant (tas min) :");
while let Some(Reverse(val)) = tas_min.pop() {
print!("{} ", val);
}
println!();
}
fn main() {
// --- Pile ---
let mut pile: Pile<i32> = Pile::new();
for v in [10, 20, 30, 40, 50] {
pile.empiler(v);
}
println!("Sommet : {:?}", pile.sommet());
while let Some(val) = pile.depiler() {
println!(" Dépilage : {}", val);
}
// --- File ---
let mut file: File<&str> = File::new();
for client in ["Alice", "Bob", "Charlie"] {
file.enfiler(client);
}
while let Some(client) = file.defiler() {
println!(" Service : {}", client);
}
// --- File de priorité ---
exemple_file_priorite();
// --- Vérification de parenthèses avec une pile ---
let expr = "{[(1 + 2) * 3] / 4}";
let mut pile_par: Pile<char> = Pile::new();
let correspondances = [(')', '('), (']', '['), ('}', '{')];
let ouvrants: Vec<char> = correspondances.iter().map(|&(_, o)| o).collect();
let mut valide = true;
for ch in expr.chars() {
if ouvrants.contains(&ch) {
pile_par.empiler(ch);
} else if let Some(&(f, o)) = correspondances.iter().find(|&&(f, _)| f == ch) {
match pile_par.depiler() {
Some(s) if s == o => {},
_ => { valide = false; break; }
}
}
}
if !pile_par.est_vide() {
valide = false;
}
println!("'{}' est bien parenthésée : {}", expr, valide);
}
Remarque 15
En Rust, Vec<T> est le choix naturel pour implémenter une pile : push et pop opèrent à la fin du vecteur en \(O(1)\) amorti. Pour une file, VecDeque<T> est le choix standard : c’est un buffer circulaire qui offre push_back et pop_front en \(O(1)\) amorti, sans le coût de \(O(n)\) de Vec::remove(0). BinaryHeap<T> implémente un tas max; pour un tas min, on enveloppe le type dans std::cmp::Reverse<T>, idiome idiomatique et sans coût runtime.
Visualisation#
Récapitulatif des structures et leurs complexités#
Résumé#
Dans ce chapitre, nous avons étudié les structures de données à accès restreint qui constituent le cœur de nombreux algorithmes fondamentaux :
La pile (LIFO) permet les opérations
push,popetpeeken \(O(1)\). En Python,list(viaappend/pop) etcollections.dequesont toutes deux adaptées. Les piles sous-tendent la gestion des appels de fonctions, la vérification de parenthèses, l’évaluation RPN et le parcours DFS.La file (FIFO) permet les opérations
enqueueetdequeueen \(O(1)\).collections.dequeest le bon choix en Python :list.pop(0)est \(O(n)\), ce qui rendrait l’algorithme BFS quadratique. En Rust,VecDeque<T>offre les mêmes garanties.La file de priorité extrait toujours l’élément de priorité minimale en \(O(\log n)\).
heapqimplémente un tas min en Python ;BinaryHeap<T>est le tas max de Rust (avecReverse<T>pour un tas min).Le deque (file à deux extrémités) généralise la pile et la file avec des insertions/suppressions \(O(1)\) des deux côtés. Il sert de buffer circulaire (via
maxlen) et de structure universelle pour les algorithmes qui accèdent aux deux extrémités.Les applications combinées — vérification de parenthèses, évaluation RPN, BFS — illustrent comment le choix d’une structure à la sémantique précise simplifie l’algorithme et garantit son efficacité.
Dans le chapitre suivant, nous aborderons les arbres — structures de données hiérarchiques qui sous-tendent les bases de données, les compilateurs et les systèmes de fichiers — en commençant par les arbres binaires de recherche.