⌂  Menu général
Support des 4 séances du chapitre « Structures de données : piles et files ». Il sert à la fois de support de projection en classe et de support de révision à la maison : cliquez sur « Voir la réponse » sous chaque exercice pour afficher le corrigé.
Type abstrait de données (TAD) : on distingue toujours l'interface (les opérations disponibles) de l'implémentation (comment elles sont codées). Une pile est LIFO (Last In, First Out), une file est FIFO (First In, First Out) — même vocabulaire d'opérations, politique d'accès opposée.

Séance 1 — Découvrir les listes chaînées

TAD, deux implémentations, et un bug classique à débusquer

Durée : 2hcons/car/cdrMutabilité

1 Version fonctionnelle (tuples)

vide = None
def cons(v, reste): return (v, reste)
def car(liste): return liste[0]
def cdr(liste): return liste[1]

creer_liste_numerique(tableau), afficher(liste), nieme_element(liste, n) :

Voir la réponse 
def creer_liste_numerique(tableau):
    liste = vide
    for x in reversed(tableau):
        liste = cons(x, liste)
    return liste

def afficher(liste):
    s = "["
    while liste is not vide:
        s += str(car(liste))
        liste = cdr(liste)
        if liste is not vide: s += ", "
    print(s + "]")

def nieme_element(liste, n):
    for _ in range(n):
        liste = cdr(liste)
    return car(liste)
nieme_element est en O(n), contrairement à l'accès direct tab[n] d'un tableau (O(1)).

2 Version orientée objet (Cellule)

class Cellule:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

🐛 Le bug d'auto-référencement (Maillon mutable)

Version buguée :

def renverser_bug(tete):
    precedent = None
    actuel = tete
    while actuel is not None:
        actuel.suivant = precedent
        precedent = actuel
        actuel = actuel.suivant   # vient d'être écrasé !
    return precedent
Voir la réponse (version corrigée) 
def renverser(tete):
    precedent = None
    actuel = tete
    while actuel is not None:
        suivant_sauvegarde = actuel.suivant   # sauvegarde AVANT d'écraser
        actuel.suivant = precedent
        precedent = actuel
        actuel = suivant_sauvegarde
    return precedent
Toujours sauvegarder une référence dont on aura encore besoin AVANT de l'écraser sur un objet mutable.

Séance 2 — Manipuler des listes chaînées

Exercices progressifs : occurrences, rang, tri, conversion

Durée : 2h6 exercices

1-2 occurrences / trouver_rang

Voir la réponse 
def occurrences(liste, valeur):
    if liste is vide:
        return 0
    return (1 if car(liste) == valeur else 0) + occurrences(cdr(liste), valeur)

def trouver_rang(liste, valeur, rang=0):
    if liste is vide:
        return -1
    if car(liste) == valeur:
        return rang
    return trouver_rang(cdr(liste), valeur, rang + 1)

3 renverser_efficace — technique de l'accumulateur

Voir la réponse 
def renverser_efficace(liste):
    resultat = vide
    while liste is not vide:
        resultat = cons(car(liste), resultat)
        liste = cdr(liste)
    return resultat
En O(n), contrairement à une version par concaténations successives qui serait en O(n²).

4-5 inserer_triee / tri_par_insertion

Voir la réponse 
def inserer_triee(liste, valeur):
    if liste is vide or valeur <= car(liste):
        return cons(valeur, liste)
    return cons(car(liste), inserer_triee(cdr(liste), valeur))

def tri_par_insertion(liste):
    resultat = vide
    while liste is not vide:
        resultat = inserer_triee(resultat, car(liste))
        liste = cdr(liste)
    return resultat

6 liste_vers_tableau

Voir la réponse 
def liste_vers_tableau(liste):
    tableau = []
    while liste is not vide:
        tableau.append(car(liste))
        liste = cdr(liste)
    return tableau

🎯 Défi bonus — sont_identiques

Comparer deux listes chaînées, valeur par valeur.

Séance 3 — Les piles (LIFO)

Classe complète, historique de navigation, calculatrice RPN

Durée : 2hLIFOO(1)

1 Classe Pile (avec taille() optimisée)

Voir la réponse 
class Pile:
    def __init__(self):
        self.sommet = None
        self._taille = 0

    def est_vide(self):
        return self.sommet is None

    def empiler(self, valeur):
        self.sommet = Maillon(valeur, self.sommet)
        self._taille += 1

    def depiler(self):
        valeur = self.sommet.valeur
        self.sommet = self.sommet.suivant
        self._taille -= 1
        return valeur

    def consulter(self):
        return self.sommet.valeur

    def vider(self):
        self.sommet = None
        self._taille = 0

    def taille(self):
        return self._taille   # O(1) grâce au compteur maintenu à jour

2 Navigateur (historique retour / retour_avant)

Voir la réponse 
class Navigateur:
    def __init__(self, page_initiale):
        self.pile_precedent = Pile()
        self.pile_suivant = Pile()
        self.page_actuelle = page_initiale

    def visiter(self, page):
        self.pile_precedent.empiler(self.page_actuelle)
        self.page_actuelle = page
        self.pile_suivant.vider()

    def retour(self):
        if self.pile_precedent.est_vide(): return
        self.pile_suivant.empiler(self.page_actuelle)
        self.page_actuelle = self.pile_precedent.depiler()

    def retour_avant(self):
        if self.pile_suivant.est_vide(): return
        self.pile_precedent.empiler(self.page_actuelle)
        self.page_actuelle = self.pile_suivant.depiler()

3 Calculatrice en notation polonaise inversée (RPN)

"3 4 +" = 7, "5 1 2 + 4 * + 3 -" = 14

Voir la réponse 
def calculer_rpn(expression):
    pile = Pile()
    for jeton in expression.split():
        if jeton in ("+", "-", "*", "/"):
            b = pile.depiler(); a = pile.depiler()
            if jeton == "+": r = a + b
            elif jeton == "-": r = a - b
            elif jeton == "*": r = a * b
            else: r = a / b
            pile.empiler(r)
        else:
            pile.empiler(float(jeton))
    return pile.depiler()
Attention à l'ordre : b est dépilé AVANT a, crucial pour - et /.

🎯 Défi bonus — Annuler / Rétablir

Une classe EditeurTexte (ecrire/annuler/retablir) sur le même principe à deux piles que le navigateur.

Séance 4 — Piles avancées + Les files (FIFO)

Parenthèses équilibrées, et la seconde structure linéaire du programme

Durée : 2hFIFOtête + queue

1 parentheses_equilibrees

Voir la réponse 
def parentheses_equilibrees(expression):
    pile = Pile()
    paires = {')': '(', ']': '[', '}': '{'}
    for car in expression:
        if car in "([{":
            pile.empiler(car)
        elif car in ")]}":
            if pile.est_vide() or pile.depiler() != paires[car]:
                return False
    return pile.est_vide()

2 Classe File (tête + queue, tout en O(1))

Voir la réponse 
class File:
    def __init__(self):
        self.tete = None
        self.queue = None
        self._taille = 0

    def est_vide(self):
        return self.tete is None

    def enfiler(self, valeur):
        nouveau = Maillon(valeur)
        if self.est_vide():
            self.tete = nouveau
            self.queue = nouveau
        else:
            self.queue.suivant = nouveau
            self.queue = nouveau
        self._taille += 1

    def defiler(self):
        valeur = self.tete.valeur
        self.tete = self.tete.suivant
        if self.tete is None:
            self.queue = None
        self._taille -= 1
        return valeur

    def premier(self):
        return self.tete.valeur

    def taille(self):
        return self._taille
Sans la référence queue, enfiler() devrait parcourir toute la file : O(n) au lieu de O(1).

3 Le jeu de la patate chaude

Voir la réponse 
def patate_chaude(noms, k):
    file = File()
    for nom in noms:
        file.enfiler(nom)
    while file.taille() > 1:
        for _ in range(k):
            file.enfiler(file.defiler())
        elimine = file.defiler()
        print(f"{elimine} est éliminé !")
    return file.premier()
file.enfiler(file.defiler()) fait "tourner" un élément de la tête vers la queue sans le perdre.
Bilan du chapitre — Pile (LIFO) : pile d'appels récursifs, annuler/rétablir, historique de navigation, parenthésage, RPN. File (FIFO) : files d'attente, impression, traitement dans l'ordre d'arrivée, et (l'an prochain) parcours en largeur (BFS) d'un graphe.

🎯 Défi bonus — Calculatrice avec priorités

Évaluer "3 + 4 * 2" = 11 (et non 14), en respectant les priorités, avec deux piles.

Voir la réponse 
def calculer_expression(expression):
    priorite = {'+': 1, '-': 1, '*': 2, '/': 2}
    valeurs = Pile()
    operateurs = Pile()

    def appliquer():
        b = valeurs.depiler(); a = valeurs.depiler()
        op = operateurs.depiler()
        if op == '+': valeurs.empiler(a + b)
        elif op == '-': valeurs.empiler(a - b)
        elif op == '*': valeurs.empiler(a * b)
        else: valeurs.empiler(a / b)

    for jeton in expression.split():
        if jeton in priorite:
            while (not operateurs.est_vide() and operateurs.consulter() in priorite
                   and priorite[operateurs.consulter()] >= priorite[jeton]):
                appliquer()
            operateurs.empiler(jeton)
        else:
            valeurs.empiler(float(jeton))

    while not operateurs.est_vide():
        appliquer()
    return valeurs.depiler()