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

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

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

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

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)\) amorti, pop() en \(O(1)\)
• C. append en \(O(1)\), pop() en \(O(n)\)
• D. append en \(O(n)\), pop() en \(O(1)\)

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 :

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

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

class Pile:
    def __init__(self):
        self.contenu = []

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

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

    def depiler(self):
        if self.est_vide():
            raise ValueError("pile vide")
        return self.contenu.pop()

    def sommet(self):
        if self.est_vide():
            raise ValueError("pile vide")
        return self.contenu[-1]

    def __len__(self):
        return len(self.contenu)

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

class File:
    def __init__(self):
        self.contenu = []

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

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

    def defiler(self):
        if self.est_vide():
            raise ValueError("file vide")
        return self.contenu.pop(0)

    def __len__(self):
        return len(self.contenu)

Alice
Bob

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 :

2. É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.

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

def evaluer_npi(expression):
    p = Pile()
    for jeton in expression.split():
        if jeton in "+-*/":
            b = p.depiler()   # opérande droit (dépilé en premier)
            a = p.depiler()   # opérande gauche
            if jeton == "+":
                p.empiler(a + b)
            elif jeton == "-":
                p.empiler(a - b)
            elif jeton == "*":
                p.empiler(a * b)
            elif jeton == "/":
                p.empiler(a / b)
        else:
            p.empiler(float(jeton))
    return p.depiler()

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.

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

3. Tester sur les exemples suivants :

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

def parenthesage_valide(expression):
    p = Pile()
    correspondance = {")": "(", "]": "["}
    for c in expression:
        if c in "([":
            p.empiler(c)
        elif c in ")]":
            if p.est_vide():
                return False
            if p.depiler() != correspondance[c]:
                return False
    return p.est_vide()

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.

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

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).

def inverser_file(f):
    p = Pile()
    # Phase 1 : vider la file dans la pile
    while not f.est_vide():
        p.empiler(f.defiler())
    # Phase 2 : vider la pile dans la file
    while not p.est_vide():
        f.enfiler(p.depiler())

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.

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.

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

class FileImpression:
    def __init__(self):
        self.file = File()

    def soumettre(self, nom, pages):
        self.file.enfiler({"nom": nom, "pages": pages})

    def imprimer_suivant(self):
        if self.file.est_vide():
            print("Aucun document en attente.")
            return 0
        doc = self.file.defiler()
        print(f"Impression de {doc['nom']} ({doc['pages']} pages)")
        return doc["pages"]

    def documents_en_attente(self):
        return len(self.file)

    def pages_restantes(self):
        total = 0
        # Parcours non destructif : on défile et ré-enfile
        n = len(self.file)
        for _ in range(n):
            doc = self.file.defiler()
            total += doc["pages"]
            self.file.enfiler(doc)
        return total

imprimante = FileImpression()
total = 0

imprimante.soumettre("Rapport", 12)
imprimante.soumettre("CV", 2)
# File : Rapport (12p) ← CV (2p)

total += imprimante.imprimer_suivant()
# Impression de Rapport (12 pages)
# File : CV (2p)

imprimante.soumettre("Thèse", 150)
# File : CV (2p) ← Thèse (150p)

total += imprimante.imprimer_suivant()
# Impression de CV (2 pages)

total += imprimante.imprimer_suivant()
# Impression de Thèse (150 pages)

print(f"Total : {total} pages imprimées")
# Total : 164 pages imprimées