Ch. 2 — Piles et files

Ce chapitre de R3.02 Développement efficace présente deux structures de données abstraites qui servent partout : la pile et la file. Leur particularité est contre-intuitive au début : contrairement à un tableau ou à une liste, on ne peut pas lire n'importe quel élément — un seul élément est accessible, toujours le même type de bout. C'est cette restriction qui les rend efficaces pour des problèmes précis : explorer un labyrinthe, gérer des annulations, dérouler les appels de méthodes, ou encore calculer des expressions arithmétiques.

1. Deux conteneurs, deux règles d'accès

2. La pile : dernier arrivé, premier sorti

Une pile est un conteneur d'éléments qui respecte le principe LIFO : l'élément accessible est le dernier élément ajouté, situé au sommet de la pile.

Quelques exemples d'utilisation donnés par le cours :

• la recherche de chemins dans un labyrinthe (c'est le TP 2 de cette ressource) ;
• la gestion d'un historique de modifications (undo/redo : on empile les actions, on dépile pour annuler) ;
• la gestion de la récursivité dans un langage : c'est la fameuse pile d'appels, qui retient « où revenir » quand une méthode en appelle une autre.

Le type de données abstrait (TDA) Pile

Un TDA décrit les opérations d'une structure sans dire comment elle est implémentée. Pour la pile, les opérations principales sont :

3. Application : le parcours en profondeur (avec une pile)

Un parcours de graphe consiste à visiter tous les sommets à partir d'une racine. Avec une pile, on obtient un parcours en profondeur : on part dans une direction et on va au bout de la branche avant de revenir.

La méthode : on empile les sommets visités ; à chaque étape, on dépile le sommet et on empile ses voisins (lus de gauche à droite). Le sommet de la pile est donc toujours le « prochain à explorer », et le dernier voisin empilé est examiné en premier.

4. Comment implémenter une pile ?

Une pile est un TDA : plusieurs implémentations donnent le même comportement.

• à partir d'un tableau — c'est l'exercice 1 du TD : un tableau plus un indice sommet ;
• à partir d'une liste chaînée ;
• en Java, on utilise la classe Stack (synchronisée, un peu ancienne) ou, plus moderne, l'interface Deque (voir « File en Java » plus bas).

Exemple classique du cours : inverser une chaîne de caractères en empilant chaque caractère, puis en les dépilant — le dernier empilé ressort en premier, donc la chaîne est lue à l'envers.

String input = "TRUC";
String output = "";
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < input.length(); i++) {
    stack.push(input.charAt(i));
}
while (!stack.isEmpty()) {
    output += stack.pop(); // C, puis U, puis R, puis T
}

5. La file : premier arrivé, premier sorti

Une file est un conteneur qui respecte le principe FIFO : l'élément accessible est le premier élément ajouté — le plus ancien de la file. On ajoute les éléments par la queue et on les retire par la tête, comme dans une file d'attente.

Exemples d'utilisation : file d'attente dans un magasin, gestion de stocks de denrées périssables (on écoule les plus anciennes), ordonnancement de processus par un système d'exploitation.

Le TDA File

6. Application : le parcours en largeur (avec une file)

Avec le même graphe que tout à l'heure, remplaçons la pile par une file : on retire le premier arrivé, et on ajoute ses voisins en queue. Le parcours change complètement de forme : on progresse niveau par niveau, d'abord tous les voisins directs de la racine, puis leurs voisins, etc. C'est le parcours en largeur.

Reprenez le schéma de la section 3 : avec une pile on visite A, E, C, G, B, F, H, D (on descend au bout des branches), avec une file A, B, C, E, D, F, G, H (niveau par niveau).

7. La file en Java

Le TDA File est représenté en Java par l'interface Queue, qui étend Collection :

• les implémentations principales : LinkedList et PriorityQueue (cette dernière exige des éléments Comparable, ou un Comparator à la construction) ;
• les méthodes à connaître : offer (ajout en queue), peek (lire la tête), poll (retirer la tête).

8. Application : les expressions arithmétiques

Le cours termine sur une application élégante des piles : le calcul d'expressions. Trois écritures existent pour 2 + 5 :

La notation postfixée simplifie l'écriture : plus besoin de parenthèses. Par exemple (10+14)*(7-2) s'écrit 10 14 + 7 2 - *.

Convertir infixée → postfixée (avec une pile)

Les règles du cours :

• un opérande (un nombre) : on l'ajoute directement à la sortie ;
• un opérateur : on l'empile si la pile est vide ou contient une parenthèse ouvrante ; sinon on dépile d'abord tous les opérateurs de priorité égale ou supérieure (ajoutés à la sortie), puis on empile l'opérateur courant ;
• une parenthèse ouvrante : on l'empile ;
• une parenthèse fermante : on dépile jusqu'à avoir dépilé l'ouvrante, en ajoutant les opérateurs à la sortie ;
• à la fin : on dépile tout le reste vers la sortie.

Suivons l'exemple du cours, (3+7)*(6-5)/((4-2)*(2+3)) :

Évaluer une expression postfixée (encore une pile)

Pour calculer une expression postfixée : on lit un élément à la fois ; un opérande est empilé ; un opérateur binaire dépile deux éléments, applique l'opération et empile le résultat. À la fin, la pile contient la valeur. Exemple du cours : 5 9 3 + 4 2 * * 7 + *

A retenir

• Pile = LIFO (dernier entré, premier sorti) — tout se passe au sommet : push, pop, peek, isEmpty.
• File = FIFO (premier entré, premier sorti) — on ajoute en queue, on retire en tête : offer, poll, peek.
• Le parcours en profondeur (au bout des branches) utilise une pile ; le parcours en largeur (niveau par niveau) utilise une file. Même graphe, résultat différent.
• Une pile sert à inverser, à revenir en arrière et à calculer des expressions ; la conversion infixée → postfixée est l'exemple type du cours.
• En Java : Stack (ancienne), Deque pour les piles modernes, Queue (LinkedList, PriorityQueue) pour les files.