05 — Piles et Files : Cours complet

Niveau : Université / Ingénierie — Durée de lecture : ~55 min

---

Table des matières

1. Pile (Stack) : LIFO
2. Applications des piles
3. File (Queue) : FIFO
4. Applications des files
5. Deque
6. File de priorité (Priority Queue)
7. Implémentations : array, linked, resizable
8. Applications réelles
9. Résumé

---

1. Pile (Stack) : LIFO

1.1 Définition

Une pile suit le principe LIFO (Last In, First Out) : le dernier élément inséré est le premier retiré.

Diagramme en cours de génération...

1.2 Implémentation sur tableau (la plus courante)

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

    def push(self, x):
        self.data.append(x)          # O(1) amorti

    def pop(self):
        if not self.data:
            raise IndexError("pile vide")
        return self.data.pop()       # O(1)

    def peek(self):
        if not self.data:
            raise IndexError("pile vide")
        return self.data[-1]

    def is_empty(self):
        return len(self.data) == 0

Python list est un tableau dynamique : append et pop en fin sont O(1) amorti. C'est LA pile par défaut du langage.

1.3 Implémentation sur liste chaînée

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

class PileChainee:
    def __init__(self):
        self.sommet = None

    def push(self, x):
        n = Noeud(x)
        n.suivant = self.sommet
        self.sommet = n

    def pop(self):
        if self.sommet is None:
            raise IndexError("pile vide")
        x = self.sommet.valeur
        self.sommet = self.sommet.suivant
        return x

    def peek(self):
        if self.sommet is None:
            raise IndexError("pile vide")
        return self.sommet.valeur

Toutes les opérations O(1). La version chaînée n'a jamais besoin de redimensionnement.

---

2. Applications des piles

2.1 Pile d'appels (call stack)

Chaque appel de fonction empile un frame (variables locales, adresse de retour). Le retour dépile.

def a():
    return b()

def b():
    return c()

def c():
    return 42

Call stack :
a() → b() → c()   (sommet = c())
après retour de c : a() → b()

Stack overflow : profondeur de récursion illimitée → mémoire épuisée.

2.2 Undo d'un éditeur

class Editeur:
    def __init__(self):
        self.historique = Pile()
        self.texte = ""

    def taper(self, texte):
        self.historique.push(self.texte)   # état précédent
        self.texte += texte

    def annuler(self):
        if not self.historique.is_empty():
            self.texte = self.historique.pop()

2.3 Parsing : expressions et parenthèses

Vérifier que les parenthèses () [] {} sont équilibrées :

def parentheses_equilibrees(expression):
    correspondance = {')': '(', ']': '[', '}': '{'}
    pile = []
    for c in expression:
        if c in "([{":
            pile.append(c)
        elif c in ")]}":
            if not pile or pile.pop() != correspondance[c]:
                return False
    return len(pile) == 0

print(parentheses_equilibrees("(a + b) * [c - {d}]"))   # True
print(parentheses_equilibrees("([)]"))                  # False

2.4 Évaluation d'expressions : notation postfixée (RPN)

3 4 + 2 * = (3+4)×2 = 14 :

def evaluer_postfix(expression):
    pile = []
    for token in expression.split():
        if token.isdigit():
            pile.append(int(token))
        else:
            b = pile.pop()
            a = pile.pop()
            if token == '+': pile.append(a + b)
            elif token == '-': pile.append(a - b)
            elif token == '*': pile.append(a * b)
            elif token == '/': pile.append(a / b)
    return pile.pop()

print(evaluer_postfix("3 4 + 2 *"))   # 14

2.5 Autres applications

---

3. File (Queue) : FIFO

3.1 Définition

Une file suit le principe FIFO (First In, First Out) : le premier inséré est le premier retiré.

Diagramme en cours de génération...

3.2 Piège : pop(0) en Python est O(n)

liste = [1, 2, 3]
x = liste.pop(0)   # O(n) — décalage de tout le reste !

Il faut soit collections.deque, soit une file circulaire faite main.

3.3 Implémentation : file circulaire sur tableau

class FileCirculaire:
    def __init__(self, capacite):
        self.data = [None] * capacite
        self.capacite = capacite
        self.tete = 0
        self.taille = 0

    def enqueue(self, x):
        if self.taille == self.capacite:
            raise OverflowError("file pleine")
        pos = (self.tete + self.taille) % self.capacite
        self.data[pos] = x
        self.taille += 1

    def dequeue(self):
        if self.taille == 0:
            raise IndexError("file vide")
        x = self.data[self.tete]
        self.tete = (self.tete + 1) % self.capacite
        self.taille -= 1
        return x

    def front(self):
        if self.taille == 0:
            raise IndexError("file vide")
        return self.data[self.tete]

• enqueue/dequeue : O(1) garanti (aucun décalage).
• Limite : capacité fixe → variante « resizable » (section 7).

3.4 Implémentation sur liste chaînée

class FileChainee:
    def __init__(self):
        self.tete = None
        self.queue = None

    def enqueue(self, x):
        n = Noeud(x)
        if self.queue:
            self.queue.suivant = n
        else:
            self.tete = n
        self.queue = n

    def dequeue(self):
        if self.tete is None:
            raise IndexError("file vide")
        x = self.tete.valeur
        self.tete = self.tete.suivant
        if self.tete is None:
            self.queue = None
        return x

O(1) pour enqueue (queue gardée) et dequeue (tête). Pas de capacité.

---

4. Applications des files

4.1 BFS — parcours en largeur

Le BFS (chapitre 08) utilise une file pour explorer les nœuds par niveau :

def bfs(graphe, depart):
    file = FileChainee()
    visites = {depart}
    file.enqueue(depart)
    ordre = []
    while file.tete is not None:
        noeud = file.dequeue()
        ordre.append(noeud)
        for voisin in graphe[noeud]:
            if voisin not in visites:
                visites.add(voisin)
                file.enqueue(voisin)
    return ordre

graphe = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
}
print(bfs(graphe, 'A'))   # ['A', 'B', 'C', 'D']

4.2 Buffers

• Buffer de streaming : les données arrivent dans l'ordre, sont consommées dans l'ordre.
• Spooler d'impression : documents en attente, FIFO.
• Buffer audio/vidéo : paquets en séquence.

4.3 Scheduling OS

• Round-robin : chaque processus reçoit un quantum, puis retourne en fin de file.
• FIFO scheduling : les tâches sont traitées dans l'ordre d'arrivée.
• Work queue / task queue : file de tâches consommée par des workers.

class SchedulerRoundRobin:
    def __init__(self, quantum):
        self.file = FileChainee()
        self.quantum = quantum

    def ajouter(self, processus):
        self.file.enqueue(processus)

    def tourner(self):
        # on fait tourner la file : on retire et réinsère en queue
        processus = self.file.dequeue()
        print(f"exécute {processus} pendant {self.quantum}")
        self.file.enqueue(processus)   # retour en fin de file
        return processus

4.4 Autres applications

---

5. Deque

5.1 Définition

Un deque (double-ended queue) permet l'insertion et la suppression aux deux extrémités.

5.2 Implémentation

En Python : collections.deque (implémentation C, blocs de tableaux liés). Manuellement : liste doublement chaînée ou tableau circulaire.

from collections import deque

d = deque()
d.append(1)          # addLast
d.appendleft(0)      # addFirst
d.pop()              # removeLast
d.popleft()          # removeFirst

5.3 Usages

• BFS bidirectionnel (un deque par côté).
• Window sliding : problèmes de fenêtre glissante (max dans une fenêtre).
• Undo/redo : un deque de chaque côté du curseur.
• Palindrome : comparer popleft et pop jusqu'au centre.
• Remplacement d'une pile OU d'une file selon les besoins.

---

6. File de priorité (Priority Queue)

6.1 Définition

Une file de priorité retire toujours l'élément de priorité extrême (min ou max), pas forcément le premier arrivé.

6.2 Implémentation canonique : le tas binaire

Un tas min (min-heap) est un arbre binaire complet où chaque parent ≤ ses enfants.

Diagramme en cours de génération...

Propriétés :

• Racine = minimum.
• Arbre complet → stocké dans un tableau : enfant gauche de i = 2i+1, droit = 2i+2, parent = (i-1)//2.
• push : insérer en fin, remonter (bubble up) tant que < parent.
• extractMin : retirer la racine, y mettre le dernier élément, tamiser (bubble down).

6.3 Implémentation Python

class TasMin:
    def __init__(self):
        self.data = []

    def _parent(self, i):
        return (i - 1) // 2

    def _enfants(self, i):
        return 2 * i + 1, 2 * i + 2

    def push(self, x):
        self.data.append(x)
        i = len(self.data) - 1
        while i > 0 and self.data[i] < self.data[self._parent(i)]:
            self.data[i], self.data[self._parent(i)] = self.data[self._parent(i)], self.data[i]
            i = self._parent(i)

    def extract_min(self):
        if not self.data:
            raise IndexError("tas vide")
        racine = self.data[0]
        dernier = self.data.pop()
        if self.data:
            self.data[0] = dernier
            self._tamiser(0)
        return racine

    def peek(self):
        return self.data[0]

    def _tamiser(self, i):
        n = len(self.data)
        while True:
            g, d = self._enfants(i)
            plus_petit = i
            if g < n and self.data[g] < self.data[plus_petit]:
                plus_petit = g
            if d < n and self.data[d] < self.data[plus_petit]:
                plus_petit = d
            if plus_petit == i:
                return
            self.data[i], self.data[plus_petit] = self.data[plus_petit], self.data[i]
            i = plus_petit

6.4 Tas max / min dans les langages

6.5 Applications

• Dijkstra : extraire le nœud le plus proche (chapitre 08).
• Scheduling prioritaire : OS, tâches critiques.
• K plus grands éléments : tas de taille k.
• Huffman coding : fusionner les deux plus petits.
• Merging de k listes triées : toujours extraire le min global.
• Priority queue dans les routers (QoS).

---

7. Implémentations : array, linked, resizable

7.1 Comparaison

7.2 File resizable (tableau circulaire redimensionnable)

class FileResizable:
    def __init__(self, capacite_initiale=8):
        self.data = [None] * capacite_initiale
        self.tete = 0
        self.taille = 0
        self.capacite = capacite_initiale

    def _redimensionner(self, nouvelle_capacite):
        nouveau = [None] * nouvelle_capacite
        for i in range(self.taille):
            nouveau[i] = self.data[(self.tete + i) % self.capacite]
        self.data = nouveau
        self.tete = 0
        self.capacite = nouvelle_capacite

    def enqueue(self, x):
        if self.taille == self.capacite:
            self._redimensionner(self.capacite * 2)
        pos = (self.tete + self.taille) % self.capacite
        self.data[pos] = x
        self.taille += 1

    def dequeue(self):
        if self.taille == 0:
            raise IndexError("file vide")
        x = self.data[self.tete]
        self.tete = (self.tete + 1) % self.capacite
        self.taille -= 1
        if self.taille < self.capacite // 4 and self.capacite > 8:
            self._redimensionner(self.capacite // 2)
        return x

• Amorti : O(1) par opération (même analyse que le tableau dynamique du chapitre 01).
• C'est l'implémentation réelle des deques/queues en Java (ArrayDeque), Go (slices), etc.

7.3 Quand choisir quoi

---

8. Applications réelles

8.1 Undo d'un éditeur (déjà vu)

Pile d'états (ou d'actions inverses). Redo = seconde pile.

8.2 Call stack

Implémentation hardware/OS de la pile de fonctions.

8.3 OS scheduling

• FIFO : files de processus.
• Round-robin : file circulaire (ou deque).
• Priorité : file de priorité (ou files multiples par niveau de priorité).

8.4 Réseau et brokers

• Message queues (RabbitMQ, Kafka) : FIFO par partition.
• Packet queues : files dans les routeurs.
• QoS : files de priorité.

8.5 BFS, Dijkstra, A*

• BFS : file simple.
• Dijkstra/A* : file de priorité (tas).

8.6 Compilateurs et parsing

• Pile pour les grammaires (Shunting-yard, evaluation).
• File pour les tokens dans certains pipelines.

---

9. Résumé

1. Pile (LIFO) : push/pop/peek O(1) — undo, call stack, parsing, DFS.
2. File (FIFO) : enqueue/dequeue/front O(1) — BFS, buffers, scheduling.
3. Piège : pop(0) Python = O(n) ; utiliser deque ou file circulaire.
4. File circulaire : O(1) garanti sans décalage ; version resizable O(1) amorti.
5. Deque : quatre opérations d'extrémité O(1) — fenêtres glissantes, BFS bidirectionnel.
6. File de priorité : tas binaire — push/extractMin O(log n), peek O(1) — Dijkstra, scheduling prioritaire, Huffman.
7. Implémentations : tableau (cache, resizable) vs chaînée (pas de redimensionnement).

---

Exercices d'auto-évaluation

1. Écrire le tracé de la pile pendant l'évaluation de "5 1 2 + 4 × + 3 −" (RPN).
2. Pourquoi pop(0) est-il O(n) en Python ?
3. Comment implémenter un undo/redo avec deux piles ?
4. Quelle est la complexité de push et extractMin dans un tas binaire ? Pourquoi ?
5. Citer deux applications industrielles d'une file et deux d'une file de priorité.
6. Convertir une file circulaire en file resizable : quel coût amorti ?

Passez au quiz puis aux TP.