Piles et files
Comparer LIFO et FIFO, implémenter leurs opérations en Python et choisir la structure qui respecte l’ordre de traitement.
Environ 40 minutes
- Tracer les opérations d’une pile et d’une file
- Implémenter ajout, retrait et test du vide
- Utiliser une pile pour vérifier un emboîtement
Un historique d’annulation et une file d’attente doivent-ils retirer la même action en premier ?
Annuler demande de revenir sur l’action la plus récente. Servir des demandes dans leur ordre d’arrivée impose au contraire de commencer par la plus ancienne. Une pile et une file stockent toutes deux une suite de valeurs, mais leurs règles d’accès diffèrent. Tu vas suivre leurs états, écrire des opérations Python et résoudre un problème d’emboîtement. Prérequis : listes, fonctions, boucles et interface d’une structure de données.
1. Une pile donne la priorité au dernier ajout
Une pile suit la règle LIFO, dernier entré, premier sorti. L’ajout et le retrait ont lieu à la même extrémité, appelée sommet. L’interface minimale propose créer, empiler, dépiler et tester le vide. Consulter le sommet sans le retirer peut être une opération supplémentaire. Le contrat doit distinguer cette consultation d’un dépilement. Dépiler exige ici une pile non vide. Si la structure est vide, il faut soit éviter l’appel en testant cette condition, soit appliquer la convention d’erreur imposée par l’interface.
Avec une liste Python, on choisit la fin comme sommet. L’ajout se fait par append et le retrait par pop sans argument. La liste [] représente une pile vide et not pile teste son vide. On peut lire pile[-1] pour consulter le sommet, seulement si la pile est non vide. Cette représentation utilise une liste généraliste, mais le programme utilisateur doit respecter les opérations de pile. Insérer ou supprimer au milieu reste possible sur une liste Python ; cela ne fait pas partie du fonctionnement abstrait que nous avons choisi.
Exemple résolu
Trace p = [], puis empile 3, empile 5, dépile, empile 8, dépile.
- Étape 1 : Les deux premiers ajouts donnent la représentation [3, 5], avec 5 au sommet.
- Étape 2 : Le premier retrait renvoie 5 et laisse [3]. L’ajout de 8 donne [3, 8].
- Étape 3 : Le second retrait renvoie 8 et laisse [3]. On a produit deux résultats dans l’ordre 5 puis 8.
Résultat : La pile finale contient seulement 3. À chaque retrait, l’élément le plus récemment ajouté parmi ceux encore présents sort.
Piège à éviter : Décrire tous les retraits comme l’inverse de tous les ajouts ne suffit pas quand ajouts et retraits sont alternés.
À toi d'essayer
Dans une pile représentée par [2, 7, 4], sommet à droite, quelle opération consulte 4 sans modifier la pile ?
Voir la réponseMasquer la réponse
La lecture p[-1] consulte le dernier élément. p.pop() renverrait aussi 4, mais modifierait la pile en le retirant.
2. Une file conserve l’ordre d’arrivée
Une file suit la règle FIFO, premier entré, premier sorti. On enfile à une extrémité et on défile à l’autre. Après les arrivées A, B puis C, un retrait fournit A. Si D arrive ensuite, B et C restent prioritaires sur D. Cette règle est adaptée à un traitement d’attente ordinaire sans priorité supplémentaire. Une structure qui trie les demandes par urgence obéit à une autre interface ; il faut donc lire la situation avant de choisir une file.
Une liste Python peut réaliser cette règle avec append pour l’ajout et pop(0) pour le retrait. Cependant, retirer au début décale les références restantes, avec un coût qui croît avec la longueur. La classe deque du module collections est adaptée aux opérations aux extrémités. On utilise append à droite et popleft à gauche. Une autre réalisation peut employer deux piles, avec transfert seulement quand la pile de sortie est vide. Ces représentations différentes doivent conserver les mêmes résultats observables.
Exemple résolu
Avec une deque, enfile A et B, défile une demande, puis enfile C.
- Étape 1 : Importe la classe et effectue les opérations.from collections import deque
f = deque()
f.append('A')
f.append('B')
x = f.popleft()
f.append('C') - Étape 2 : Le retrait fournit A. La structure contient ensuite B, puis C dans l’ordre d’attente.
- Étape 3 : Deux nouveaux appels de popleft produiront B puis C. La file sera alors vide.
Résultat : x vaut A et l’état final du scénario contient B avant C. Utiliser pop à la place de popleft aurait retiré B au premier retrait.
Piège à éviter : Confondre les extrémités transforme le service attendu et peut traiter une demande récente avant une ancienne.
On ne juge pas une implémentation seulement sur un scénario où tous les éléments sont égaux. Si la file contient trois fois la même valeur, un retrait par la mauvaise extrémité peut produire le même affichage. Choisis des valeurs distinctes et alterne les opérations. Vérifie aussi le passage d’un élément à zéro élément, puis l’ajout après ce retour au vide. Ces cas révèlent les erreurs de suivi de tête ou de sommet que les gros exemples peuvent masquer.
À toi d'essayer
Un traitement reçoit X, Y puis Z. Il retire Z puis Y. Est-ce compatible avec une file FIFO sans opération intermédiaire ?
Correction détaillée pas à pasDans ce chapitre : 2 corrections détaillées.
3. Une pile pour des parenthèses bien emboîtées
Pour chaque parenthèse ouvrante, on attend une fermeture correspondante. La dernière ouverture encore en attente doit être fermée en premier : c’est précisément une règle de pile. On parcourt le texte de gauche à droite. Une ouverture est empilée. Une fermeture demande une ouverture disponible ; sinon, le texte est incorrect. À la fin, aucune ouverture ne doit rester. Nous traitons seulement les parenthèses rondes ; les autres caractères sont ignorés. Pour plusieurs familles de délimiteurs, il faudrait mémoriser leur type et vérifier chaque correspondance.
Exemple résolu
Écris une fonction pour les parenthèses rondes et applique-la à "(a+(b))" puis à ")(".
- Étape 1 : Vérifie l’emboîtement.def equilibre(texte):
pile = []
for caractere in texte:
if caractere == '(':
pile.append(caractere)
elif caractere == ')':
if not pile:
return False
pile.pop()
return not pile - Étape 2 : Dans le premier texte, les deux ouvertures sont retirées par les deux fermetures. La pile finit vide et aucune fermeture n’est arrivée trop tôt.
- Étape 3 : Dans le second texte, la première fermeture trouve une pile vide. La fonction renvoie immédiatement False, même si une ouverture suit.
Résultat : equilibre("(a+(b))") vaut True ; equilibre(")(") vaut False. Le texte vide est accepté : il ne contient aucune ouverture en attente ni aucune fermeture sans ouverture.
Piège à éviter : Compter seulement les ouvertures et les fermetures accepterait à tort ")(", car l’égalité des nombres ne prouve pas le bon ordre.
L’invariant explique la fonction : après chaque préfixe du texte qui n’a pas été rejeté, la pile contient les ouvertures non encore fermées dans l’ordre où elles ont été rencontrées. Une fermeture enlève la plus récente. Si aucune n’existe, aucune suite du texte ne peut réparer cette fermeture déjà placée trop tôt. Le retour anticipé est donc justifié. Le test final détecte l’autre défaut possible : une ou plusieurs ouvertures n’ont jamais été fermées. Les tests et l’invariant traitent deux rôles complémentaires, observation d’exemples et justification générale.
À toi d'essayer
On veut étendre le contrôle aux crochets et aux parenthèses. Pourquoi une pile qui mémorise seulement le nombre d’ouvertures ne suffit-elle pas ? Donne un cas qui la trompe.
Correction détaillée pas à pasDans ce chapitre : 2 corrections détaillées.
4. Au bac : choisir l’ordre avant le code
Au bac : résoudre un exercice de pile ou de file
- Identifie l’ordre attendu dans la situation : dernière action pour annuler, première demande pour servir, dernière ouverture pour fermer.
- Écris le contrat des opérations et précise l’extrémité choisie dans la représentation.
- Trace un tableau avec opération, valeur renvoyée et état restant. N’oublie pas les opérations qui ne renvoient rien.
- Contrôle les structures vides avant tout retrait, selon les préconditions du sujet.
- Teste les opérations alternées et explique pourquoi la structure choisie conserve la règle de traitement.
Les piles interviennent dans les retours en arrière, l’emboîtement et la mémorisation d’un travail à reprendre. Les files servent lorsqu’un traitement doit respecter l’antériorité des demandes, ou explorer des situations par vagues successives. Ces usages ne sont pas des définitions à apprendre sans contexte : demande toujours ce qu’un retrait doit produire. Dans un exercice, changer de bibliothèque ne résout pas une erreur d’ordre. Une deque utilisée avec append et pop se comporte comme une pile, malgré son nom ; c’est le jeu des opérations qui réalise l’abstraction.
Vocabulaire
- Sommet :
- Extrémité par laquelle une pile ajoute et retire ses éléments.
- Empiler :
- Ajouter au sommet d’une pile.
- Défiler :
- Retirer et renvoyer l’élément le plus ancien d’une file.
- Préfixe :
- Début d’une séquence, éventuellement vide ou égal à la séquence entière.
Comparer les retraits
| Structure | Priorité | Python |
|---|---|---|
| Pile | Plus récent | append et pop en fin. |
| File | Plus ancien | append et popleft sur deque. |
S’entraîner : ouvre l’espace Exercices du site.
À retenir
- Une pile suit LIFO et une file suit FIFO.
- La pile utilise un sommet commun à l’ajout et au retrait.
- Un retrait sur une structure vide doit respecter la convention du contrat.
- Des nombres égaux de parenthèses ouvrantes et fermantes ne garantissent pas leur bon ordre.
Fiche de révision
Dans une trace, sépare systématiquement résultat produit et état conservé.
Pour révéler le mauvais choix d’extrémité, utilise plusieurs valeurs distinctes.
Un contrôle d’emboîtement rejette une fermeture trop tôt et des ouvertures restantes à la fin.
Un outil général comme une liste ou une deque réalise une abstraction selon les opérations que tu choisis.
Questions fréquentes
Une file peut-elle utiliser deux piles ?
Oui, en inversant les valeurs vers une pile de sortie uniquement lorsque cette dernière est vide.
Une liste Python est-elle automatiquement une pile ?
Non. Elle réalise une pile quand on limite les opérations à la discipline choisie, par exemple append et pop en fin.
Et maintenant ?
Tu as lu le cours. L’étape suivante tient en une action.
Relis le coursReprends l’essentiel avant de passer à la suite.Prolonge l’expérience !
Continue à explorer ce chapitre à travers de nouvelles activités, des défis et des expériences interactives. Avec Premium, l’apprentissage continue !
Ici, tu débloques aussi 2 corrections détaillées.
Parent ? Suivez les progrès de votre enfant.
