Piles et files
Ce que ce chapitre apporte
- Distinguer les deux disciplines d'accès, dernier arrivé premier servi et premier arrivé premier servi.
- Tenir une pile sur un tableau et un indice de sommet, et en écrire les deux opérations.
- Tenir une file sur un tableau circulaire, et suivre la rotation des indices.
- Reconnaître le débordement et le retrait à vide, et poser la garde qui les empêche.
- Employer une pile pour évaluer une expression parenthésée et une file pour un parcours en largeur.
Un tableau range des valeurs côte à côte et laisse choisir laquelle lire. Une pile et une file retirent ce choix : la pile rend toujours la dernière arrivée, la file toujours la première. Cette contrainte volontaire est ce qui rend possibles l'annulation d'une action, l'évaluation d'une expression parenthésée et le parcours en largeur d'un graphe. Ni l'une ni l'autre n'existe dans ce pseudo-code : elles se tiennent à la main, sur un tableau et un indice.
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
Une pile est une collection où l'on ne peut ajouter et retirer qu'à une seule extrémité, appelée le sommet. Le dernier élément rangé est donc le premier disponible. Les deux opérations portent les noms d'empiler et de dépiler.
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.
programme principal
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'ordre dans l'une des deux paires écrase une valeur ou en relit une déjà retirée.
Le contenu des cases au-dessus du sommet n'est jamais effacé au retrait : sommet ← sommet - 1 suffit, parce que la case redevient libre par définition et sera réécrite à la prochaine addition. Suivre la figure pas à pas rend la chose visible : le tableau p garde ses anciennes valeurs, et seule la position du sommet décide de ce qui existe.
Les deux fautes réelles
Une pile tenue à la main a deux façons de mal tourner, et une seule d'entre elles s'annonce.
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 :
programme principal
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. Rien ne le signale non plus de soi-même ; la seule protection est un test écrit avant l'écriture.
programme principal
27 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.
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 seules fautes possibles de la structure. La pile des appels de fonction est soumise aux mêmes limites, et le module d'architecture montre comment la machine la range en mémoire.
La file : premier arrivé, premier servi
Une file est une collection où l'on ajoute à une extrémité, la queue, et où l'on retire à l'autre, la tête. Le premier élément arrivé est donc le premier servi. Les deux opérations portent les noms d'enfiler et de défiler.
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 additions, même si trois ont déjà été retirées.
Le remède consiste à refermer le tableau sur lui-même : passé la dernière case, l'indice suivant est la première. C'est ce que fait (indice MOD capacite) + 1, et c'est ce qu'on appelle un tableau circulaire.
programme principal
55 pas. La rotation se lit dans la sortie : t4 prend la case 4, puis t5 revient occuper la case 1, libérée par le départ de t1. Les cinq tâches ressortent malgré tout dans leur ordre d'arrivée, t1 à t5, sur un tableau qui n'a jamais compté plus de quatre cases.
Tenter de déduire si la file est vide ou pleine de la seule comparaison entre tete et queue. Les deux indices sont égaux dans les deux cas, et rien ne les distingue. Le compteur nb existe pour cela : il est la seule information qui tranche, et son oubli produit une file qui se croit vide alors qu'elle est pleine.
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.
programme principal
40 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 :
programme principal
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, la même expression s'évalue en un seul parcours : chaque fermante déclenche une opération, sur les deux valeurs et l'opérateur les plus récents.
programme principal
122 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. Aucune règle de priorité n'a été écrite ; les parenthèses et la pile suffisent.
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 :
programme principal
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 façon dont une expression mal parenthésée se manifeste.
Une file pour parcourir en largeur
Changer la discipline change l'ordre de visite, et rien d'autre. Un parcours qui explore un graphe en s'appuyant sur une file visite d'abord tous les voisins immédiats du point 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.
programme principal
120 pas, et l'ordre de visite est 1, 2, 3, 4, 5 : le sommet 1, puis ses deux voisins 2 et 3, puis ce qu'ils atteignent. Remplacer la file par une pile, sans changer une seule autre ligne, donnerait un parcours en profondeur, qui s'enfonce le long d'un chemin avant de revenir. Les deux parcours et leurs usages respectifs sont traités dans le chapitre sur les parcours de graphes.
Le tableau vu n'est pas un raffinement. Sans lui, un sommet accessible par deux chemins serait enfilé deux fois, et un cycle ferait tourner la boucle indéfiniment jusqu'au plafond de pas. La marque se pose à l'enfilement, pas à la visite : posée trop tard, elle laisse le temps à un second exemplaire d'entrer dans la file.
Vérification
1.Qu'est-ce qui distingue une pile d'une file ?
2.Dans une pile tenue sur un tableau, que vaut sommet quand la pile est vide ?
3.Pourquoi une file se tient-elle sur un tableau circulaire ?
4.Dans une file circulaire, tete et queue sont égaux. Que peut-on en déduire ?
5.Pourquoi une pile convient-elle à l'évaluation d'une expression parenthésée ?
La méthode
- Choisir la discipline avant la structure. La question n'est pas où ranger, mais lequel doit ressortir en premier : la réponse désigne la pile ou la file.
- Tenir une pile avec un tableau et un indice, en respectant l'ordre des deux lignes : monter puis écrire pour empiler, lire puis descendre pour dépiler.
- Tenir une file avec deux indices et un compteur, et faire tourner chaque indice par
(indice MOD capacite) + 1. - Poser les deux gardes avant toute autre chose : pas de retrait à sommet nul, pas d'ajout à capacité atteinte.
- Déduire l'état de la file du compteur, jamais de la seule comparaison des deux indices.
- Marquer un élément au moment où il entre dans la file, et non au moment où il en sort, sous peine de le traiter deux fois.
Synthèse
- Une pile sert le dernier arrivé, une file le premier : deux disciplines d'accès, et rien d'autre ne les distingue.
- Une pile tient sur un tableau et un indice de sommet ; empiler et dépiler font deux lignes chacun.
- Une file tient sur un tableau circulaire, avec une tête, une queue et un compteur qui seul dit si elle est vide ou pleine.
- Le débordement et le retrait à vide sont les deux seules fautes de la structure, et deux tests écrits à la main les couvrent toutes les deux.
- Une pile apparie les parenthèses et évalue l'expression qu'elles délimitent ; une file donne le parcours en largeur, dont le pendant en profondeur s'obtient en changeant la seule structure.
Le chapitre suivant abandonne le rangement côte à côte : chaque valeur y désignera elle-même la suivante, ce qui rend immédiat ce qu'un tableau rend coûteux et inversement. C'est l'objet de chaîner les données.