Piles et files

Piles (LIFO — Last In, First Out)

Une pile est une structure de données où l'on insère et retire les éléments par le sommet uniquement.

Opérations :

• `empiler(x)` (push) : ajouter $x$ au sommet
• `depiler()` (pop) : retirer et renvoyer l'élément au sommet
• `est_vide()` : tester si la pile est vide
• `sommet()` : consulter le sommet sans le retirer

Toutes ces opérations sont en $O(1)$.

Implémentation avec une liste Python

```python class Pile: def __init__(self): self.elements = []

def est_vide(self): return len(self.elements) == 0

def empiler(self, x): self.elements.append(x)

def depiler(self): assert not self.est_vide(), "Pile vide" return self.elements.pop()

def sommet(self): assert not self.est_vide(), "Pile vide" return self.elements[-1] ```

Application : vérification du parenthésage

```python def parenthesage_correct(expression): """Vérifie que les parenthèses sont bien appariées.""" pile = Pile() corresp = {')': '(', ']': '[', '}': '{'} for c in expression: if c in '([{': pile.empiler(c) elif c in ')]}': if pile.est_vide() or pile.depiler() != corresp[c]: return False return pile.est_vide() ```

Files (FIFO — First In, First Out)

Une file est une structure où l'on insère par un bout (enfiler) et l'on retire par l'autre (défiler).

```python from collections import deque

class File: def __init__(self): self.elements = deque()

def est_vide(self): return len(self.elements) == 0

def enfiler(self, x): self.elements.append(x)

def defiler(self): assert not self.est_vide(), "File vide" return self.elements.popleft() ```

Remarque. On utilise `collections.deque` plutôt qu'une liste car `popleft()` est en $O(1)$ pour un deque, contre $O(n)$ pour une liste.

Application : parcours en largeur (BFS)

Les files sont utilisées dans le parcours en largeur des graphes et des arbres.

```python def parcours_largeur(graphe, depart): """Parcours en largeur d'un graphe représenté par listes d'adjacence.""" visites = set() file = deque([depart]) visites.add(depart) while file: sommet = file.popleft() print(sommet) for voisin in graphe[sommet]: if voisin not in visites: visites.add(voisin) file.append(voisin) ```

Files de priorité

Une file de priorité est une structure où l'on peut insérer des éléments avec une priorité et extraire l'élément de priorité minimale.

```python import heapq

tas = [] heapq.heappush(tas, 5) heapq.heappush(tas, 2) heapq.heappush(tas, 8) heapq.heappop(tas) # 2 (le minimum) ```

Les opérations d'insertion et d'extraction sont en $O(\log n)$.