Les piles et les files
Un tableau permet d'ajouter et de retirer n'importe où. Mais deux manières disciplinées de l'utiliser sont si utiles qu'elles ont un nom : la pile et la file.
La pile : dernier arrivé, premier sorti
Pense à une pile d'assiettes : on pose une assiette sur le dessus, et on reprend toujours celle du dessus. La dernière posée est la première retirée.
Avec un tableau :
- empiler :
ajoute place l'élément à la fin ; - regarder le sommet :
dernier(tableau) ; - dépiler : on supprime le dernier élément.
assiettes est un tableau
assiettes ajoute 'bleue'
assiettes ajoute 'rouge'
assiettes ajoute 'verte'
affiche 'Au sommet : ' + dernier(assiettes) // verte
assiettes supprime longueur(assiettes) - 1
affiche 'Au sommet : ' + dernier(assiettes) // rouge
Le dernier élément est à l'index longueur(assiettes) - 1 : c'est lui qu'on supprime.
Une pile pour annuler
Le bouton « Annuler » d'un logiciel fonctionne avec une pile : chaque action est empilée, et annuler revient à dépiler la dernière.
historique est un tableau
historique ajoute 'écrire Bonjour'
historique ajoute 'mettre en gras'
historique ajoute 'changer la couleur'
affiche 'Annulation de : ' + dernier(historique)
historique supprime longueur(historique) - 1
affiche 'Annulation de : ' + dernier(historique)
historique supprime longueur(historique) - 1
affiche 'Il reste ' + longueur(historique) + ' action dans l’historique.'
Les actions sont annulées dans l'ordre inverse où elles ont été faites.
Question : On empile A, puis B, puis C. Dans quel ordre sortent-ils de la pile ? — C, B, A. Dernier arrivé, premier sorti : C sort d'abord, puis B, puis A.
La file : premier arrivé, premier sorti
Pense à la queue à la cantine : le premier arrivé est le premier servi.
- entrer dans la file :
ajoute place à la fin ; - voir le premier :
premier(tableau) ; - servir : on supprime l'élément à l'index 0.
attente est un tableau
attente ajoute 'Léa'
attente ajoute 'Tom'
attente ajoute 'Inès'
tant que longueur(attente) > 0
affiche 'On sert ' + premier(attente)
attente supprime 0
affiche 'Encore ' + longueur(attente) + ' personnes dans la file'
fin tant que
Léa est servie la première, puis Tom, puis Inès : exactement l'ordre d'arrivée.
Une pile pour vérifier des parenthèses
Dans le calcul (3 + (4 * 2)), les parenthèses sont-elles bien fermées ? Un problème classique, résolu par une pile :
- on rencontre
( : on l'empile ; - on rencontre
) : on dépile une parenthèse ouvrante. S'il n'y en a pas, c'est une erreur ; - à la fin, la pile doit être vide.
fonction estEquilibre(formule)
ouvertes est un tableau
symbole est un texte
pour i de 1 à longueur(formule)
symbole vaut copier(formule, i, 1)
si symbole = '(' alors
ouvertes ajoute symbole
sinon si symbole = ')' alors
si longueur(ouvertes) = 0 alors
retourne faux
fin si
ouvertes supprime longueur(ouvertes) - 1
fin si
fin pour
retourne longueur(ouvertes) = 0
fin fonction
affiche estEquilibre('(3 + (4 * 2))') // vrai
affiche estEquilibre('(3 + 4))') // faux
affiche estEquilibre('((3 + 4)') // faux
Dans le deuxième exemple, une parenthèse se ferme alors que la pile est vide. Dans le troisième, il reste une parenthèse dans la pile à la fin. C'est ainsi que CoddyRun lui-même vérifie tes programmes !
En résumé
- Pile : on ajoute et on retire au même bout. Dernier arrivé, premier sorti.
- File : on ajoute à la fin, on retire au début. Premier arrivé, premier sorti.
ajoute, dernier, premier et supprime suffisent pour les programmer.- La pile sert à annuler, à vérifier des parenthèses ; la file à traiter des demandes dans l'ordre.
