Piles et files

Le bouton « annuler » d'un traitement de texte, le bouton « précédent » d'un navigateur, la pile d'appels du chapitre 1 : trois mécanismes qui font la même chose. Ils gardent une suite d'éléments et n'en rendent qu'un seul, le dernier arrivé.

À l'autre bout, la file d'impression, la file des processus prêts du cours de systèmes, la file d'attente d'un guichet : mêmes éléments gardés, mais c'est le premier arrivé qui sort.

Ces deux structures sont des listes volontairement bridées : elles n'autorisent les opérations qu'aux extrémités. La restriction paraît appauvrissante ; c'est elle qui fait toute leur valeur, pour deux raisons — elle garantit un coût constant, et elle donne à la structure une sémantique que le lecteur du code comprend immédiatement.

La pile

Une pile (stack) obéit à la règle LIFO : dernier entré, premier sorti. Trois opérations, toutes en $O(1)$.

1empiler(x)    pose x au sommet2dépiler()     retire et rend l'élément du sommet3sommet()      rend l'élément du sommet sans le retirer4estVide()

L'image est celle d'une pile d'assiettes : on ne prend que celle du dessus, et il n'existe aucune opération pour atteindre le milieu. Toute tentative de contourner cette limite est le signe qu'on avait besoin d'une autre structure.

Deux implémentations, et le choix est moins évident qu'il n'y paraît.

Par tableau : un tableau et un indice sommet. Empiler écrit en T[sommet] et incrémente ; dépiler décrémente. Extrêmement rapide — accès contigus, aucune allocation — mais la capacité est bornée, sauf à redimensionner en doublant la taille, ce qui donne un coût amorti constant.

Par liste chaînée : la tête de liste est le sommet. Empiler est une insertion en tête, dépiler une suppression en tête — les deux opérations à $O(1)$ du chapitre 5. Aucune limite de capacité, mais un pointeur par élément et des accès dispersés.

En pratique on choisit le tableau, pour la raison de cache du chapitre précédent, sauf si la taille maximale est réellement imprévisible.

La file

Une file (queue) obéit à la règle FIFO : premier entré, premier sorti.

1enfiler(x)    ajoute x en queue2défiler()     retire et rend l'élément de tête

L'implémentation par liste chaînée est immédiate à condition de garder deux pointeurs, tête et queue : on défile en tête et on enfile en queue, les deux en $O(1)$. Sans pointeur de queue, enfiler redeviendrait $O(n)$.

L'implémentation par tableau, elle, pose un problème instructif. Si l'on défile en avançant un indice de tête, l'espace libéré au début du tableau n'est jamais réutilisé : la file « dérive » vers la droite et finit par déborder alors que le tableau est presque vide.

La solution est le tampon circulaire : les indices reviennent à zéro après la dernière case, par un modulo.

1capacité 6, tête = 4, nombre = 42 3       0     1     2     3     4     54    ┌─────┬─────┬─────┬─────┬─────┬─────┐5    │  C  │  D  │     │     │  A  │  B  │6    └─────┴─────┴─────┴─────┴─────┴─────┘7                             ▲tête8    enfiler(E)  →  position (4 + 4) mod 6 = 2

Reste un piège classique : avec les seuls indices de tête et de queue, une file pleine et une file vide donnent la même configuration — tête et queue confondues. Deux parades : maintenir un compteur d'éléments, ce qui est le plus simple et le plus clair ; ou sacrifier une case en déclarant la file pleine quand il en reste une libre.

C'est exactement le tampon du tube du chapitre 2 du cours de systèmes, et le tampon producteur-consommateur de son chapitre 5. Les sémaphores vide et plein y comptaient précisément ce que ce compteur compte ici.

Ce qu'on en fait

Quatre applications, et chacune éclaire une propriété.

Vérifier un parenthésage. Chaque symbole ouvrant est empilé ; chaque fermant doit correspondre au sommet, qu'on dépile. À la fin, la pile doit être vide. Trois erreurs distinctes se lisent alors : un fermant alors que la pile est vide (fermeture orpheline), un fermant qui ne correspond pas au sommet (mauvais appariement), une pile non vide à la fin (ouvertures non refermées). C'est ce que fait un éditeur pour signaler une accolade manquante, et c'est la première étape de tout analyseur syntaxique.

Évaluer une expression postfixée. En notation polonaise inverse, 3 4 2 × + s'évalue sans la moindre parenthèse et sans aucune règle de priorité : on empile les nombres, et chaque opérateur dépile ses deux opérandes et empile le résultat. La simplicité de l'algorithme explique que cette notation ait été celle des calculatrices HP et qu'elle reste celle des machines virtuelles.

La pile d'appels. Le chapitre 1 l'a décrite comme un mécanisme ; c'est cette structure. Un appel empile un cadre, un retour dépile — et la remontée en ordre inverse de la descente est simplement la règle LIFO. Vous l'avez d'ailleurs réimplémentée à la main dans l'exercice du chapitre 1.

Les files d'attente. Toute ressource partagée servie dans l'ordre d'arrivée est une file : processus prêts, requêtes disque, paquets réseau, travaux d'impression. Le chapitre 4 du cours de systèmes n'a fait qu'ordonner cette file autrement — FIFO, c'est le nom de la structure autant que celui de l'algorithme.

Une cinquième application arrive au chapitre 9, et elle mérite d'être annoncée : le parcours d'un graphe en profondeur utilise une pile, le parcours en largeur utilise une file. Le code est le même à une ligne près ; c'est le choix de la structure qui décide de l'ordre de visite.

À vous

L'exercice implémente les deux structures, puis les met au travail.

D'abord une pile par tableau et une file en tampon circulaire — avec le piège du plein contre vide, que le squelette laisse ouvert : la file acceptera d'enfiler par-dessus des éléments non défilés tant que vous n'aurez pas ajouté le compteur.

Ensuite deux applications : le vérificateur de parenthésage, qui doit distinguer les trois erreurs possibles et pas seulement dire « incorrect », et l'évaluateur postfixé, dont un jeu de tests contient volontairement une soustraction et une division pour faire tomber l'inversion des opérandes.

// ── Pile par tableau ──────────────────────────────────────────────────────
function creerPile() {
  const T = [];
  return {
    empiler: (x) => T.push(x),
    depiler: () => T.pop(),
    sommet: () => T[T.length - 1],
    estVide: () => T.length === 0,
    taille: () => T.length,
    contenu: () => [...T],
  };
}

// ── File par tampon circulaire ────────────────────────────────────────────
function creerFile(capacite) {
  const T = new Array(capacite).fill(null);
  let tete = 0, queue = 0;
  // ← il manque un compteur : sans lui, plein et vide sont indiscernables
  return {
    enfiler(x) {
      T[queue] = x;
      queue = (queue + 1) % capacite;
      return true;   // ← devrait refuser si la file est pleine
    },
    defiler() {
      const x = T[tete];
      tete = (tete + 1) % capacite;
      return x;      // ← devrait rendre undefined si la file est vide
    },
    estVide: () => false,   // ← à écrire
    estPleine: () => false, // ← à écrire
    contenu: () => T.map((v, i) => (v === null ? "." : v)).join(" "),
  };
}

// ── Application 1 : parenthésage ──────────────────────────────────────────
const PAIRES = { ")": "(", "]": "[", "}": "{" };

function verifier(texte) {
  const p = creerPile();
  for (let i = 0; i < texte.length; i++) {
    const c = texte[i];
    if ("([{".includes(c)) p.empiler({ c, i });
    else if (c in PAIRES) {
      // ← à écrire : trois cas d'erreur distincts à distinguer
    }
  }
  return { ok: true };
}

// ── Application 2 : expression postfixée ──────────────────────────────────
function evaluer(expression) {
  const p = creerPile();
  for (const jeton of expression.split(" ")) {
    if (!isNaN(Number(jeton))) { p.empiler(Number(jeton)); continue; }
    const a = p.depiler();
    const b = p.depiler();
    // ← attention à l'ORDRE : lequel de a et b est l'opérande de gauche ?
    if (jeton === "+") p.empiler(a + b);
    if (jeton === "-") p.empiler(a - b);
    if (jeton === "*") p.empiler(a * b);
    if (jeton === "/") p.empiler(a / b);
  }
  return p.depiler();
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Ajoutez le compteur à la file et faites-la refuser proprement.
// 2. Écrivez verifier() en distinguant les trois erreurs.
// 3. Corrigez l'ordre des opérandes dans evaluer().

for (const e of ["5 1 2 + 4 * + 3 -", "7 3 -", "20 4 /"]) {
  console.log(e.padEnd(22) + "= " + evaluer(e));
}

En travaux pratiques

Ce que la suite en fait

Le bloc IV passe au non linéaire. Un arbre est ce qu'on obtient en donnant deux successeurs à une cellule au lieu d'un, et ses parcours emploient exactement les deux structures de ce chapitre — pile pour la profondeur, file pour la largeur.

Le lien le plus fort est avec le chapitre 7 : le parcours infixe d'un arbre d'expression rend la notation usuelle, le parcours suffixe rend la notation postfixée que vous venez d'évaluer. La pile et l'arbre d'expression sont les deux faces d'un même objet, et c'est précisément ce qui permet à un compilateur de transformer l'un en l'autre.

À retenir