Piles et files

Vue d'ensemble

Une pile et une file sont deux façons d'organiser une collection d'éléments qui ne diffèrent que par l'ordre de sortie. Dans une pile, on sort toujours le dernier entré (comme une pile d'assiettes) ; dans une file, on sort toujours le premier entré (comme une file d'attente). Ces deux structures sont partout : historique de navigation, annuler/refaire, parcours de graphes, gestion de tâches. Cette fiche te fait écrire chaque opération en Python, la décrypter ligne par ligne, en analyser le coût, et t'exerce sur l'application reine : la vérification du parenthésage.

Au programme (tronc commun, 1^re année — BO 2021) — Structures de données : piles (LIFO) et files (FIFO) ; opérations de base et leur coût ; implémentation à l'aide des listes Python ; exemples d'utilisation (dont la vérification d'un bon parenthésage).

Prérequis

Manipuler les listes Python : append, pop, indexation t[-1], longueur len(t)
Boucle for sur une chaîne ou une liste, boucle while
Notion de coût d'une opération en $O (1)$ / $O (n)$

🎯 Accompagnement Majorant

Tu confonds encore « dernier entré » et « premier entré » sous la pression du DS ? Les structures de données sont le socle de toute l'informatique de prépa. Nos mentors alumni X · Centrale · Mines t'entraînent à choisir la bonne structure et à dérouler ses opérations à la main, jusqu'à ce que ce soit un réflexe.

Trouver un mentor →

1. La pile — LIFO

Définition 1.1 — Pile

Une pile (en anglais stack) est une structure dans laquelle le dernier élément entré est le premier sorti : on dit qu'elle est LIFO (Last In, First Out). On y accède uniquement par le sommet. Les opérations de base sont :

empiler (push) : ajouter un élément au sommet ;
dépiler (pop) : retirer et renvoyer l'élément du sommet ;
sommet : lire l'élément du sommet sans le retirer ;
pile vide ? : tester si la pile ne contient aucun élément.

💡 L'analogie de la pile d'assiettes. Tu empiles les assiettes propres les unes sur les autres. Pour en prendre une, tu prends celle du dessus — la dernière posée. Impossible d'attraper celle du fond sans enlever d'abord toutes celles du dessus. C'est exactement le comportement LIFO.

2. Implémenter une pile avec une liste

En Python, une simple liste fait une excellente pile : on considère que le sommet est la fin de la liste. La méthode append empile et la méthode pop (sans argument) dépile — et les deux coûtent $O (1)$ .

pile = []              # une pile vide

pile.append(1)         # empiler 1  (push)
pile.append(2)         # empiler 2
pile.append(3)         # empiler 3 : la pile vaut [1, 2, 3], sommet 3

sommet = pile[-1]      # lire le sommet SANS depiler : 3

x = pile.pop()         # depiler (pop) : x vaut 3, la pile devient [1, 2]

vide = (len(pile) == 0)   # tester si la pile est vide : ici False

🔍 Décryptage ligne par ligne

pile = []La pile de départ est une liste vide. On n'a besoin d'aucune classe : une liste Python suffit. Le sommet sera toujours le dernier élément.

pile.append(3)Empiler = ajouter à la fin. append pose l'élément au sommet (la fin de la liste). Après trois append, la pile vaut [1, 2, 3] et le sommet est 3. Coût

O (1)

sommet = pile[-1]Regarder sans toucher. L'indice -1 désigne le dernier élément : on lit le sommet sans le retirer. La pile est inchangée.

x = pile.pop()Dépiler = retirer le dernier. pop() sans argument enlève l'élément de la fin et le renvoie. Ici x reçoit 3 et la pile redevient [1, 2]. Coût

O (1)

len(pile) == 0Tester la pile vide. Une pile est vide quand sa longueur est nulle. On teste toujours ça avant de dépiler, sinon on risque une erreur (voir §7).

Exécution pas à pas — les opérations ci-dessus
Opération	Effet	Pile après	Valeur renvoyée
append(1)	empile 1	[1]	—
append(2)	empile 2	[1, 2]	—
append(3)	empile 3	[1, 2, 3]	—
pile[-1]	lit le sommet	[1, 2, 3]	3
pop()	dépile le sommet	[1, 2]	3

3. La file — FIFO

Définition 3.1 — File

Une file (en anglais queue) est une structure dans laquelle le premier élément entré est le premier sorti : on dit qu'elle est FIFO (First In, First Out). On ajoute d'un côté (la queue) et on retire de l'autre (la tête). Les opérations de base sont :

enfiler : ajouter un élément en queue ;
défiler : retirer et renvoyer l'élément de tête (le plus ancien) ;
file vide ? : tester si la file ne contient aucun élément.

💡 L'analogie de la file d'attente. À la boulangerie, tu te places derrière les autres, et c'est la personne arrivée en premier qui est servie en premier. Pas de resquilleur : premier arrivé, premier servi. C'est le comportement FIFO.

4. Implémenter une file avec une liste

On peut aussi utiliser une liste : on enfile en queue avec append et on défile en tête avec pop(0). Ça marche… mais attention au coût (voir plus bas).

file = []              # une file vide

file.append("a")       # enfiler "a"
file.append("b")       # enfiler "b"
file.append("c")       # enfiler "c" : la file vaut ["a", "b", "c"], tete "a"

premier = file.pop(0)  # defiler : premier vaut "a", la file devient ["b", "c"]

🔍 Décryptage ligne par ligne

file.append("a")Enfiler = ajouter en queue. Comme pour la pile, append ajoute à la fin. La tête de la file (le plus ancien) est donc le premier élément de la liste, file[0].

premier = file.pop(0)Défiler = retirer la tête. pop(0) retire l'élément d'indice 0 (le plus ancien) et le renvoie. Ici "a" sort en premier : c'est bien du FIFO. Mais pop(0) est coûteux — c'est le piège de la section suivante.

⚠ pop(0) coûte $O (n)$ , pas $O (1)$ . Retirer l'élément d'indice 0 oblige Python à décaler d'un cran vers la gauche tous les autres éléments pour boucher le trou. Sur une file de n éléments, un seul pop(0) coûte donc

O (n)

. Vider une file de n éléments à coups de pop(0) revient à

O (n^{2})

au total : catastrophique quand n est grand.

📝 La bonne solution : collections.deque (hors cœur du programme). Pour une file efficace, la bibliothèque standard fournit deque (« double-ended queue ») : append enfile et popleft défile, les deux en $O (1)$ . C'est ce qu'on utilise en pratique dès que la performance compte ; ça reste hors du cœur du programme, mais bon à connaître.

from collections import deque

file = deque()         # une file efficace, vide
file.append("a")       # enfiler   (a droite)
file.append("b")
file.append("c")

premier = file.popleft()   # defiler (a gauche) en O(1) : "a"

🔍 Décryptage ligne par ligne

from collections import dequeOn importe la structure. deque est optimisée pour ajouter/retirer aux deux bouts.

file.append("a")Enfiler en queue. Exactement comme une liste, en

O (1)

premier = file.popleft()Défiler la tête en $O (1)$ . popleft() retire et renvoie l'élément de gauche (le plus ancien) sans décaler quoi que ce soit. C'est le remplaçant direct et efficace de pop(0).

5. Le coût des opérations

Proposition 5.1 — Coûts à retenir

Avec une liste Python, empiler et dépiler une pile coûtent $O (1)$ . Enfiler dans une file coûte $O (1)$ , mais défiler avec pop(0) coûte $O (n)$ . Avec un deque, défiler (popleft) redevient $O (1)$ .

Coût de chaque opération selon l'implémentation
Opération	Pile — liste	File — liste	File — deque
empiler / enfiler	`append` : $O (1)$	`append` : $O (1)$	`append` : $O (1)$
dépiler / défiler	`pop()` : $O (1)$	`pop(0)` : $O (n)$ ⚠	`popleft()` : $O (1)$
lire le sommet / la tête	`pile[-1]` : $O (1)$	`file[0]` : $O (1)$	`file[0]` : $O (1)$
vide ?	`len == 0` : $O (1)$	`len == 0` : $O (1)$	`len == 0` : $O (1)$

📝 À retenir en une phrase. La pile avec une liste est parfaite (tout en

O (1)

). La file avec une liste a un défaut : pop(0) en

O (n)

; on le tolère si la file reste petite, sinon on passe à deque.

6. Application — vérifier un bon parenthésage

Voici l'application phare de la pile. On veut vérifier qu'une expression est bien parenthésée : chaque parenthèse (ou crochet, ou accolade) fermante correspond à la dernière ouvrante restée ouverte. « Dernière ouverte, première fermée » : c'est du LIFO, donc une pile est l'outil naturel.

📐 Méthode — vérifier le parenthésage avec une pile.

Parcourir les caractères un par un.
À chaque ouvrante, l'empiler.
À chaque fermante, vérifier que le sommet est l'ouvrante correspondante et la dépiler ; si la pile est vide ou ne correspond pas, c'est mal parenthésé.
À la fin, l'expression est bien parenthésée si et seulement si la pile est vide (aucune ouvrante n'est restée sans fermante).

def bien_parenthesee(s):
    pile = []
    fermantes = {")": "(", "]": "[", "}": "{"}   # a chaque fermante, l'ouvrante attendue
    for c in s:
        if c in "([{":                 # une ouvrante : on l'empile
            pile.append(c)
        elif c in ")]}":               # une fermante : on doit depiler la bonne ouvrante
            if len(pile) == 0 or pile.pop() != fermantes[c]:
                return False
    return len(pile) == 0              # bien parenthesee si et seulement si la pile est vide

🔍 Décryptage ligne par ligne

fermantes = {")": "(", ...}La table des correspondances. À chaque symbole fermant, on associe l'ouvrant qui doit se trouver au sommet. Ça évite trois if séparés.

if c in "([{":
    pile.append(c)

Ouvrante → on empile. On mémorise qu'une parenthèse (ou crochet, accolade) est ouverte, en la posant au sommet de la pile.

if len(pile) == 0 or
   pile.pop() != fermantes[c]

Fermante → on contrôle le sommet. Deux cas d'échec : (1) la pile est vide — une fermante sans rien à fermer ; (2) le sommet dépilé n'est pas l'ouvrante attendue — mauvais appariement, comme [). Grâce au « ou » paresseux, si la pile est vide on n'appelle même pas pop.

return len(pile) == 0Bilan final. Si tout s'est bien apparié, la pile est vide. S'il reste des ouvrantes (comme dans (()), la pile n'est pas vide : mal parenthésé.

Exécution pas à pas — bien_parenthesee("(a+[b])")
Caractère	Nature	Action	Pile après
(	ouvrante	empile '('	['(']
a	autre	ignore	['(']
+	autre	ignore	['(']
[	ouvrante	empile '['	['(', '[']
b	autre	ignore	['(', '[']
]	fermante	dépile '[' — correspond	['(']
)	fermante	dépile '(' — correspond	[]
fin	—	pile vide	renvoie True ✓

💡 Deux contre-exemples. Sur "([)]", à la fermante ) le sommet est [ (et non () : mauvais appariement, on renvoie False. Sur "(()", la boucle finit avec ['('] dans la pile : elle n'est pas vide, on renvoie False. Bien vu : la pile détecte les deux fautes.

7. Pièges classiques en copie

⚠ Dépiler (ou défiler) une structure vide. Sur une liste vide, [].pop() lève IndexError: pop from empty list et arrête le programme. Toujours tester len(pile) == 0 (ou if pile:) avant de dépiler.

⚠ Confondre LIFO et FIFO. Pile = dernier entré premier sorti ; file = premier entré premier sorti. Le réflexe : une pile s'empile et se dépile du même côté (la fin, avec pop()) ; une file entre par un bout et sort par l'autre (append puis pop(0)).

⚠ Écrire pile.pop(0) pour une pile. Un pop(0) retire le premier élément : ce n'est plus une pile mais une file, et le comportement (comme le coût

O (n)

) change du tout au tout. Pour une pile, c'est pop() tout court.

⚠ Oublier le test de correspondance dans le parenthésage. Se contenter de compter « autant d'ouvrantes que de fermantes » accepte à tort "[(])". Il faut vérifier quelle ouvrante on dépile, pas seulement leur nombre.

8. Exercices d'application

Fais-les sur papier avant d'ouvrir le corrigé, puis passe au quiz en bas de fiche.

Exo 1Prévoir la sortie d'une pileFacile

p = []
p.append("X")
p.append("Y")
print(p.pop())
p.append("Z")
print(p)

Voir la correction détaillée

Après les deux append, la pile vaut ["X", "Y"], sommet "Y".

p.pop() retire et renvoie le sommet : affiche Y, et la pile redevient ["X"].

On empile "Z" : la pile vaut ["X", "Z"]. Second affichage : ['X', 'Z'].

Exo 2Un sommet sûrIntermédiaire

Écris une fonction sommet(p) qui renvoie le sommet de la pile p sans la modifier, et renvoie None si la pile est vide (au lieu de planter).

Voir la correction détaillée

On teste d'abord le cas vide pour éviter l'IndexError :

def sommet(p):
    if len(p) == 0:
        return None
    return p[-1]

On utilise p[-1] (lecture) et non p.pop() : la pile reste intacte. Ainsi sommet([]) renvoie None et sommet([7, 8, 9]) renvoie 9.

Exo 3Le coût de vider une fileDifficile

Une file reçoit n enfilements puis n défilements. Quel est le coût total si on l'implémente avec une liste et pop(0) ? Et avec un deque et popleft ? Justifie.

Voir la correction détaillée

Les n enfilements coûtent

O (1)

chacun, soit

O (n)

dans les deux cas.

Liste : chaque pop(0) décale les éléments restants. Quand il en reste

k

, le coût est

O (k)

. Le total est

O (n + (n - 1) + \dots + 1) = O (n^{2})

deque : chaque popleft coûte

O (1)

, donc

O (n)

au total. Bilan :

O (n)

contre

O (n^{2})

— pour n grand, l'écart est énorme. C'est pour ça qu'une vraie file utilise deque.

Récap final — Ce qu'il faut absolument retenir

À la veille d'une khôlle ou d'un DS, parcours cette checklist : tu dois pouvoir répondre « oui, sans hésiter » à chaque question.

Sais-tu ce que veut dire LIFO (pile) et FIFO (file), avec l'analogie assiettes / file d'attente ?
Sais-tu qu'une pile s'implémente avec une liste : append pour empiler, pop() pour dépiler, tous deux en $O (1)$ ?
Sais-tu lire le sommet sans dépiler (pile[-1]) ?
Sais-tu qu'une file avec une liste utilise append et pop(0), mais que pop(0) coûte $O (n)$ ?
Sais-tu qu'un deque (popleft) rend le défilement $O (1)$ ?
Sais-tu redonner le tableau des coûts de chaque opération ?
Sais-tu écrire bien_parenthesee(s) avec une pile et la dérouler sur un exemple ?
Sais-tu qu'il faut tester la structure vide avant de dépiler pour éviter l'IndexError ?

Vue d'ensemble

Prérequis

1. La pile — LIFO

2. Implémenter une pile avec une liste

3. La file — FIFO

4. Implémenter une file avec une liste

5. Le coût des opérations

6. Application — vérifier un bon parenthésage

7. Pièges classiques en copie

8. Exercices d'application

Récap final — Ce qu'il faut absolument retenir

Débloque la fiche complète

Quiz — Piles et files

Fiches associées

Recherche par dichotomie

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Tu veux aller plus loin sur ce chapitre ?