Exercices : piles et files

Exercice 1 — QCM : piles et files

Pour chaque question, une seule réponse est correcte.

1. On empile successivement les lettres A, B, C, D dans une pile initialement vide. On dépile ensuite deux fois. Quelle est la lettre au sommet de la pile ?

  • A. A
  • B. B
  • C. C
  • D. D

Correction publiée après la séance.

2. On enfile les lettres A, B, C dans une file, puis on défile une fois. Quelle lettre est renvoyée ?

  • A. C (la dernière enfilée)
  • B. B (celle du milieu)
  • C. A (la première enfilée)
  • D. une erreur car la file est pleine

Correction publiée après la séance.

3. Parmi les situations suivantes, laquelle correspond à une pile ?

  • A. les clients qui font la queue à la boulangerie
  • B. la fonction « annuler » (Ctrl-Z) d’un éditeur de texte
  • C. les documents envoyés à une imprimante partagée
  • D. les voitures qui passent à un péage dans l’ordre d’arrivée

Correction publiée après la séance.

4. Quelle opération est interdite sur une pile ?

  • A. consulter l’élément au sommet sans le retirer
  • B. empiler un nouvel élément
  • C. accéder directement au troisième élément en partant du fond
  • D. dépiler l’élément au sommet

Correction publiée après la séance.

5. On implémente une pile à l’aide du type list de Python en utilisant append pour empiler et pop() pour dépiler. Quelle est la complexité de ces deux opérations ?

  • A. append en \(O(n)\), pop() en \(O(n)\)
  • B. append en \(O(1)\), pop() en \(O(1)\)
  • C. append en \(O(1)\), pop() en \(O(n)\)
  • D. append en \(O(n)\), pop() en \(O(1)\)

Correction publiée après la séance.

Exercice 2 — Exercice guidé : dérouler empiler/dépiler pas à pas

On considère une pile p initialement vide. On exécute les instructions suivantes :

p.empiler(4)
p.empiler(7)
p.empiler(2)
a = p.depiler()
p.empiler(9)
b = p.depiler()
p.empiler(1)
c = p.depiler()
  1. Recopier et compléter le tableau suivant en dessinant l’état de la pile après chaque instruction (le sommet est en haut) et en indiquant la valeur des variables a, b et c :
InstructionÉtat de la pile (bas → haut)Variable
empiler(4)
empiler(7)
empiler(2)
depiler()a =
empiler(9)
depiler()b =
empiler(1)
depiler()c =
Indice

empiler pose l’élément au sommet, c’est-à-dire à droite de l’état écrit du bas vers le haut. depiler retire l’élément du sommet et le renvoie : c’est lui qui va dans la variable.

  1. Après ces instructions, quels éléments restent dans la pile ? Dans quel ordre ?

    Indice

    Lire la dernière ligne du tableau : ce sont les éléments restants, du bas vers le sommet.

Correction publiée après la séance.

Exercice 3 — Exercice guidé : compléter une classe Pile à trous

Compléter les méthodes de la classe Pile implémentée avec le type list de Python.

class Pile:
    def __init__(self):
        self.contenu = ...        # créer une liste vide

    def est_vide(self):
        return ...                # vrai si la liste est vide

    def empiler(self, element):
        ...                       # ajouter en fin de liste

    def depiler(self):
        if self.est_vide():
            raise ValueError("pile vide")
        return ...                # retirer et renvoyer le dernier élément

    def sommet(self):
        """Renvoie l'élément au sommet sans le retirer."""
        if self.est_vide():
            raise ValueError("pile vide")
        return ...                # accéder au dernier élément

    def __len__(self):
        return ...                # nombre d'éléments
Indice

Toutes les opérations portent sur la liste self.contenu : append ajoute en fin, pop() retire et renvoie le dernier élément, self.contenu[-1] est le dernier élément et len(self.contenu) le nombre d’éléments. La pile est vide quand cette longueur vaut 0.

Correction publiée après la séance.

Exercice 4 — Implémenter une file

En s’inspirant de l’exercice précédent, écrire une classe File implémentée avec le type list de Python.

La classe doit comporter les méthodes suivantes :

  • est_vide(self) : renvoie True si la file est vide ;
  • enfiler(self, element) : ajoute un élément en fin de file ;
  • defiler(self) : retire et renvoie l’élément en début de file ;
  • __len__(self) : renvoie le nombre d’éléments.

Indication : pour retirer le premier élément d’une liste, on utilise pop(0).

Tester avec :

f = File()
f.enfiler("Alice")
f.enfiler("Bob")
f.enfiler("Charlie")
print(f.defiler())   # doit afficher Alice
print(f.defiler())   # doit afficher Bob
Indice

Même structure que la classe Pile : une liste self.contenu, dont les éléments s’ajoutent en fin avec append. Seule différence, defiler retire le premier élément, avec pop(0).

Code à copier puis compléter
class File:
    def __init__(self):
        self.contenu = []

    def est_vide(self):
        return len(self.contenu) == ...

    def enfiler(self, element):
        self.contenu.append(...)

    def defiler(self):
        return self.contenu.pop(...)

    def __len__(self):
        return ...

Correction publiée après la séance.

Exercice 5 — Notation polonaise inversée (NPI)

La notation polonaise inversée (NPI) est une façon d’écrire les calculs sans parenthèses. On écrit d’abord les opérandes, puis l’opérateur. Par exemple :

  • \((3 + 4)\) s’écrit 3 4 + ;
  • \((3 + 4) \times 2\) s’écrit 3 4 + 2 * ;
  • \(3 + 4 \times 2\) s’écrit 3 4 2 * +.

L’évaluation utilise une pile selon l’algorithme suivant :

  • si le jeton est un nombre, on l’empile ;
  • si le jeton est un opérateur, on dépile deux opérandes, on effectue le calcul, et on empile le résultat.
  1. Déroulé guidé. Évaluer pas à pas l’expression 5 3 + 8 2 - * en complétant le tableau :
Jeton luActionÉtat de la pile (bas → haut)
5empiler 55
3
+
8
2
-
*
Indice

Pour un opérateur, le premier nombre dépilé est l’opérande de droite et le second celui de gauche : pour 8 2 -, on calcule 8 − 2. Le résultat est empilé à la place des deux opérandes.

  1. Écrire une fonction evaluer_npi(expression) qui prend en paramètre une chaîne de caractères (jetons séparés par des espaces) et renvoie le résultat du calcul en utilisant la classe Pile.

    Indice

    expression.split() donne la liste des jetons. Pour chaque jeton : si c’est un opérateur, dépiler deux nombres, calculer, puis empiler le résultat ; sinon, empiler float(jeton). À la fin, le résultat est le seul élément de la pile.

    Code à copier puis compléter
    def evaluer_npi(expression):
    p = Pile()
    for jeton in expression.split():
        if jeton in "+-*/":
            droite = p.depiler()
            gauche = p.depiler()
            if jeton == "+":
                p.empiler(gauche + droite)
            elif jeton == "-":
                p.empiler(...)
            elif jeton == "*":
                p.empiler(...)
            else:
                p.empiler(...)
        else:
            p.empiler(float(jeton))
    return ...

  2. Tester avec evaluer_npi("5 3 + 8 2 - *") qui doit renvoyer 48.

Correction publiée après la séance.

Exercice 6 — Vérification du parenthésage

Un problème classique en compilation est de vérifier si les parenthèses et crochets d’une expression sont correctement appariés. Par exemple :

  • "(a + [b * c])" est valide ;
  • "(a + [b * c)]" est invalide (croisement des délimiteurs) ;
  • "(a + b" est invalide (parenthèse non fermée).

Algorithme : on parcourt les caractères un par un. Si on rencontre un ouvrant (( ou [), on l’empile. Si on rencontre un fermant () ou ]), on vérifie que le sommet de la pile correspond à l’ouvrant attendu. À la fin, la pile doit être vide.

  1. Dérouler l’algorithme sur "[a + (b * c)]" en montrant l’état de la pile après chaque ouvrant ou fermant.

    Indice

    Seuls les caractères [, (, ) et ] comptent : un ouvrant est empilé ; un fermant dépile le sommet, qui doit être l’ouvrant du même type.

  2. Écrire une fonction parenthesage_valide(expression) qui renvoie True si le parenthésage est correct, False sinon.

    Indice

    Parcourir les caractères. Un ouvrant est empilé. Pour un fermant, renvoyer False si la pile est vide ou si l’ouvrant dépilé ne lui correspond pas. Après la boucle, le parenthésage n’est correct que si la pile est vide.

    Code à copier puis compléter
    def parenthesage_valide(expression):
    p = Pile()
    for c in expression:
        if c in "([":
            p.empiler(c)
        elif c in ")]":
            if p.est_vide():
                return False
            ouvrant = p.depiler()
            if (c == ")" and ouvrant != "(") or (c == "]" and ouvrant != ...):
                return ...
    return p.est_vide()

  3. Tester sur les exemples suivants :

    • "()" → True
    • "([a + b] * (c - d))" → True
    • "(a + b]" → False
    • "((" → False

Correction publiée après la séance.

Exercice 7 — Inversion d’une file avec une pile

On souhaite inverser l’ordre des éléments d’une file sans utiliser de tableau ni de liste auxiliaire, mais uniquement une pile.

  1. Expliquer en quelques phrases le principe de la méthode.

    Indice

    Une pile rend les éléments dans l’ordre inverse de celui où ils ont été empilés : que se passe-t-il si l’on défile tous les éléments de la file pour les empiler, puis qu’on les dépile pour les enfiler de nouveau ?

  2. Écrire une fonction inverser_file(f) qui prend une file f en paramètre et inverse ses éléments sur place.

    Indice

    Deux boucles while se suivent : la première vide la file dans la pile, la seconde vide la pile dans la file.

    Code à copier puis compléter
    def inverser_file(f):
    p = Pile()
    while not f.est_vide():
        p.empiler(f.defiler())
    while not p.est_vide():
        f.enfiler(...)

  3. Tester : si la file contient initialement A ← B ← C (A en tête), après inversion elle doit contenir C ← B ← A (C en tête).

    Indice

    Enfiler A, B et C, appeler inverser_file, puis défiler les éléments un par un en les affichant.

Correction publiée après la séance.

Exercice 8 — Synthèse : simuler une file d’impression

On modélise une file d’attente d’imprimante. Chaque document est représenté par un dictionnaire {"nom": ..., "pages": ...}.

  1. Créer une classe FileImpression avec les méthodes :

    • soumettre(self, nom, pages) : ajoute un document à la file ;
    • imprimer_suivant(self) : retire le prochain document de la file, affiche "Impression de [nom] (X pages)" et renvoie le nombre de pages ;
    • documents_en_attente(self) : renvoie le nombre de documents restants ;
    • pages_restantes(self) : renvoie le nombre total de pages en attente.
    Indice

    Ranger les documents dans une liste de dictionnaires {"nom": ..., "pages": ...}. imprimer_suivant retire le premier avec pop(0), comme dans la classe File, et pages_restantes additionne les pages de tous les documents de la liste.

    Code à copier puis compléter
    class FileImpression:
    def __init__(self):
        self.documents = []

    def soumettre(self, nom, pages):
        self.documents.append({"nom": nom, "pages": pages})

    def imprimer_suivant(self):
        doc = self.documents.pop(...)
        print(f"Impression de {doc['nom']} ({doc['pages']} pages)")
        return ...

    def documents_en_attente(self):
        return ...

    def pages_restantes(self):
        total = 0
        for doc in self.documents:
            total = ...
        return total

  2. Simuler le scénario suivant :

    • Alice soumet « Rapport » (12 pages), puis Bob soumet « CV » (2 pages) ;
    • l’imprimante imprime un document ;
    • Charlie soumet « Thèse » (150 pages) ;
    • l’imprimante imprime les deux documents restants.
    Indice

    Traduire chaque ligne du scénario par un appel de méthode : soumettre pour un dépôt, imprimer_suivant pour une impression.

  3. Afficher le nombre total de pages imprimées.

    Indice

    Additionner les valeurs renvoyées par les appels à imprimer_suivant.

Correction publiée après la séance.

Chapitres liés