Cours sur les Piles et les Files
Cours sur les Piles et les Files
Data Structures · course
Voir tous les documents en programmationTous les cours en programmation
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce cours s’adresse aux étudiants en informatique et traite des structures de données avancées que sont les piles et les files. Il présente leurs définitions, modes d’implémentation contigus et chaînés, ainsi que les opérations fondamentales associées. Ce matériel permet de comprendre comment manipuler ces structures essentielles pour la gestion des données en attente de traitement.
Une pile est une liste d’éléments de même type où les ajouts, suppressions et accès ne se font qu’au sommet, c’est-à-dire le dernier élément ajouté. Elle suit le principe LIFO (Last-In, First-Out), ce qui signifie que le dernier élément inséré est le premier à être retiré.
Les opérations principales sont :
L’implémentation peut se faire avec un tableau ou une liste chaînée. Le tableau impose une taille maximale, tandis que la liste chaînée est dynamique.
La pile est représentée par une structure contenant :
#define MAX 100
typedef struct pile {
Type_element Tableau[MAX];
int sommet; // indice de la première case libre, entre 0 et MAX
} Pile;
Pile CréerPileVide() {
Pile P;
P.sommet = 0;
return P;
}
int EstPileVide(Pile P) {
return (P.sommet == 0);
}
int EstPilePleine(Pile P) {
return (P.sommet == MAX);
}
Type_element tete(Pile P) {
if (!EstPileVide(P))
return P.Tableau[P.sommet - 1];
else
printf("Erreur : Pile vide");
}
Pile Empiler(Pile P, Type_element e) {
if (!EstPilePleine(P)) {
P.Tableau[P.sommet] = e;
P.sommet++;
} else {
printf("Erreur : Pile pleine");
}
return P;
}
Pile Depiler(Pile P) {
if (!EstPileVide(P))
P.sommet--;
else
printf("Erreur : Pile vide");
return P;
}
Créer une pile vide, empiler deux éléments, puis dépiler un élément :
Pile P = CréerPileVide();
P = Empiler(P, 10);
P = Empiler(P, 20);
Type_element sommet = tete(P); // sommet vaut 20
P = Depiler(P);
sommet = tete(P); // sommet vaut 10
Une pile chaînée est une succession de cellules où chaque cellule contient :
Le pointeur P représente le sommet de la pile.
typedef struct cellule {
Type_element Val;
struct cellule* succ;
} Cellule;
typedef Cellule* Pile;
Pile CréerPileVide() {
Pile P = NULL;
return P;
}
int EstPileVide(Pile P) {
return (P == NULL);
}
Type_element tete(Pile P) {
if (!EstPileVide(P))
return P->Val;
else
printf("Erreur : Pile vide");
}
Pile Empiler(Pile P, Type_element e) {
Cellule* NC = (Cellule*)malloc(sizeof(Cellule));
if (NC) {
NC->Val = e;
NC->succ = P;
P = NC;
} else {
printf("Erreur : mémoire insuffisante");
}
return P;
}
Pile Depiler(Pile P) {
if (!EstPileVide(P)) {
Cellule* NC = P;
P = P->succ;
free(NC);
} else {
printf("Erreur : Pile vide");
}
return P;
}
Une file est une structure linéaire où l’ajout d’un élément se fait en fin, tandis que la lecture et la suppression se font au début. Elle suit le principe FIFO (First In, First Out) : le premier élément ajouté est le premier à être retiré.
Les opérations autorisées sont :
Utiliser un tableau linéaire pour une file nécessite de décaler tous les éléments à chaque suppression, ce qui est inefficace.
Pour optimiser, on utilise un tableau circulaire où les indices Tête et Queue sont calculés modulo MAX. Le tableau peut contenir au maximum MAX-1 éléments.
#define MAX 100
typedef struct file {
Type_element Tab[MAX];
int Tête;
int Queue;
} File;
File CréerFileVide() {
File f;
f.Tête = 0;
f.Queue = 0;
return f;
}
int EstFileVide(File f) {
return (f.Tête == f.Queue);
}
int EstFilePleine(File f) {
return ((f.Queue + 1) % MAX == f.Tête);
}
Type_element LireFile(File f) {
if (!EstFileVide(f))
return f.Tab[f.Tête];
else
printf("Erreur : File vide");
}
File Enfiler(Type_element e, File f) {
if (!EstFilePleine(f)) {
f.Tab[f.Queue] = e;
f.Queue = (f.Queue + 1) % MAX;
} else {
printf("Erreur : File pleine");
}
return f;
}
File Défiler(File f) {
if (!EstFileVide(f)) {
f.Tête = (f.Tête + 1) % MAX;
} else {
printf("Erreur : File vide");
}
return f;
}
Créer une file vide, enfiler deux éléments, puis défiler un élément :
File f = CréerFileVide();
f = Enfiler(10, f);
f = Enfiler(20, f);
Type_element tête = LireFile(f); // tête vaut 10
f = Défiler(f);
tête = LireFile(f); // tête vaut 20
Une file chaînée est une liste chaînée avec deux pointeurs :
typedef struct cellule {
Type_element valeur;
struct cellule* suivant;
} Cellule;
typedef struct file {
Cellule* Tête;
Cellule* Queue;
} File;
File CréerFileVide() {
File f;
f.Tête = NULL;
f.Queue = NULL;
return f;
}
int EstFileVide(File f) {
return (f.Tête == NULL);
}
Type_element LireFile(File f) {
if (!EstFileVide(f))
return f.Tête->valeur;
else
printf("Erreur : File vide");
}
File Enfiler(Type_element e, File f) {
Cellule* NC = (Cellule*)malloc(sizeof(Cellule));
if (NC) {
NC->valeur = e;
NC->suivant = NULL;
if (!EstFileVide(f)) {
f.Queue->suivant = NC;
} else {
f.Tête = NC;
}
f.Queue = NC;
}
return f;
}
File Défiler(File f) {
if (!EstFileVide(f)) {
Cellule* NC = f.Tête;
f.Tête = f.Tête->suivant;
free(NC);
if (f.Tête == NULL)
f.Queue = NULL;
} else {
printf("Erreur : File vide");
}
return f;
}