Cours sur les Piles et les Files

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.

Les Piles (Stacks)

Définition

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 :

• Empiler : ajouter un élément au sommet de la pile.
• Dépiler : retirer l’élément au sommet de la pile.

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.

Implémentation contiguë

La pile est représentée par une structure contenant :

• un tableau de taille maximale MAX,
• un entier sommet indiquant la première case libre (indice).

#define MAX 100
typedef struct pile {
  Type_element Tableau[MAX];
  int sommet; // indice de la première case libre, entre 0 et MAX
} Pile;

Opérations sur la pile contiguë

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;
}

Exemple d’utilisation

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

Implémentation chaînée

Une pile chaînée est une succession de cellules où chaque cellule contient :

• une valeur,
• un pointeur vers la cellule suivante.

Le pointeur P représente le sommet de la pile.

typedef struct cellule {
  Type_element Val;
  struct cellule* succ;
} Cellule;

typedef Cellule* Pile;

Opérations sur la pile chaînée

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;
}

Les Files (Queues)

Définition

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 :

• ajout en fin (enfiler),
• retrait au début (défiler),
• accès à l’élément en tête de file.

Implémentation contiguë linéaire

Utiliser un tableau linéaire pour une file nécessite de décaler tous les éléments à chaque suppression, ce qui est inefficace.

Implémentation contiguë circulaire

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.

• Si Tête = Queue, la file est vide.
• Si (Queue + 1) modulo MAX = Tête, la file est pleine.

Définition du type File contiguë

#define MAX 100
typedef struct file {
  Type_element Tab[MAX];
  int Tête;
  int Queue;
} File;

Opérations sur la file contiguë

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;
}

Exemple d’utilisation

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

Implémentation chaînée

Une file chaînée est une liste chaînée avec deux pointeurs :

• Tête : pointeur vers la cellule en début de file,
• Queue : pointeur vers la cellule en fin de file.

typedef struct cellule {
  Type_element valeur;
  struct cellule* suivant;
} Cellule;

typedef struct file {
  Cellule* Tête;
  Cellule* Queue;
} File;

Opérations sur la file chaînée

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;
}

Glossaire des termes clés

• Pile (Stack) : structure de données suivant le principe LIFO, où le dernier élément ajouté est le premier retiré.
• Sommet : élément en haut de la pile, dernier ajouté.
• Empiler : opération d’ajout d’un élément au sommet de la pile.
• Dépiler : opération de suppression de l’élément au sommet de la pile.
• File (Queue) : structure de données suivant le principe FIFO, où le premier élément ajouté est le premier retiré.
• Enfiler : opération d’ajout d’un élément en fin de file.
• Défiler : opération de suppression de l’élément en tête de file.
• Représentation contiguë : implémentation utilisant un tableau fixe.
• Représentation chaînée : implémentation utilisant des listes chaînées dynamiques.
• Tableau circulaire : tableau où les indices sont calculés modulo la taille maximale pour optimiser l’utilisation de l’espace.
• LIFO : Last In, First Out, principe des piles.
• FIFO : First In, First Out, principe des files.

Points clés à retenir

• Les piles fonctionnent selon le principe LIFO, les files selon le principe FIFO.
• Les opérations principales sont empiler/dépiler pour les piles, enfiler/défiler pour les files.
• Les piles et files peuvent être implémentées soit par tableaux (contiguë), soit par listes chaînées (chaînée).
• L’implémentation contiguë impose une taille maximale, la chaînée est dynamique mais utilise plus de mémoire.
• Les tableaux circulaires optimisent l’utilisation de l’espace mémoire pour les files.
• Les piles permettent de transformer des algorithmes récursifs en itératifs, améliorant ainsi les performances.
• Les files sont largement utilisées dans la gestion des événements et les systèmes d’exploitation.