Piles et files

Une structure de données n'est pas seulement un endroit où ranger. C'est aussi une discipline : la règle qui décide ce qui ressort et dans quel ordre. Deux disciplines suffisent à couvrir une part considérable des besoins réels, et elles s'écrivent l'une comme l'autre avec les moyens des chapitres précédents.

La pile : dernier arrivé, premier servi

L'image est celle d'une pile d'assiettes : la dernière posée est la seule accessible. Rien n'oblige à une structure particulière pour la tenir, un tableau et un entier suffisent. L'entier, sommet, compte les éléments présents et désigne en même temps la case occupée la plus haute. Une pile vide, c'est sommet à zéro.

27 pas, et la sortie donne la discipline sans commentaire : les actions sont appliquées dans l'ordre gras, couleur, taille, et annulées dans l'ordre taille, couleur, gras. C'est exactement la commande « annuler » d'un traitement de texte, et c'est pour cette raison qu'elle défait toujours la dernière opération et jamais une autre.

Deux lignes seulement font tout le travail, et elles vont toujours par paire. Empiler, c'est monter le sommet puis écrire ; dépiler, c'est lire puis descendre le sommet. Inverser l'empilement écrit par-dessus la valeur du sommet, qui est perdue, et laisse le sommet sur une case périmée ; inverser le dépilement rend la valeur située juste en dessous, et la dernière arrivée n'est jamais servie.

Les deux fautes réelles

Une pile tenue à la main a deux façons de mal tourner. Dans la page, l'une et l'autre arrêtent l'algorithme, la seconde à condition que le tableau ait été créé avec sa taille ; sur une machine réelle, elles peuvent passer inaperçues. C'est pourquoi elles se préviennent au lieu de se constater.

Le retrait à vide consiste à dépiler quand sommet vaut déjà zéro. L'algorithme demande alors p[0], qui n'existe pas dans ce cours, et le déroulement s'interrompt en le disant :

La figure s'arrête à la dernière ligne, après avoir retiré 42 une première fois. Le message nomme l'indice 0. C'est la forme la plus douce de cette faute : elle se voit. Sur une machine réelle, un sommet passé sous zéro lit une zone de mémoire qui appartient à autre chose, et rend une valeur plausible au lieu d'une erreur.

Le débordement est l'autre bout du même problème : empiler alors que la capacité réservée est atteinte. Sur un tableau créé avec sa taille, comme p ← tableau[3], la page arrête l'algorithme à la première écriture au-delà de la dernière case : sans garde, la quatrième valeur viserait p[4], et le message dirait que l'indice 4 sort du tableau, qui compte 3 éléments. Python s'arrêterait aussi sur une liste de trois cases ; un programme en C, lui, écrirait en silence dans la mémoire voisine. Dans tous les cas, la valeur n'est pas rangée et le traitement est interrompu. La bonne pratique est donc un test écrit avant l'écriture, qui refuse proprement :

26 pas, trois valeurs rangées, la quatrième refusée avec un message. Le refus n'est pas un échec de l'algorithme : c'est la seule réponse honnête possible, et elle vaut mieux qu'une écriture au-delà de la zone réservée, qui arrêterait tout ici et passerait inaperçue ailleurs.

Deux gardes, une à chaque extrémité. Une pile se tient avec deux gardes, une à chaque extrémité : ne pas retirer quand sommet vaut 0, ne pas ajouter quand sommet vaut la capacité. Ces deux tests occupent quatre lignes et évitent les deux fautes propres à la structure. La pile des appels du chapitre sur la récursivité en est une, soumise aux mêmes limites : c'est elle qui déborde quand une récursion ne s'arrête pas. Le parcours d'architecture montre comment la machine la range en mémoire.

La file : premier arrivé, premier servi

Une file demande deux indices au lieu d'un, et cela change tout. Les deux avancent dans le même sens, jamais en arrière : au fil des retraits, la tête s'éloigne du début du tableau et laisse derrière elle des cases inutilisables. Un tableau de quatre cases se trouverait plein après quatre ajouts, même si trois éléments en sont déjà sortis.

Le remède consiste à refermer le tableau sur lui-même : passé la dernière case, l'indice suivant est la première. Avec des cases numérotées de 1 à capacite, la case qui suit la case i est i + 1, sauf la dernière, dont la suivante est la première. Le reste de la division par la capacité fait ce travail, à un décalage près : pour une capacité de 4, i MOD 4 vaut 1, 2, 3 puis 0 quand i vaut 1, 2, 3 puis 4, et ajouter 1 donne 2, 3, 4 puis 1. D'où (indice MOD capacite) + 1, qui avance d'une case et revient au début après la dernière : c'est ce qu'on appelle un tableau circulaire.

Un atelier reçoit cinq ordres de fabrication, de OF1 à OF5, et les traite dans leur ordre d'arrivée ; sa file d'attente ne tient que quatre ordres.

55 pas. La rotation se lit dans la sortie : OF4 prend la case 4, puis OF5 revient occuper la case 1, libérée par le départ de OF1. Les cinq ordres ressortent malgré tout dans leur ordre d'arrivée, de OF1 à OF5, sur un tableau qui n'a jamais compté plus de quatre cases. Cette figure n'a pas de garde, parce que ses arrivées sont connues d'avance. Une file réelle en demande deux, symétriques de celles de la pile : tester nb = capacite avant d'enfiler, et nb = 0 avant de défiler.

Une pile pour les parenthèses

Une expression parenthésée est le meilleur usage de pile qui soit, parce que la règle des parenthèses est exactement la discipline d'une pile : la parenthèse qu'une fermante referme est toujours la dernière ouverte.

Le moteur ne sait pas découper un texte caractère par caractère ; l'expression s'écrit donc comme un tableau de symboles. La pile retient la position de chaque ouvrante en attente.

39 pas. L'appariement est annoncé au passage : la fermante 8 referme l'ouvrante 4, la fermante 9 referme l'ouvrante 1. Un sommet revenu à zéro à la fin du parcours signe une expression équilibrée.

Retirer la dernière parenthèse fermante suffit à faire parler l'algorithme :

35 pas, et le diagnostic est précis : il manque une fermante, et l'ouvrante restée en attente est celle de la position 1. Une pile ne se contente pas de compter, elle sait laquelle attend encore.

Une pile pour évaluer

Le comptage n'était qu'un échauffement. Avec deux piles, l'une pour les valeurs et l'autre pour les opérateurs, une expression s'évalue en un seul parcours, à une condition que l'algorithme ne vérifie pas : chaque opération doit avoir ses propres parenthèses, comme dans ((3 + 4) * (10 - 1)). Chaque fermante déclenche alors une opération, sur les deux valeurs et l'opérateur les plus récents. Le tableau expr mêle cette fois des textes et des nombres, ce que le chapitre sur les tableaux évite : c'est le prix d'une expression écrite sans découpage de texte.

111 pas pour obtenir 63. L'ordre des calculs annoncés est celui que les parenthèses imposent : 3 + 4 d'abord, puis 10 - 1, puis le produit des deux résultats. La première valeur dépilée est l'opérande de droite, la dernière arrivée : pour 10 - 1, b reçoit 1 et g reçoit 10 ; dépiler dans l'autre ordre calculerait 1 - 10.

Aucune règle de priorité n'a été écrite : dans une expression entièrement parenthésée, les parenthèses fixent seules l'ordre des calculs. Sur (3 + 4) * 2, où le produit n'a pas les siennes, le même algorithme affiche 7 au lieu de 14, sans rien signaler ; sur (10 - 2 - 3), il affiche 10 au lieu de 5. C'est l'hypothèse non vérifiée du chapitre sur la dichotomie, sous une autre forme : l'algorithme exige une propriété de ses données, et doit l'énoncer. Évaluer une expression ordinaire demande en plus des règles de priorité entre opérateurs, que ce chapitre n'aborde pas.

Le point remarquable est ce qui se passe quand l'expression est mal formée. Une parenthèse fermante de trop réclame une valeur dans une pile déjà vide, et la faute vue plus haut hors contexte se produit ici en situation, sur le même algorithme :

La première fermeture réussit et affiche 7. La seconde s'interrompt sur l'indice 0 : la pile des valeurs est vide, il n'y a plus rien à dépiler. Un retrait à vide n'est donc pas un cas d'école : c'est la forme que prend une expression mal parenthésée dans un algorithme qui ne s'en garde pas, à l'endroit exact où la fermante est en trop. La garde tient en quelques lignes, et elle change un arrêt en diagnostic. Sur l'appariement des parenthèses, elle donne ceci :

43 pas, et le diagnostic est complet : la fermante 4 ne referme rien, l'algorithme va quand même au bout, et il compte une fermante en trop. Sur les deux expressions de la section précédente, il donne exactement les mêmes sorties qu'avant.

Une file pour parcourir en largeur

Changer la discipline change l'ordre de visite, et rien d'autre. Un graphe est un ensemble de points reliés par des flèches : les cinq postes d'un atelier, par exemple, et les convoyeurs qui mènent de l'un à l'autre. Chaque flèche, ou arc, part d'un poste et en atteint un autre ; les postes que l'on atteint directement depuis un poste sont ses voisins. Pour ne pas les confondre avec le sommet d'une pile, ces points s'appellent ici des postes ; le chapitre sur les graphes les nomme des sommets. Un parcours qui explore un graphe en s'appuyant sur une file visite d'abord tous les voisins immédiats du poste de départ, puis leurs voisins, et ainsi de suite : c'est le parcours en largeur.

Le graphe est donné par ses arcs, dans deux tableaux parallèles de même longueur : le premier arc va du poste depart[1] au poste arrivee[1], c'est-à-dire de 1 à 2, le dernier de 4 à 5.

120 pas, et l'ordre de visite est 1, 2, 3, 4, 5 : le poste 1, puis ses deux voisins 2 et 3, puis ce qu'ils atteignent. Chaque poste n'entrant qu'une fois dans la file, grâce à vu, cinq cases suffisent, et la rotation est inutile. Remplacer la file par une pile donne un parcours qui s'enfonce le long d'un chemin avant de revenir, proche du parcours en profondeur ; les deux parcours, et la place exacte de la marque dans chacun, sont traités dans le chapitre sur les parcours de graphes.

Mettre en pratique

Une pile ou une file se suit sans rien dérouler, à condition de compter les gestes et d'appliquer les gardes.