Introduction

Les piles, les files et les files doubles sont des types abstraits de données qui organisent les éléments selon un ordre d’accès précis. Elles interviennent dans les compilateurs, les systèmes d’exploitation, les navigateurs, les serveurs d’impression, les systèmes de réservation et de nombreuses simulations. Ce chapitre présente leurs principes, leurs opérations, leurs implémentations et leurs usages.

Objectifs d’apprentissage

• Expliquer les principes LIFO et FIFO.
• Définir les opérations fondamentales d’une pile, d’une file et d’une deque.
• Implémenter une pile avec un tableau ou une liste chaînée.
• Implémenter une file linéaire et une file circulaire.
• Détecter et gérer le débordement et le sous-dépassement.
• Choisir la structure la plus adaptée à un problème concret.
• Analyser la complexité temporelle et spatiale des opérations.

4.1 Piles

4.1.1 Principe LIFO

Une pile est une structure dans laquelle le dernier élément ajouté est le premier à être retiré. Ce comportement est appelé LIFO, pour Last In, First Out. L’accès est limité à une seule extrémité appelée sommet.

4.1.2 Opérations fondamentales

TAD Pile<T>
   Empiler(x : T)
   Dépiler() : T
   Sommet() : T
   EstVide() : Booléen
   Taille() : Entier
FinTAD

4.1.3 Exemple de trace

4.2 Implémentation d’une pile

4.2.1 Implémentation avec un tableau

Une pile à capacité fixe peut être stockée dans un tableau. Un indice sommet indique la position du dernier élément occupé. Lorsque la pile est vide, sommet vaut généralement -1.

Type PileTableau
   elements : Tableau[0..CAPACITE-1] de Élément
   sommet : Entier
FinType

Procédure Initialiser(P)
   P.sommet ← -1
FinProcédure

Fonction EstVide(P) : Booléen
   Retourner P.sommet = -1
FinFonction

Fonction EstPleine(P) : Booléen
   Retourner P.sommet = CAPACITE - 1
FinFonction

Empiler avec un tableau

Procédure Empiler(P, x)
   Si EstPleine(P) Alors
       Signaler "Débordement de pile"
   Sinon
       P.sommet ← P.sommet + 1
       P.elements[P.sommet] ← x
   FinSi
FinProcédure
Dépiler avec un tableau
Fonction Dépiler(P) : Élément
   Si EstVide(P) Alors
       Signaler "Sous-dépassement de pile"
   Sinon
       x ← P.elements[P.sommet]
       P.sommet ← P.sommet - 1
       Retourner x
   FinSi
FinFonction

4.2.2 Implémentation avec une liste chaînée

Dans une pile chaînée, le sommet correspond à la tête de la liste. Empiler revient à insérer en tête et dépiler revient à supprimer la tête.

Type Noeud
   valeur : Élément
   suivant : Référence vers Noeud
FinType

Type PileChainee
   sommet : Référence vers Noeud
   taille : Entier
FinType

Procédure Empiler(P, x)
   nouveau ← Allouer(Noeud)
   nouveau.valeur ← x
   nouveau.suivant ← P.sommet
   P.sommet ← nouveau
   P.taille ← P.taille + 1
FinProcédure
Fonction Dépiler(P) : Élément
   Si P.sommet = NUL Alors
       Signaler "Pile vide"
   FinSi
   ancien ← P.sommet
   x ← ancien.valeur
   P.sommet ← ancien.suivant
   Libérer(ancien)
   P.taille ← P.taille - 1
   Retourner x
FinFonction

4.2.3 Débordement et sous-dépassement

Le débordement se produit lorsqu’une insertion est demandée alors qu’aucun emplacement n’est disponible. Le sous-dépassement se produit lorsqu’une suppression ou une consultation est demandée sur une pile vide.

• Prévenir le débordement en testant EstPleine avant Empiler.
• Prévenir le sous-dépassement en testant EstVide avant Dépiler ou Sommet.
• Choisir une stratégie d’erreur : exception, code de retour, valeur optionnelle ou message contrôlé.
• Ne jamais retourner silencieusement une valeur non initialisée.

4.3 Files

4.3.1 Principe FIFO

Une file respecte l’ordre FIFO, First In, First Out : le premier élément ajouté est le premier retiré. L’ajout s’effectue à la fin et le retrait à la tête.

TAD File<T>
   Enfiler(x : T)
   Défiler() : T
   Tête() : T
   Fin() : T
   EstVide() : Booléen
   Taille() : Entier
FinTAD

4.3.2 File avec une liste chaînée

Une implémentation efficace maintient deux références : tête pour le premier nœud et fin pour le dernier. Ainsi, Enfiler et Défiler restent en O(1).

Procédure Enfiler(F, x)
   nouveau ← Allouer(Noeud)
   nouveau.valeur ← x
   nouveau.suivant ← NUL
   Si F.fin = NUL Alors
       F.tête ← nouveau
       F.fin ← nouveau
   Sinon
       F.fin.suivant ← nouveau
       F.fin ← nouveau
   FinSi
   F.taille ← F.taille + 1
FinProcédure
Fonction Défiler(F) : Élément
   Si F.tête = NUL Alors
       Signaler "File vide"
   FinSi
   ancien ← F.tête
   x ← ancien.valeur
   F.tête ← ancien.suivant
   Si F.tête = NUL Alors
       F.fin ← NUL
   FinSi
   Libérer(ancien)
   F.taille ← F.taille - 1
   Retourner x
FinFonction

4.4 Files circulaires

4.4.1 Motivation

Dans une file stockée dans un tableau linéaire, les suppressions successives laissent des cases libres au début. Une file circulaire réutilise ces cases grâce à des indices calculés modulo la capacité.

4.4.2 Indices de tête et de fin

• L’indice tête désigne le premier élément à retirer.
• L’indice fin désigne la prochaine case disponible ou le dernier élément, selon la convention.
• Le déplacement circulaire utilise : indice ← (indice + 1) mod capacité.
• Un compteur taille simplifie la distinction entre file vide et file pleine.

Type FileCirculaire
   elements : Tableau[0..CAPACITE-1] de Élément
   tête : Entier
   fin : Entier
   taille : Entier
FinType

Fonction EstVide(F) : Booléen
   Retourner F.taille = 0
FinFonction

Fonction EstPleine(F) : Booléen
   Retourner F.taille = CAPACITE
FinFonction
Procédure Enfiler(F, x)
   Si EstPleine(F) Alors
       Signaler "File pleine"
   FinSi
   F.elements[F.fin] ← x
   F.fin ← (F.fin + 1) mod CAPACITE
   F.taille ← F.taille + 1
FinProcédure

Fonction Défiler(F) : Élément
   Si EstVide(F) Alors
       Signaler "File vide"
   FinSi
   x ← F.elements[F.tête]
   F.tête ← (F.tête + 1) mod CAPACITE
   F.taille ← F.taille - 1
   Retourner x
FinFonction

4.5 Files doubles

4.5.1 Définition

Une file double, ou deque, autorise l’ajout et la suppression aux deux extrémités. Elle généralise donc les piles et les files.

Une deque peut être implémentée par une liste doublement chaînée ou par un tableau circulaire. Dans les deux cas, les opérations aux extrémités peuvent être réalisées en O(1).

TAD Deque<T>
   AjouterDébut(x : T)
   AjouterFin(x : T)
   RetirerDébut() : T
   RetirerFin() : T
   Premier() : T
   Dernier() : T
   EstVide() : Booléen
FinTAD

4.5.2 Applications des deques

• Historique avec ajout et suppression aux deux extrémités.
• Fenêtre glissante pour maintenir un minimum ou un maximum.
• Planification de tâches avec priorité locale.
• Parcours en largeur bidirectionnel.
• Implémentation d’une pile ou d’une file selon le besoin.

Applications guidées

Application 1 — Vérification des parenthèses

Objectif : vérifier qu’une expression contient des parenthèses, crochets et accolades correctement appariés et imbriqués.

Fonction ParenthèsesCorrectes(texte) : Booléen
   Initialiser une pile P
   Pour chaque caractère c de texte Faire
       Si c est ouvrant Alors
            Empiler(P, c)
       SinonSi c est fermant Alors
            Si EstVide(P) Alors
                Retourner Faux
            FinSi
            ouvrant ← Dépiler(P)
            Si ouvrant ne correspond pas à c Alors
                Retourner Faux
            FinSi
       FinSi
   FinPour
   Retourner EstVide(P)
FinFonction

Application 2 — Évaluation d’expressions

La pile permet d’évaluer facilement une expression postfixée. Les opérandes sont empilés ; lorsqu’un opérateur est rencontré, les deux opérandes nécessaires sont dépilés.

Fonction EvaluerPostfixe(tokens) : Réel
   Initialiser une pile P
   Pour chaque token t Faire
       Si t est un nombre Alors
            Empiler(P, t)
       Sinon
            b ← Dépiler(P)
            a ← Dépiler(P)
            Empiler(P, Appliquer(t, a, b))
       FinSi
   FinPour
   résultat ← Dépiler(P)
   Si Non EstVide(P) Alors Signaler "Expression invalide"
   Retourner résultat
FinFonction

Application 3 — Gestion d’une file d’impression

Chaque document est ajouté dans une file avec son identifiant, son nombre de pages et son propriétaire. L’imprimante traite les documents dans leur ordre d’arrivée.

Procédure AjouterDocument(file, document)
   Enfiler(file, document)
FinProcédure

Procédure TraiterProchain(file)
   Si EstVide(file) Alors
       Afficher "Aucun document"
   Sinon
       doc ← Défiler(file)
       Imprimer(doc)
   FinSi
FinProcédure

Application 4 — Système de réservation

Lorsqu’une ressource est complète, les nouvelles demandes sont placées dans une file d’attente. Dès qu’une place se libère, la première demande est confirmée.

Procédure DemanderRéservation(demande)
   Si placeDisponible Alors
       Confirmer(demande)
   Sinon
       Enfiler(fileAttente, demande)
   FinSi
FinProcédure

Procédure LibérerPlace()
   Si Non EstVide(fileAttente) Alors
       demande ← Défiler(fileAttente)
       Confirmer(demande)
   Sinon
       placeDisponible ← Vrai
   FinSi
FinProcédure

Application 5 — Simulation d’une file d’attente

Une simulation étudie les temps d’attente d’un guichet. Chaque client possède une heure d’arrivée et une durée de service. La file conserve les clients non encore servis.

• À chaque unité de temps, ajouter les clients arrivés.
• Si le serveur est libre et la file non vide, défiler un client.
• Calculer son temps d’attente : début du service − heure d’arrivée.
• Mettre à jour l’instant de fin du service.
• À la fin, calculer le temps d’attente moyen et maximal.

Comparaison synthétique des structures

Erreurs fréquentes et bonnes pratiques

Travaux dirigés

TD 1 — Trace d’une pile

Tracer la pile après : Empiler(2), Empiler(7), Dépiler(), Empiler(5), Sommet().

TD 2 — Pile avec tableau

Écrire les fonctions Taille, Sommet et Vider pour une pile stockée dans un tableau.

TD 3 — Inverser une chaîne

Utiliser une pile pour inverser une chaîne de caractères.

TD 4 — Parenthèses

Étendre la vérification aux symboles (), [] et {}.

TD 5 — File chaînée

Écrire les opérations Enfiler et Défiler en maintenant tête et fin.

TD 6 — File circulaire

Pour une capacité 5, tracer tête, fin et taille après plusieurs ajouts et retraits.

TD 7 — Deque

Montrer comment une deque peut simuler une pile puis une file.

TD 8 — Impression

Ajouter une priorité simple : les documents urgents sont insérés au début de la deque.

TD 9 — Réservation

Proposer une stratégie d’annulation d’une demande en attente.

TD 10 — Simulation

Calculer le temps d’attente moyen de clients dont les arrivées et durées sont fournies.

Corrigés indicatifs des travaux dirigés

Corrigé TD 1

Corrigé TD 2

Fonction Taille(P) : Entier
   Retourner P.sommet + 1
FinFonction

Fonction Sommet(P) : Élément
   Si EstVide(P) Alors Signaler "Pile vide"
   Retourner P.elements[P.sommet]
FinFonction

Procédure Vider(P)
   P.sommet ← -1
FinProcédure

Corrigé TD 3

Fonction Inverser(chaine) : Chaîne
   Initialiser une pile P
   Pour chaque caractère c Faire Empiler(P, c)
   résultat ← ""
   TantQue Non EstVide(P) Faire
       résultat ← résultat + Dépiler(P)
   FinTantQue
   Retourner résultat
FinFonction

Corrigé TD 4

La correction correspond à l’algorithme ParenthèsesCorrectes présenté dans les applications. La fonction de correspondance doit vérifier les couples (,), [,] et {,}.

Corrigé TD 5

Enfiler crée un nœud, l’attache après fin et met à jour fin. Défiler supprime tête ; si la file devient vide, fin doit également devenir NUL.

Corrigé TD 6

Corrigé TD 7

• Pile : AjouterFin correspond à Empiler et RetirerFin à Dépiler.
• File : AjouterFin correspond à Enfiler et RetirerDébut à Défiler.

Corrigé TD 8

Utiliser une deque : AjouterDébut pour les documents urgents et AjouterFin pour les documents ordinaires. Le traitement utilise toujours RetirerDébut.

Corrigé TD 9

Une annulation arbitraire n’est pas naturellement efficace dans une file. On peut parcourir une structure chaînée et supprimer la demande, ou marquer la demande comme annulée puis l’ignorer lorsqu’elle atteint la tête.

Corrigé TD 10

Pour chaque client, le début du service est le maximum entre son arrivée et la fin du service précédent. L’attente vaut début − arrivée. La moyenne est la somme des attentes divisée par le nombre de clients.

Travail pratique — Gestionnaire de tâches

Développer une application qui combine une pile d’historique, une file de tâches ordinaires et une deque de tâches prioritaires.

Fonctionnalités attendues

• Ajouter une tâche ordinaire en fin de file.
• Ajouter une tâche urgente en tête de deque.
• Traiter la prochaine tâche.
• Annuler la dernière action grâce à une pile.
• Afficher les tâches en attente sans modifier leur ordre.
• Gérer les structures vides et les erreurs.

Étapes proposées

1. Définir le type Tâche.
2. Spécifier les TAD utilisés et leurs contrats.
3. Implémenter les opérations de base.
4. Construire le menu principal.
5. Préparer des jeux d’essai.
6. Mesurer la complexité des opérations.

Synthèse du chapitre

• Une pile suit l’ordre LIFO et travaille au sommet.
• Une file suit l’ordre FIFO, avec ajout en fin et retrait en tête.
• Une file circulaire réutilise efficacement les cases d’un tableau.
• Une deque autorise les opérations aux deux extrémités.
• Les implémentations chaînées sont dynamiques ; les tableaux offrent une bonne localité mémoire.
• Les opérations principales sont généralement en O(1).
• La gestion explicite des structures vides et pleines est indispensable.

Glossaire

Auto-évaluation

Fin du chapitre 4