Cours sur les Piles et les Files

Ce cours couvre les structures de données avancées que sont les piles et les files, destinées aux étudiants en informatique. Il présente leurs définitions, modes d’implémentation contigus et chaînés, ainsi que les opérations fondamentales associées. Ce contenu est essentiel pour comprendre la gestion efficace des données en attente de traitement dans divers contextes informatiques.

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 sont possibles qu’au niveau du sommet de la pile. Le sommet est le dernier élément ajouté. La pile suit le principe LIFO (Last-In, First-Out) : le dernier élément entré est le premier sorti.

Les opérations principales sont :

• Empiler : ajouter un élément au sommet, aussi appelé insertion.
• Dépiler : retirer l’élément au sommet, aussi appelé suppression.

La gestion des débordements (pile pleine) et des sous-dépilements (pile vide) est essentielle, notamment dans une implémentation par tableau.

Implémentation contiguë

La pile est représentée par un tableau de taille maximale MAX et un indice sommet indiquant la première case libre.

#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éons une pile vide, empilons les éléments 5, puis 10, puis dépilons un élément :

Pile P = CréerPileVide();
P = Empiler(P, 5);   // P.sommet = 1, sommet = 5
P = Empiler(P, 10);  // P.sommet = 2, sommet = 10
P = Depiler(P);      // P.sommet = 1, sommet = 5

Implémentation chaînée

Une pile chaînée est une succession de cellules, chaque cellule contenant :

• un champ pour l’information (valeur),
• un pointeur vers l’élément suivant.

Le sommet de la pile est représenté par un pointeur vers la première cellule.

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 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 arrivé est le premier servi.

Les opérations autorisées sont :

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

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. Un tableau de capacité MAX 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.

Exemple : capacité MAX = 8, éléments effectifs = 7, Tête = 5, Queue = 4. Après 7 défils successifs, Tête = (5 + 7) mod 8 = 4 = Queue, la file est vide.

Définition contiguë du type File

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

Implémentation chaînée

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

• Tête : pointeur vers la cellule en tête de file (premier élément),
• Queue : pointeur vers la cellule en fin de file (dernier élément).

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 LIFO où l’ajout et la suppression se font au sommet.
• Sommet : dernier élément ajouté dans une pile.
• Empiler : opération d’ajout d’un élément au sommet d’une pile.
• Dépiler : opération de suppression de l’élément au sommet d’une pile.
• File (Queue) : structure de données FIFO où l’ajout se fait en fin et la suppression en tête.
• Tête : premier élément d’une file, celui qui sera retiré en premier.
• Queue : dernier élément d’une file, où s’ajoutent les nouveaux éléments.
• Représentation contiguë : implémentation utilisant un tableau fixe.
• Représentation chaînée : implémentation utilisant des cellules liées par des pointeurs.
• LIFO : principe "Last In, First Out" des piles.
• FIFO : principe "First In, First Out" des files.
• Tableau circulaire : tableau où les indices sont calculés modulo la taille pour optimiser l’utilisation.

Points clés à retenir

• Les piles suivent le principe LIFO, les files suivent le principe FIFO.
• Les opérations principales sont l’ajout, la suppression et l’accès à l’élément en sommet (pile) ou en tête (file).
• Les piles et files peuvent être implémentées par tableaux (contiguë) ou listes chaînées (chaînée).
• L’implémentation contiguë est limitée par la taille fixe du tableau, mais offre une complexité optimale.
• L’implémentation chaînée est plus flexible en mémoire mais nécessite une gestion plus lourde des pointeurs.
• Les piles sont utiles pour transformer des algorithmes récursifs en itératifs et pour l’évaluation d’expressions arithmétiques.
• Les files sont largement utilisées dans la gestion des événements et les systèmes d’exploitation.
• Le choix entre représentation contiguë et chaînée dépend des contraintes mémoire et des besoins de l’application.