01 — Piles et files : LIFO, FIFO et leurs usages

Ce que tu vas apprendre

• La pile (LIFO) et la file (FIFO), et ce qui les distingue
• Comment les implémenter correctement et en O(1)
• Le piège de la file naïve sur un tableau
• Leurs usages réels dans le code que tu écris

Prérequis

• 00 — Introduction

La pile et la file sont les structures de données les plus simples après le tableau, et parmi les plus utilisées, souvent sans qu'on s'en rende compte. Elles imposent toutes deux une discipline sur l'ordre dans lequel on retire les éléments. La pile sert en dernier celui entré en dernier ; la file sert en premier celui entré en premier. Cette contrainte d'apparence anodine structure énormément d'algorithmes.

La pile : dernier entré, premier sorti (LIFO)

Une pile (stack) fonctionne comme une pile d'assiettes : on ajoute au sommet, on retire du sommet. Le dernier élément empilé est le premier dépilé, d'où LIFO (Last In, First Out). Deux opérations principales : empiler (push) et dépiler (pop), toutes deux en O(1).

En JavaScript et en Python, un simple tableau fait une pile parfaite, parce que l'ajout et le retrait en fin sont en O(1).

typescriptclass Pile<T> {
  private items: T[] = [];
  empiler(x: T): void { this.items.push(x); }      // O(1)
  depiler(): T | undefined { return this.items.pop(); } // O(1)
  sommet(): T | undefined { return this.items[this.items.length - 1]; }
  estVide(): boolean { return this.items.length === 0; }
}

Les usages de la pile sont partout :

• La pile d'appels elle-même : chaque appel de fonction empile un contexte, chaque retour le dépile. La récursion, c'est une pile gérée par le langage (vu dans la série Complexité, article 04).
• Annuler / refaire : chaque action est empilée ; annuler dépile.
• Vérifier des parenthèses équilibrées : on empile chaque ouvrante, on dépile à chaque fermante.
• Le parcours en profondeur d'un arbre ou d'un graphe (qu'on verra dans la série Graphes) utilise une pile, explicitement ou via la récursion.

pythondef parentheses_equilibrees(s: str) -> bool:
    pile = []
    paires = {")": "(", "]": "[", "}": "{"}
    for c in s:
        if c in "([{":
            pile.append(c)
        elif c in paires:
            if not pile or pile.pop() != paires[c]:
                return False
    return not pile

La file : premier entré, premier sorti (FIFO)

Une file (queue) fonctionne comme une file d'attente : on ajoute à la fin, on retire au début. Le premier arrivé est le premier servi, d'où FIFO (First In, First Out). Les opérations : enfiler (enqueue) à la fin, défiler (dequeue) au début.

C'est ici qu'un piège apparaît. Avec un tableau, enfiler en fin est O(1), mais défiler au début (shift en JavaScript, pop(0) en Python) est O(n) : retirer le premier élément oblige à décaler tous les autres, comme vu dans la série Complexité. Une file naïve sur tableau est donc lente.

typescript// ❌ Piège : shift() est O(n), la file devient O(n) par défilement
const file: number[] = [];
file.push(1);       // O(1)
file.shift();       // O(n) — décale tout le tableau

La bonne implémentation utilise une structure adaptée. En Python, c'est collections.deque, conçue pour l'ajout et le retrait aux deux bouts en O(1).

pythonfrom collections import deque

file = deque()
file.append(1)      # enfiler : O(1)
file.append(2)
file.popleft()      # défiler : O(1), renvoie 1

En JavaScript, on peut utiliser une file circulaire sur tableau, ou une liste chaînée (article 03), ou simplement gérer un index de tête pour éviter le décalage. L'important est de ne jamais utiliser shift() dans une boucle sur de gros volumes.

Les usages de la file :

• Le parcours en largeur (BFS) d'un graphe, qui sert au plus court chemin non pondéré (série Graphes).
• Les files de tâches : traiter des jobs dans l'ordre d'arrivée.
• Les buffers entre un producteur et un consommateur.

Récapitulatif

La leçon pratique : la pile se fait gratuitement avec un tableau dans tous les langages. La file demande de l'attention, car l'implémentation naïve sur tableau est un O(n) caché. C'est un cas typique où connaître le coût des opérations (série Complexité) évite un bug de performance.

L'article suivant présente une file particulière, qui ne sert pas dans l'ordre d'arrivée mais dans l'ordre de priorité : la file de priorité, construite sur un tas binaire.

Sources

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 10.1 "Stacks and Queues". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.3. Addison-Wesley.
• Python Software Foundation. collections.deque. docs.python.org/3/library/collections.html#collections.deque