Le bouton Annuler et la file de l’imprimante
Une pile et une file sont deux façons de ranger des données en attendant de s’en servir. Elles se cachent derrière le bouton Annuler d’un logiciel et derrière la file d’attente d’une imprimante.
La différence tient à une question : quel élément sort en premier ?
À la fin de cette leçon
Remarque
Je peux utiliser une pile et une file pour ranger et reprendre des données.
Mots clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Pile | une liste où le dernier arrivé est le premier sorti | |
| File | une liste où le premier arrivé est le premier sorti | |
| 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 l’élément du début de la file | pop(0) |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une pile, c’est comme une pile d’assiettes
Tu poses une assiette sur le dessus. Tu reprends aussi celle du dessus. La dernière posée est la première reprise.
On dit dernier arrivé, premier sorti. Empiler ajoute au dessus. Dépiler retire le dessus. En Python, une liste avec append et pop() fait une pile.
Lance une pile : le bouton Annuler
actions = []
actions.append("écrire un mot")
actions.append("mettre en gras")
actions.append("effacer une ligne")
print("pile :", actions)
# Annuler retire la dernière action faite.
derniere = actions.pop()
print("annulé :", derniere)
print("pile :", actions)
# Appuie encore sur Annuler : ajoute deux lignes pop().
Une file, c’est comme la queue d’une caisse
Le premier client arrivé est le premier servi. Les nouveaux se placent à la fin.
On dit premier arrivé, premier sorti. Enfiler ajoute à la fin. Défiler retire au début. En Python, append et pop(0) font une file.
Lance une file : l’imprimante du lycée
impressions = []
impressions.append("devoir de Lola")
impressions.append("affiche du club")
impressions.append("menu de la cantine")
print("file :", impressions)
# L'imprimante prend toujours le premier document.
en_cours = impressions.pop(0)
print("imprimé :", en_cours)
print("file :", impressions)
# Ajoute un document, puis imprime encore deux fois.
Exemple travaillé : même suite, deux sorties
| On ajoute dans l’ordre | Pile : ordre de sortie | File : ordre de sortie |
|---|---|---|
| A, B, C | C, B, A | A, B, C |
| 1, 2, 3, 4 | 4, 3, 2, 1 | 1, 2, 3, 4 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une pile vérifie les parenthèses
Une calculatrice doit vérifier que (2 + (3 * 4)) est bien écrit. Chaque parenthèse ouvrante doit avoir sa fermante.
On empile chaque ( rencontrée. À chaque ), on dépile. Si la pile est vide à ce moment, ou pleine à la fin, le texte est mal écrit.
Exemple travaillé : lire ( ( ) ( ) )
| Caractère lu | Action | Pile après |
|---|---|---|
| ( | on empile | ( (taille 1) |
| ( | on empile | ( ( (taille 2) |
| ) | on dépile | ( (taille 1) |
| ( | on empile | ( ( (taille 2) |
| ) | on dépile | ( (taille 1) |
| ) | on dépile | vide |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Lance le vérificateur de parenthèses simples
def parentheses_simples(texte):
pile = []
for caractere in texte:
if caractere == "(":
pile.append(caractere)
if caractere == ")":
if len(pile) == 0:
return False # une fermante sans ouvrante
pile.pop()
return len(pile) == 0 # il ne doit rien rester
print(parentheses_simples("(()())"))
print(parentheses_simples("(()"))
print(parentheses_simples(")("))
# Le devoir ajoute les crochets et les accolades.
Empile trois lettres et dépile une fois
docker exec jupyter python3 -c "pile = ['a', 'b']; pile.append('c'); print(pile.pop(), pile)"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.
Défile le premier jour du fichier du lab
docker exec jupyter python3 -c "import csv; file = [x['weekday'] for x in csv.DictReader(open('hires.csv'))][:3]; print(file.pop(0), file)"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.
Utilise la file toute faite de Python
docker exec jupyter python3 -c "import collections; f = collections.deque([1, 2, 3]); print(f.popleft(), 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.
Ce que disent les trois Runs
Le premier Run affiche c ['a', 'b']. On a empilé a, b, c, puis dépilé : c sort, a et b restent.
Le deuxième prend les trois premiers jours du fichier. Il affiche Wed ['Thu', 'Fri'] : le premier jour sort, les deux autres attendent.
Le troisième utilise collections.deque, une vraie file. popleft retire le premier et affiche 1 deque([2, 3]).
Une erreur fréquente
Attention
Beaucoup pensent que pop() et pop(0) font la même chose. pop() retire le dernier élément : c’est une pile. pop(0) retire le premier : c’est une file. Pour choisir, demande-toi quel élément doit sortir en premier.
Pour aller plus loin : inverser un mot
Une pile inverse l’ordre. Empile chaque lettre de "cinema", puis dépile tout dans une nouvelle chaîne.
Que donne ce programme sur "radar" ? Pourquoi ce mot est-il spécial ?