Vue d'ensemble
La pile et la file sont les deux structures de données linéaires les plus utilisées en informatique. Toutes deux stockent une collection d'éléments et ne les rendent que dans un ordre imposé : la pile façon « pile d'assiettes » (on retire la dernière posée), la file façon « file d'attente à la boulangerie » (on sert le premier arrivé). En MP2I on les implémente en C par listes chaînées, ce qui donne toutes les opérations de base en temps constant .
- Type abstrait pile (LIFO) et ses opérations : créer, empiler, dépiler, sommet, tester si vide.
- Type abstrait file (FIFO) et ses opérations : créer, enfiler, défiler, tester si vide.
- Implémentation par listes chaînées ; coût de chaque opération.
- Applications : bon parenthésage, parcours de structures, gestion de tâches.
Prérequis
- Structures (
struct), pointeurs et allocation dynamique (malloc,free). - Listes chaînées : cellule contenant une valeur et un pointeur
suivant, terminaison parNULL. - Passage par adresse (
&et déréférencement*) pour modifier une variable de l'appelant.
Les pointeurs vous donnent le vertige ? C'est le point qui bloque le plus en début de MP2I. Nos mentors alumni X · Centrale · Mines reprennent avec vous chaque *p et chaque ->suivant jusqu'à ce que le mécanisme devienne une évidence.
La pile (LIFO)
Une pile est une collection d'éléments dans laquelle on n'ajoute et on ne retire qu'à une seule extrémité, appelée le sommet. Le dernier élément ajouté est le premier retiré : on parle de discipline LIFO (Last In, First Out). Les opérations sont : empiler (ajouter au sommet), dépiler (retirer le sommet), sommet (lire sans retirer) et tester si la pile est vide.
Le type en C
On réutilise la cellule d'une liste chaînée. Une pile est simplement un pointeur vers sa cellule de sommet ; la pile vide est le pointeur NULL.
struct Cellule {
int valeur; // la donnée stockée dans la cellule
struct Cellule *suivant; // pointeur vers la cellule du dessous
};
typedef struct Cellule Cellule;
typedef Cellule* Pile; // une pile = un pointeur vers son sommetint valeur;la valeur portée par la cellule ; ici des entiers, mais le principe est identique pour tout autre type.struct Cellule *suivant;l'adresse de la cellule située juste en dessous dans la pile. La cellule du fond pointe vers NULL.typedef Cellule* Pile;on baptise Pile le type « pointeur vers cellule ». Une variable de type Pile contient donc l'adresse du sommet, et NULL représente la pile vide.Tester si la pile est vide
int est_vide(Pile p) {
return p == NULL; // vraie (1) ssi aucune cellule
}return p == NULL;la pile est vide exactement quand son sommet vaut NULL. L'expression p == NULL vaut 1 (vrai) ou 0 (faux), ce que la fonction renvoie directement.Empiler (push)
Empiler crée une cellule qui devient le nouveau sommet et pointe vers l'ancien sommet. Comme on modifie la variable pile de l'appelant, on la passe par adresse : le paramètre est un Pile * (pointeur vers un pointeur).
void empiler(Pile *p, int x) {
Cellule *nouvelle = malloc(sizeof(Cellule));
nouvelle->valeur = x; // on range la donnée
nouvelle->suivant = *p; // la nouvelle pointe vers l'ancien sommet
*p = nouvelle; // le sommet devient la nouvelle cellule
}void empiler(Pile *p, int x)p est l'adresse de la variable pile ; *p désigne donc le sommet lui-même, que l'on va pouvoir modifier durablement.malloc(sizeof(Cellule))réserve dans le tas la mémoire d'une cellule et renvoie son adresse, rangée dans nouvelle.nouvelle->valeur = x;on écrit la valeur à empiler dans la nouvelle cellule (-> = accès à un champ via un pointeur).nouvelle->suivant = *p;on accroche la nouvelle cellule au-dessus de l'ancien sommet *p : la nouvelle « regarde » l'ancien sommet.*p = nouvelle;on met à jour le sommet de l'appelant : il pointe désormais sur la cellule fraîchement créée. C'est cette ligne qui rend le changement visible à l'extérieur.Sommet et dépiler (pop)
int sommet(Pile p) {
return p->valeur; // suppose la pile non vide
}
int depiler(Pile *p) {
if (*p == NULL) { // protection : pile vide
fprintf(stderr, "Erreur : pile vide\n");
exit(EXIT_FAILURE);
}
Cellule *tete = *p; // on retient l'ancien sommet
int x = tete->valeur; // la valeur à renvoyer
*p = tete->suivant; // le sommet descend d'un cran
free(tete); // on libère la cellule retirée
return x;
}return p->valeur;sommet lit la valeur du sommet sans retirer la cellule. On passe p par valeur car on ne modifie rien.if (*p == NULL) { ... exit ... }garde-fou indispensable : dépiler une pile vide n'a pas de sens et ferait planter le programme à la ligne suivante. On arrête proprement avec un message d'erreur.Cellule *tete = *p;on garde l'adresse de l'actuel sommet, sinon on la perdrait en déplaçant le sommet et on ne pourrait plus la libérer (fuite mémoire).int x = tete->valeur;on récupère la valeur avant de libérer la cellule, car après free elle serait inaccessible.*p = tete->suivant;le nouveau sommet est la cellule d'en dessous. Si la pile n'avait qu'un élément, tete->suivant vaut NULL et la pile redevient vide.free(tete);on rend au système la mémoire de la cellule retirée : indispensable pour éviter les fuites.if (*p == NULL), l'accès tete->valeur déréférence NULL : erreur de segmentation. Protégez toujours depiler (et sommet). De même, ne jamais oublier free : chaque malloc d'empilage doit avoir son free de dépilage.Trace d'une séquence d'opérations
Déroulons empiler 1, empiler 2, empiler 3, puis un depiler. On note la pile de gauche (fond) à droite (sommet).
| Opération | État de la pile (fond → sommet) | Sommet | Valeur renvoyée |
|---|---|---|---|
| départ | (vide) | — | — |
| empiler 1 | 1 | 1 | — |
| empiler 2 | 1, 2 | 2 | — |
| empiler 3 | 1, 2, 3 | 3 | — |
| depiler | 1, 2 | 2 | 3 ✓ |
Conforme au principe LIFO : le dernier empilé (3) est le premier dépilé.
La file (FIFO)
Une file est une collection d'éléments dans laquelle on ajoute à une extrémité (la queue) et on retire à l'autre (la tête). Le premier élément ajouté est le premier retiré : discipline FIFO (First In, First Out). Les opérations sont : enfiler (ajouter en queue), défiler (retirer en tête) et tester si la file est vide.
Le type en C : deux pointeurs
Avec une liste chaînée simple, on ne peut ajouter et retirer en que si l'on connaît les deux bouts. On stocke donc deux pointeurs : tete (là où l'on défile) et queue (là où l'on enfile).
struct Cellule {
int valeur;
struct Cellule *suivant;
};
typedef struct Cellule Cellule;
struct File {
Cellule *tete; // premier arrivé : on défile ici
Cellule *queue; // dernier arrivé : on enfile ici
};
typedef struct File File;Cellule *tete;adresse de la cellule de tête (le plus ancien élément). C'est elle que l'on retire en défilant.Cellule *queue;adresse de la cellule de queue (le plus récent). C'est après elle qu'on accroche un nouvel élément, sans reparcourir la liste : d'où le .typedef struct File File;une file est une structure à deux champs (et non un simple pointeur comme la pile) : il faut suivre les deux extrémités simultanément.La file est vide quand tete == NULL (et alors queue == NULL aussi). On l'initialise ainsi :
void init_file(File *f) {
f->tete = NULL;
f->queue = NULL;
}
int file_vide(File *f) {
return f->tete == NULL;
}f->tete = NULL; f->queue = NULL;une file neuve ne contient rien : ses deux pointeurs sont NULL. On passe f par adresse pour modifier la structure de l'appelant.return f->tete == NULL;tester la tête suffit : s'il n'y a pas de tête, il n'y a aucun élément.Enfiler (ajout en queue)
void enfiler(File *f, int x) {
Cellule *nouvelle = malloc(sizeof(Cellule));
nouvelle->valeur = x;
nouvelle->suivant = NULL; // la nouvelle est en bout de file
if (f->queue == NULL) { // cas file vide
f->tete = nouvelle;
f->queue = nouvelle;
} else {
f->queue->suivant = nouvelle; // on l'accroche après l'ancienne queue
f->queue = nouvelle; // elle devient la nouvelle queue
}
}nouvelle->suivant = NULL;la nouvelle cellule sera la dernière : personne ne la suit, donc suivant vaut NULL.if (f->queue == NULL)cas particulier de la file vide : il n'y a pas d'« ancienne queue » à qui s'accrocher.f->tete = nouvelle; f->queue = nouvelle;dans une file vide, la nouvelle cellule est à la fois la tête et la queue.f->queue->suivant = nouvelle;cas général : on relie l'ancienne dernière cellule à la nouvelle. C'est ici que le pointeur queue évite de reparcourir la liste.f->queue = nouvelle;on met à jour le pointeur de queue. L'oublier est l'erreur classique : les enfilages suivants seraient mal placés.Défiler (retrait en tête)
int defiler(File *f) {
if (f->tete == NULL) { // protection : file vide
fprintf(stderr, "Erreur : file vide\n");
exit(EXIT_FAILURE);
}
Cellule *tete = f->tete;
int x = tete->valeur;
f->tete = tete->suivant; // la tête avance
if (f->tete == NULL) { // la file devient vide
f->queue = NULL; // il faut aussi annuler la queue !
}
free(tete);
return x;
}if (f->tete == NULL) { ... exit ... }garde-fou : défiler une file vide n'a pas de sens et provoquerait un déréférencement de NULL.Cellule *tete = f->tete;on retient la cellule de tête pour pouvoir la libérer après avoir fait avancer f->tete.f->tete = tete->suivant;la nouvelle tête est la cellule suivante (le deuxième plus ancien élément).if (f->tete == NULL) f->queue = NULL;si on vient de retirer le dernier élément, la tête devient NULL ; il faut aussi remettre queue à NULL, sinon queue pointerait sur une cellule libérée et le prochain enfilage planterait.free(tete);on libère la cellule retirée après en avoir lu la valeur.enfiler, oublier f->queue = nouvelle ; (2) dans defiler, oublier de remettre f->queue = NULL quand la file se vide. Dans les deux cas la file semble marcher… jusqu'au premier enfilage qui écrit à travers un pointeur invalide.Trace d'une séquence d'opérations
Déroulons enfiler 1, enfiler 2, enfiler 3, defiler, defiler, enfiler 4, defiler. On note la file de la tête (à gauche) à la queue (à droite).
| Opération | État (tête → queue) | tete | queue | Valeur renvoyée |
|---|---|---|---|---|
| départ | (vide) | NULL | NULL | — |
| enfiler 1 | 1 | 1 | 1 | — |
| enfiler 2 | 1, 2 | 1 | 2 | — |
| enfiler 3 | 1, 2, 3 | 1 | 3 | — |
| defiler | 2, 3 | 2 | 3 | 1 ✓ |
| defiler | 3 | 3 | 3 | 2 ✓ |
| enfiler 4 | 3, 4 | 3 | 4 | — |
| defiler | 4 | 4 | 4 | 3 ✓ |
Conforme au principe FIFO : les valeurs sortent dans l'ordre d'arrivée 1, 2, 3, 4.
Pile ou file, comment choisir en exam ? Le bon réflexe se travaille sur des exercices ciblés. Nos mentors alumni X · Centrale · Mines vous entraînent à reconnaître d'un coup d'œil la structure attendue par un énoncé.
Trouver un mentor →Applications classiques
Vérifier un bon parenthésage (pile)
Une chaîne de parenthèses est bien parenthésée si chaque ) ferme une ( ouverte non encore fermée, et si tout est refermé à la fin. La pile est l'outil naturel : on empile à chaque (, on dépile à chaque ).
int bien_parenthese(const char *s) {
Pile p = NULL;
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == '(') {
empiler(&p, s[i]); // une ouvrante de plus à refermer
} else if (s[i] == ')') {
if (p == NULL) return 0; // rien à fermer : mal parenthese
depiler(&p); // on ferme la derniere ouverte
}
}
return p == NULL; // vrai ssi tout a ete referme
}for (int i = 0; s[i] != '\0'; i++)on parcourt la chaîne caractère par caractère jusqu'au marqueur de fin '\0'.if (s[i] == '(') empiler(&p, s[i]);chaque parenthèse ouvrante est empilée : elle représente une fermeture encore attendue.if (p == NULL) return 0;on rencontre une ) alors que la pile est vide : il n'y a aucune ouvrante à fermer, la chaîne est invalide.depiler(&p);sinon, la ) ferme la dernière ( ouverte : on la retire de la pile (LIFO = on ferme la plus récemment ouverte).return p == NULL;à la fin, la chaîne est correcte si et seulement s'il ne reste aucune ouvrante non fermée, c'est-à-dire pile vide."(()())" → valide (pile vide à la fin) ; "(()" → invalide (il reste une () ; "())" → invalide (une ) tombe sur une pile vide) ; ")(" → invalide.Parcours de structures
- Repérez l'ordre imposé par l'énoncé : « le dernier reçu est traité en premier » → pile (LIFO) ; « premier arrivé, premier servi » → file (FIFO).
- Fermeture / annulation / retour arrière (parenthèses, undo, appels de fonctions) → pile.
- Traitement dans l'ordre d'arrivée (tâches, impressions, parcours en largeur) → file.
- Dans les deux cas, protégez le retrait sur structure vide et libérez chaque cellule.
Coût et points de vigilance
Toutes les opérations vues sont en : empiler, dépiler, sommet, tester si vide pour la pile ; enfiler, défiler, tester si vide pour la file. C'est précisément ce que garantit l'implémentation par liste chaînée avec insertion/suppression aux extrémités connues.
| Structure | Ajout | Retrait | Lecture de l'élément accessible | Test vide |
|---|---|---|---|---|
| Pile (LIFO) | empiler — | dépiler — | sommet — | |
| File (FIFO) | enfiler — | défiler — | tête — |
queue (à l'enfilage) ou de la remettre à NULL (au défilage qui vide). (3) Oublier free au retrait → fuite mémoire (pénalisée en concours).Exercices corrigés
On part d'une pile vide et on exécute : empiler 7, empiler 4, depiler, empiler 9, depiler, depiler. Donnez, dans l'ordre, les trois valeurs renvoyées par les depiler, et l'état final de la pile.
Voir la correction détaillée
7.7, 4 (sommet 4).7.7, 9 (sommet 9).7.(vide).Écrivez une fonction int taille(Pile p) qui renvoie le nombre d'éléments d'une pile sans la détruire. Quelle est sa complexité ?
Voir la correction détaillée
p de l'appelant).int taille(Pile p) {
int n = 0;
while (p != NULL) { // tant qu'il reste une cellule
n = n + 1; // on la compte
p = p->suivant; // on descend d'un cran
}
return n;
}p est passé par valeur, avancer p ne modifie pas la pile de l'appelant : la structure est préservée.On dispose d'une file f et des opérations enfiler, defiler, file_vide, ainsi que d'une pile avec empiler, depiler, est_vide. Décrivez un algorithme qui inverse l'ordre des éléments de f (le premier devient le dernier), puis justifiez qu'il fonctionne.
Voir la correction détaillée
f n'est pas vide, x = defiler(&f) puis empiler(&p, x). Les éléments sortent de la file dans l'ordre d'arrivée a1, a2, …, an et sont empilés : le sommet est an.p n'est pas vide, x = depiler(&p) puis enfiler(&f, x). La pile rend d'abord an, puis a(n-1), …, a1 ; enfilés dans cet ordre, ils donnent la file an, …, a1.defiler, un empiler, un depiler et un enfiler, tous en : coût total .Récap final — Ce qu'il faut absolument retenir
Pile et file sont deux disciplines d'accès opposées, toutes deux implémentées par liste chaînée avec des opérations en . Vérifie que tu maîtrises chaque point ci-dessous.
- Sais-tu énoncer la différence LIFO / FIFO et donner un exemple concret de chacune ?
- Sais-tu qu'une pile se code comme un simple pointeur vers son sommet, et pourquoi on insère en tête ?
- Sais-tu écrire
empileretdepileravec un paramètrePile *, et expliquer le rôle de*p? - Sais-tu pourquoi une file a besoin de deux pointeurs (
teteetqueue) pour rester en ? - Sais-tu traiter les deux cas particuliers de
enfiler(file vide) et dedefiler(file qui devient vide) ? - Sais-tu protéger un retrait sur structure vide et libérer chaque cellule avec
free? - Sais-tu utiliser une pile pour vérifier un bon parenthésage ?
- Sais-tu que toutes les opérations de base sont en ?