Piles, files et deques en Python : cours et exercices corrigés

Q: Comment implémenter une pile en Python ?

Par une liste dont le sommet est le dernier élément : `creer_pile()` renvoie `[]`, `est_vide(P)` teste `len(P) == 0`, `empiler(P, x)` fait `P.append(x)`, `depiler(P)` renvoie `P.pop()` et `sommet(P)` renvoie `P[len(P) - 1]`. Dépiler une pile vide ou lire son sommet n'a pas de sens : `depiler` et `sommet` vérifient la précondition par `assert not est_vide(P)`. Chaque opération se fait en temps constant, quelle que soit la hauteur de la pile. Mettre le sommet en tête, avec `insert(0, x)` et `pop(0)`, donnerait des résultats justes, mais chaque opération déplacerait tous les autres éléments. Au programme marocain, le sommet s'écrit aussi `P[-1]`.

Q: Pourquoi utiliser deque au lieu d'une liste pour une file en Python ?

Parce que `pop(0)` n'est pas en temps constant : pour retirer le premier élément d'une liste de k éléments, il fait glisser les k - 1 autres d'une case. Vider ainsi une file de n éléments coûte (n(n-1))/(2) décalages, 499 500 pour mille camions : un coût quadratique. Une deque, créée par `deque()` après `from collections import deque`, ajoute par `append` et retire par `popleft` en temps constant, et la file se vide en O(n). Défiler s'écrit `popleft()` : avec `pop()`, la deque se comporte en pile, sans erreur. En France, `deque` n'est pas exigible et le sujet le documente ; au programme marocain, elle est nommée en deuxième année, au parcours des graphes.

Structures de données abstraites pile et file, implémentation par une liste Python (append, pop) et par deque, opérations et coûts, applications classiques : parenthèses bien formées, évaluation d'une expression postfixée, file d'attente, parcours.

14méthodes
30exercices corrigés
4problèmes
15pièges
42figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Une pile fait sortir le dernier élément entré (LIFO) : en Python, c'est une liste dont le sommet est en fin, avec append pour empiler et pop() pour dépiler, chacun en temps constant. Une file fait sortir le premier entré (FIFO) : par une liste, défiler par pop(0) fait glisser tous les autres éléments, et vider une file de $n$ éléments coûte $\frac{n(n-1)}{2}$ décalages, soit 499 500 pour mille éléments ; une deque du module collections, avec append et popleft, défile en temps constant. Ce chapitre d'informatique commune de première année, au programme de MPSI, PCSI, PTSI, TSI et TPC, au Maroc et en France, définit ces structures par leur interface, puis traite les applications classiques : vérification des parenthèses, évaluation d'une expression postfixée, simulation d'une file d'attente, file avec deux piles, pile à la place de la récursion. Les exercices et problèmes reprennent des questions des sujets du CNC, de CCINP, de Mines-Ponts, de Centrale-Supélec et de X-ENS. En France, pop(0) et deque sont hors de l'annexe du programme : un sujet qui s'en sert les documente.

Ce que tu sauras faire

À la saison des dattes, les camions attendent le pont-bascule dans l'ordre de leur arrivée, et les caisses pesées s'empilent dans la salle de stockage. Deux règles de sortie différentes, deux structures de données : la file et la pile. Elles servent partout, des calculs d'une calculatrice à la pile d'appels de Python, et les sujets les demandent souvent. À la fin de ce chapitre, tu dois savoir :

définir une pile et une file de façon abstraite, par les opérations qu'on peut faire, et dessiner leur état après une suite d'opérations ;
écrire leurs opérations en Python avec une liste, et dire ce que coûte chacune ;
expliquer pourquoi une file par liste devient lente, et la remplacer par une deque, documentée comme dans un sujet ;
vérifier un parenthésage et évaluer une expression postfixée avec une pile, prouver ces algorithmes et donner leur coût ;
simuler une file d'attente ;
écrire une file de capacité fixe, une file avec deux piles, et remplacer une récursion par une pile.

L'essentiel : Implémentations et coûts Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

implémentation	ajouter	retirer	vider $n$ éléments
pile par liste, sommet en fin (`append`, `pop()`)	$O(1)$	$O(1)$	$O(n)$
file par liste (`append`, `pop(0)`)	$O(1)$	$O(k)$ pour $k$ éléments	$O(n^2)$
file par deque (`append`, `popleft`)	$O(1)$	$O(1)$	$O(n)$
file circulaire de capacité fixe	$O(1)$	$O(1)$	$O(n)$
file par deux piles	$O(1)$	$O(1)$ en moyenne sur une suite d'opérations	$O(n)$

pop(0) fait glisser tous les autres éléments : $k - 1$ décalages pour une file de $k$ éléments, $\frac{n(n-1)}{2}$ pour vider une file de $n$ éléments.
Une deque (from collections import deque) ajoute et retire aux deux bouts en temps constant : append, appendleft, pop, popleft, len. En file : append et popleft. En pile : append et pop.

def creer_pile():
    # pile vide
    return []

def est_vide(P):
    # True si P est vide
    return len(P) == 0

def empiler(P, x):
    # x au sommet de P
    P.append(x)

def depiler(P):
    # P non vide ; retire et renvoie le sommet
    assert not est_vide(P)
    return P.pop()

def sommet(P):
    # P non vide ; renvoie le sommet sans le retirer
    assert not est_vide(P)
    return P[len(P) - 1]

Une méthode du chapitre Extrait gratuit

Méthode Vérifier un parenthésage et retrouver les couples

Quand l’utiliser

L'énoncé demande si une expression, une formule ou un texte est bien parenthésé, ou quelle parenthèse ferme quelle autre.

Rappel de cours

Avec une seule sorte, un compteur qui ne devient jamais négatif et finit à 0 suffit. Avec plusieurs sortes, il faut une pile : la dernière ouverte est la première fermée. En empilant les indices, on retrouve les couples.

Démarche

Parcourir les caractères de gauche à droite.
Ouvrante : l'empiler (ou empiler son indice).
Fermante : si la pile est vide, réponse fausse ; sinon dépiler et comparer à l'ouvrante attendue (ou noter le couple).
À la fin, la réponse est vraie si et seulement si la pile est vide.

Rédaction type

if c == "(" or c == "[" or c == "{":
    empiler(P, c)
elif c == ")" or c == "]" or c == "}":
    if est_vide(P):
        return False
    if associee(depiler(P)) != c:
        return False

« La pile contient les ouvrantes lues et pas encore fermées ; une fermante doit correspondre au sommet ; la chaîne est bien parenthésée si la pile est vide à la fin. »

Exemple traité

print(bien_parenthesee("{(x+1)*[y-2]}"))
print(couples_parentheses("(x+1)*(y-2)"))

Le programme affiche :

True
[(0, 4), (6, 10)]

Les deux parenthèses de (x+1)*(y-2) se suivent sans s'emboîter : chacune est fermée avant l'ouverture de la suivante.

Erreurs fréquentes

Compter seulement : ")(" et "([)]" passeraient.
Oublier le test de la pile vide avant de dépiler : une fermante en premier arrête le programme au lieu de renvoyer False.
Oublier le test final : "((" serait acceptée.

Pour s’entraîner

Exercices 6, 14, 15, 17 et 29, problème 1.

Un exercice corrigé Extrait gratuit

Exercice Évaluer à la main des expressions postfixées ★☆☆

Une expression postfixée est donnée par la liste de ses jetons : des nombres et les chaînes '+', '-', '*', '/'. Quand on lit un opérateur, on dépile d'abord l'opérande de droite, puis celui de gauche.

Dresser le tableau des étapes (jeton lu, opération faite, contenu de la pile après) pour [9, 3, '+', 2, '*', 4, -2, '-', '/']. Le jeton -2 est le nombre $-2$ , pas un opérateur.
Même question pour 3 10 5 + * 1 - et pour 32 2 12 3 7 2 - * - * -.
Écrire en notation postfixée l'expression $(6 - 2) \times (3 + 1)$ , puis vérifier les quatre valeurs avec evalue_postfixe.

Indications

Méthode 8 : un nombre s'empile ; un opérateur dépile $b$ puis $a$ et empile $a \text{ op } b$ ; à la fin, une seule valeur.
Question 3 : écrire chaque sous-expression en postfixe, puis l'opérateur qui les relie, à la fin.

Analyse : comment trouver l’idée

L'ordre des opérandes ne compte que pour - et /. Dans la première expression, la soustraction lit $4$ puis $-2$ : elle calcule $4 - (-2) = 6$ , et la division finale $24 / 6$ . Dans la troisième, quatre nombres attendent dans la pile avant le premier opérateur.

Correction détaillée

[9, 3, '+', 2, '*', 4, -2, '-', '/'] (tableau vérifié par programme) :

jeton	opération	pile après
`9`	empiler	`[9]`
`3`	empiler	`[9, 3]`
`'+'`	$9 + 3 = 12$	`[12]`
`2`	empiler	`[12, 2]`
`'*'`	$12 \times 2 = 24$	`[24]`
`4`	empiler	`[24, 4]`
`-2`	empiler	`[24, 4, -2]`
`'-'`	$4 - (-2) = 6$	`[24, 6]`
`'/'`	$24 / 6 = 4$	`[4.0]`

3 10 5 + * 1 - :

jeton	opération	pile après
`3`	empiler	`[3]`
`10`	empiler	`[3, 10]`
`5`	empiler	`[3, 10, 5]`
`'+'`	$10 + 5 = 15$	`[3, 15]`
`'*'`	$3 \times 15 = 45$	`[45]`
`1`	empiler	`[45, 1]`
`'-'`	$45 - 1 = 44$	`[44]`

32 2 12 3 7 2 - * - * - :

jeton	opération	pile après
`32`, `2`, `12`, `3`, `7`, `2`	six empilements	`[32, 2, 12, 3, 7, 2]`
`'-'`	$7 - 2 = 5$	`[32, 2, 12, 3, 5]`
`'*'`	$3 \times 5 = 15$	`[32, 2, 12, 15]`
`'-'`	$12 - 15 = -3$	`[32, 2, -3]`
`'*'`	$2 \times (-3) = -6$	`[32, -6]`
`'-'`	$32 - (-6) = 38$	`[38]`

$(6 - 2) \times (3 + 1)$ s'écrit 6 2 - 3 1 + * : on écrit $6 - 2$ (6 2 -), puis $3 + 1$ (3 1 +), puis l'opérateur * qui les relie.

print(evalue_postfixe([9, 3, '+', 2, '*', 4, -2, '-', '/']))
print(evalue_postfixe([3, 10, 5, '+', '*', 1, '-']))
print(evalue_postfixe([32, 2, 12, 3, 7, 2, '-', '*',
                       '-', '*', '-']))
print(evalue_postfixe([6, 2, '-', 3, 1, '+', '*']))

Le programme affiche :

Interprétation : la division donne toujours un flottant (4.0), même quand le quotient est entier ; les trois autres expressions n'ont que des opérations entières et donnent des entiers.

Méthodes à retenir

Le tableau « jeton, opération, pile » se remplit sans hésiter si l'on écrit toujours l'opération sous la forme $a \text{ op } b$ , avec $b$ le premier dépilé. Voir la méthode 8.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 14 méthodes, 15 pièges corrigés, la carte mentale, 30 exercices corrigés, 4 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Les trois premiers chapitres de chaque matière sont offerts avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Voir les offres

Plan du cours

1. Attendre son tour : deux façons
- 1.1 Le problème
- 1.2 Interface et implémentation
2. La pile
- 2.1 Définition
- 2.2 Les opérations
- 2.3 Simuler à la main
3. Une pile en Python
- 3.1 Le code
- 3.2 Coût
- 3.3 Pourquoi le sommet n'est pas en tête
- 3.4 Une pile passée à une fonction
4. À quoi servent les piles
- 4.1 Revenir en arrière
- 4.2 La pile d'appels
5. Vérifier des parenthèses
- 5.1 Une seule sorte : un compteur suffit
- 5.2 Plusieurs sortes : la pile
- 5.3 Retrouver les couples
- 5.4 Preuve et coût
6. Évaluer une expression postfixée
- 6.1 Trois écritures d'une expression
- 6.2 L'algorithme
- 6.3 Ordre des opérandes et expressions mal formées
- 6.4 Histoire de la notion
7. La file
- 7.1 Définition
- 7.2 Les opérations
- 7.3 Une file par une liste
8. Ce que coûte pop(0)
- 8.1 Ce que fait pop(0)
- 8.2 Vider une file
9. La deque
- 9.1 Ce que le sujet fournit
- 9.2 Une file par une deque
- 9.3 Une deque sert de file ou de pile
10. Simuler une file d'attente
- 10.1 Le problème
- 10.2 La boucle sur le temps
- 10.3 Ce que dit la simulation
11. Piles et files de capacité fixe
- 11.1 Pile bornée
- 11.2 La file circulaire
12. Une file avec deux piles
13. Une pile à la place de la récursion, et ce qui vient ensuite
- 13.1 La palmeraie, sans récursion
- 13.2 La règle
- 13.3 Ce qui vient ensuite

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Choisir entre pile, file et deque
Écrire les primitives d'une pile par une liste
Écrire les primitives d'une file par une liste, puis par une deque
Simuler à la main une suite d'opérations
Respecter l'interface imposée par un sujet
Parcourir une pile sans la détruire
Vérifier un parenthésage et retrouver les couples
Évaluer une expression postfixée
Prouver un algorithme à pile
Justifier le coût des opérations et d'une boucle
Simuler une file d'attente
Remplacer une récursion par une pile explicite
Implémenter une pile bornée et une file circulaire
Implémenter une file avec deux piles

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (12)

États successifs d'une pile
Programmes à simuler sur une file et une deque
Pile, file ou deque ?
Compléter l'interface d'une pile
Ce que coûtent pop() et pop(0)
Parenthèses d'une seule sorte
Évaluer à la main des expressions postfixées
Une pile de capacité limitée
Place prise dans la pile d'appels
Copier une pile sans la détruire
Une file par une liste, puis par une deque
Page précédente et page suivante

Entraînement (14)

Inverser, faire tourner, échanger
Parenthèses de trois sortes
Retrouver la parenthèse associée
Une calculatrice postfixée qui lit une ligne
Prouver la vérification des parenthèses
La file du pont-bascule
Une file circulaire à deux indices
Lire un mot par les deux bouts
Annuler une modification
De la récursion à une pile
Moyenne des 500 dernières valeurs
Remplir une zone avec une pile
Deux files par priorité
Quelles sorties une pile peut-elle produire ?

Approfondissement (4)

Une file avec deux piles : combien d'opérations ?
De l'écriture usuelle à l'écriture postfixée
Les grottes à ciel ouvert
Sortir d'un labyrinthe avec une pile

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Pile, expressions postfixées et parenthèses
CNC 2015, filières MP, PSI et TSI, épreuve d'informatique, problème « Gestion des expressions postfixées », questions 10 à 15, 17 à 19 et 21, complétées
File bornée et file d'attente d'impression
CNC 2014, filières MP, PSI et TSI, épreuve d'informatique, problème II, questions 5 à 8, complétées
Le tri α par une pile de segments
X-ENS 2016, filières PSI et PT, composition d'informatique, partie IV, questions 12 à 15
Enveloppe convexe et piles abstraites
X-ENS 2015, filières MP et PC, composition d'informatique B, parties I et III, questions 1, 3 et 10 à 13

Questions fréquentes

Comment implémenter une pile en Python ?

Par une liste dont le sommet est le dernier élément : creer_pile() renvoie [], est_vide(P) teste len(P) == 0, empiler(P, x) fait P.append(x), depiler(P) renvoie P.pop() et sommet(P) renvoie P[len(P) - 1]. Dépiler une pile vide ou lire son sommet n'a pas de sens : depiler et sommet vérifient la précondition par assert not est_vide(P). Chaque opération se fait en temps constant, quelle que soit la hauteur de la pile. Mettre le sommet en tête, avec insert(0, x) et pop(0), donnerait des résultats justes, mais chaque opération déplacerait tous les autres éléments. Au programme marocain, le sommet s'écrit aussi P[-1].

Quelle différence entre une pile et une file ?

Une pile fait sortir le dernier entré, comme des caisses posées les unes sur les autres : on ajoute et l'on retire au sommet, en anglais LIFO (last in, first out). Une file fait sortir le premier entré, comme des camions qui attendent leur pesée : on ajoute en queue et l'on retire en tête, en anglais FIFO (first in, first out). Les opérations se correspondent : empiler et enfiler, depiler et defiler, sommet et tete. Ces structures se définissent par leur interface, le nom, les paramètres, la précondition et la valeur renvoyée de chaque opération ; un programme qui n'utilise que l'interface reste juste quand on change d'implémentation.

Pourquoi utiliser deque au lieu d'une liste pour une file en Python ?

Parce que pop(0) n'est pas en temps constant : pour retirer le premier élément d'une liste de $k$ éléments, il fait glisser les $k - 1$ autres d'une case. Vider ainsi une file de $n$ éléments coûte $\frac{n(n-1)}{2}$ décalages, 499 500 pour mille camions : un coût quadratique. Une deque, créée par deque() après from collections import deque, ajoute par append et retire par popleft en temps constant, et la file se vide en $O(n)$ . Défiler s'écrit popleft() : avec pop(), la deque se comporte en pile, sans erreur. En France, deque n'est pas exigible et le sujet le documente ; au programme marocain, elle est nommée en deuxième année, au parcours des graphes.

Comment vérifier qu'une expression est bien parenthésée avec une pile ?

Avec une seule sorte de parenthèses, un compteur suffit : il augmente sur (, diminue sur ), ne doit jamais devenir négatif et doit finir à 0. Avec (), [] et {}, il faut une pile, car la dernière ouverte est la première fermée : "([)]" a des comptes justes et reste mal parenthésée. On empile chaque ouvrante ; sur une fermante, si la pile est vide, on renvoie False, sinon on dépile et l'on vérifie que l'ouvrante correspond. À la fin, la chaîne est bien parenthésée si et seulement si la pile est vide. Le coût est en $O(n)$ pour $n$ caractères. En empilant les indices des ouvrantes, on retrouve les couples de parenthèses associées.

Comment évaluer une expression postfixée avec une pile ?

En notation postfixée, ou polonaise inverse, l'opérateur suit ses deux opérandes : $(250 - 10) \times 3$ s'écrit 250 10 - 3 *. On lit les jetons de gauche à droite ; un nombre est empilé ; un opérateur dépile d'abord l'opérande de droite, puis celui de gauche, calcule et empile le résultat. À la fin, la pile contient une seule valeur, ici 720. L'ordre des opérandes compte pour - et / : 7 2 - vaut 5, et les prendre dans l'ordre où on les dépile donnerait $-5$ . Une expression mal formée est arrêtée par une précondition, pile vide sous un opérateur ou plus d'une valeur à la fin. Le coût est en $O(n)$ pour $n$ jetons.

Comment faire une file avec deux piles ?

On enfile en empilant sur une pile d'entrée. Pour défiler, on dépile une pile de sortie ; si elle est vide, on y verse d'abord toute la pile d'entrée, ce qui renverse l'ordre et place le plus ancien élément au sommet. Un défilement peut coûter cher, puisqu'il transfère toute la pile d'entrée, mais chaque élément n'est transféré qu'une fois. Sur une suite de $m$ opérations, il y a donc au plus $m$ transferts : le coût total est en $O(m)$ , et le coût moyen d'une opération est constant. Ce raisonnement sur toute la suite d'opérations s'appelle une analyse amortie ; le mot n'est pas au programme.

Comment y accéder

Ce chapitre fait partie de l'accès complet. Les trois premiers chapitres de chaque matière (deux par bloc en économie et droit, en management et gestion) sont offerts avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet et les tarifs, vois les offres.