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

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

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).

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.

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.

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)$.