Annuler une frappe, imprimer à la reprographie
Une pile est une structure où le dernier élément posé est le premier retiré. Une file est une structure où le premier arrivé est le premier servi. Savoir choisir entre les deux règle beaucoup de problèmes de programmation.
Le bouton Annuler d’un traitement de texte défait d’abord votre dernière action. La reprographie de la faculté imprime d’abord le premier document reçu. Ce sont une pile et une file.
À la fin de cette leçon
Remarque
Je peux utiliser une pile et une file pour résoudre un problème.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Pile | une liste où l’on ajoute et retire par le même bout | |
| File | une liste où l’on ajoute à un bout et retire à l’autre | |
| Empiler | poser un élément sur le dessus de la pile | append |
| Dépiler | retirer l’élément du dessus de la pile | pop |
| Enfiler | ajouter un élément à la fin de la file | |
| Défiler | retirer le premier élément de la file |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une pile retire d’abord le dernier arrivé
Pensez à une pile d’assiettes. On pose une assiette sur le dessus, et on reprend celle du dessus. La dernière posée sort la première.
C’est la règle LIFO, en anglais last in, first out : dernier entré, premier sorti. Empiler et dépiler ne touchent que le dessus. Chacun ne coûte qu’une étape, même avec un million d’éléments.
Exemple travaillé : le bouton Retour d’un navigateur
| Action | Pile après | Page affichée |
|---|---|---|
| Ouvrir accueil | accueil | accueil |
| Ouvrir recherche | accueil, recherche | recherche |
| Ouvrir article | accueil, recherche, article | article |
| Retour | accueil, recherche | recherche |
| Retour | accueil | accueil |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une pile de pages à lancer
# L’historique d’un navigateur : une pile de pages.
historique = []
historique.append("accueil")
historique.append("recherche")
historique.append("article")
print("pile :", historique)
page = historique.pop()
print("on quitte :", page)
print("on revient à :", historique[len(historique) - 1])
# Ajoutez une page, puis revenez deux fois en arrière.
Dans le labo, une liste sert de pile
Les deux commandes suivantes utilisent une liste Python comme pile. La première empile trois lettres, dépile une fois, puis affiche la lettre dépilée et ce qui reste.
La seconde empile les lettres du mot REPAS, puis les dépile toutes. Le mot sort à l’envers : une pile renverse l’ordre.
Empiler trois lettres, dépiler une fois
python3 -c "p = []; p.append('a'); p.append('b'); p.append('c'); print(p.pop(), p)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Lire un mot à l’envers avec une pile
python3 -c "p = []; [p.append(c) for c in 'REPAS']; print(''.join(p.pop() for _ in range(5)))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une file sert d’abord le premier arrivé
Dans la file d’attente d’un restaurant universitaire, la première personne arrivée est servie la première. C’est la règle FIFO, en anglais first in, first out : premier entré, premier sorti.
On enfile à une extrémité et on défile à l’autre. Avec une liste, pop(0) fait reculer toutes les valeurs, ce que la leçon 1 a montré lent. Le type deque du module collections défile en une seule étape.
Exemple travaillé : une file d’impression
| Action | File après | Imprimé |
|---|---|---|
| Léa envoie | Léa | Rien |
| Karim envoie | Léa, Karim | Rien |
| Inès envoie | Léa, Karim, Inès | Rien |
| L’imprimante prend un travail | Karim, Inès | Léa |
| L’imprimante prend un travail | Inès | Karim |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Enfiler deux lettres, défiler une fois
python3 -c "from collections import deque; f = deque(); f.append('a'); f.append('b'); print(f.popleft(), list(f))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une pile vérifie les parenthèses
Un compilateur doit vérifier que chaque parenthèse ouverte est refermée, dans le bon ordre. On lit le texte de gauche à droite.
Une ouvrante s’empile. Une fermante doit correspondre à l’ouvrante du dessus, qu’on dépile. À la fin d’un texte correct, la pile est vide.
Exemple travaillé : ([x]) puis ([)]
| Texte | Caractère | Action | Pile |
|---|---|---|---|
| ([x]) | ( | Empiler | ( |
| ([x]) | [ | Empiler | (, [ |
| ([x]) | x | Ignorer | (, [ |
| ([x]) | ] | Dépiler [, il correspond | ( |
| ([x]) | ) | Dépiler (, il correspond | Vide : correct |
| ([)] | ) | Le dessus est [ : refus | Incorrect |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Erreur fréquente
Attention
Beaucoup de gens pensent qu’il suffit de compter : autant d’ouvrantes que de fermantes. Ce n’est pas assez. ([)] a deux paires, mais il n’est pas équilibré. L’ordre compte, et seule une pile le garde.
Pour aller plus loin
Écrivez une fonction qui inverse un mot avec une pile : empilez chaque lettre, puis dépilez-les dans un nouveau mot.
Remplacez ensuite la pile par une file. Prédisez le mot obtenu pour REPAS, puis vérifiez. Expliquez la différence en une phrase.