Cours sur les Piles et les Files

Ce laboratoire porte sur les structures de données avancées que sont les piles et les files. Il permet d’apprendre leur définition, leur mode de fonctionnement, ainsi que leur implémentation en mémoire, tant en représentation contiguë qu’en représentation chaînée. Le travail pratique propose de manipuler ces structures, de comprendre leurs opérations fondamentales, et de comparer leurs usages. Pour réaliser ce TP, il est nécessaire de maîtriser les bases du langage C, notamment la gestion des tableaux, des pointeurs, et la manipulation dynamique de la mémoire.

Objectifs

• Comprendre le fonctionnement des piles (LIFO) et des files (FIFO).
• Implémenter une pile et une file en représentation contiguë (tableau) et chaînée (liste).
• Maîtriser les opérations fondamentales : création, test de vide/plein, accès, insertion et suppression.
• Appréhender les avantages et limites des deux modes de représentation.
• Écrire un programme comparant le contenu d’une pile et d’une file.

Prérequis et installation

• Connaissances en langage C : structures, tableaux, pointeurs, allocation dynamique.
• Environnement de développement C avec un compilateur compatible (gcc, clang, etc.).
• Accès à un éditeur de texte et un terminal pour compiler et exécuter les programmes.

Implémentation d’une pile en représentation contiguë

Dans cette étape, vous allez créer une pile utilisant un tableau de taille fixe MAX (ici 100). La pile est gérée par un indice sommet qui indique la première case libre du tableau.

Commencez par définir la structure :

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

Implémentez ensuite les opérations suivantes :

• Création d’une pile vide :

Pile CreerPileVide() {
  Pile P;
  P.sommet = 0;
  return P;
}

• Test pile vide :

int EstPileVide(Pile P) {
  return (P.sommet == 0);
}

• Test pile pleine :

int EstPilePleine(Pile P) {
  return (P.sommet == MAX);
}

• Accès à la tête de la pile :

Type_element tete(Pile P) {
  if (!EstPileVide(P))
    return P.Tableau[P.sommet - 1];
  else
    printf("Erreur : Pile vide\n");
}

• Empiler un élément :

Pile Empiler(Pile P, Type_element e) {
  if (!EstPilePleine(P)) {
    P.Tableau[P.sommet] = e;
    P.sommet++;
  } else {
    printf("Erreur : Pile pleine\n");
  }
  return P;
}

Dépiler un élément :

Pile Depiler(Pile P) {
  if (!EstPileVide(P)) {
    P.sommet--;
  } else {
    printf("Erreur : Pile vide\n");
  }
  return P;
}

Cette étape vous permet de comprendre la gestion d’une pile dans un tableau fixe, ainsi que les risques liés aux débordements (pile pleine) et sous-débordements (pile vide).

Implémentation d’une pile en représentation chaînée

Cette étape consiste à implémenter la pile sous forme d’une liste chaînée, où chaque cellule contient une valeur et un pointeur vers l’élément suivant. Le sommet de la pile est représenté par un pointeur vers la première cellule.

Définissez la structure :

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

typedef Cellule* Pile;

Implémentez les opérations :

• Création d’une pile vide :

Pile CreerPileVide() {
  Pile P = NULL;
  return P;
}

• Test pile vide :

int EstPileVide(Pile P) {
  return (P == NULL);
}

• Accès à la tête :

Type_element tete(Pile P) {
  if (!EstPileVide(P))
    return P->Val;
  else
    printf("Erreur : Pile vide\n");
}

• Empiler un élément :

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\n");
  }
  return P;
}

• Dépiler un élément :

Pile Depiler(Pile P) {
  if (!EstPileVide(P)) {
    Cellule *NC = P;
    P = P->succ;
    free(NC);
  } else {
    printf("Erreur : Pile vide\n");
  }
  return P;
}

Cette représentation permet d’éviter les problèmes de taille fixe, mais nécessite une gestion dynamique de la mémoire.

Implémentation d’une file en représentation contiguë circulaire

La file est une structure où l’ajout se fait en fin (queue) et la suppression en début (tête). Pour éviter les décalages coûteux, la représentation circulaire utilise un tableau et les indices sont gérés modulo MAX.

Définissez la structure :

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

Implémentez les opérations :

• Création d’une file vide :

File CreerFileVide() {
  File f;
  f.Tete = 0;
  f.Queue = 0;
  return f;
}

• Test file vide :

int EstFileVide(File f) {
  return (f.Tete == f.Queue);
}

• Test file pleine :

int EstFilePleine(File f) {
  return ((f.Queue + 1) % MAX == f.Tete);
}

• Accès à l’élément en tête :

Type_element LireFile(File f) {
  if (!EstFileVide(f))
    return f.Tab[f.Tete];
  else
    printf("Erreur : File vide\n");
}

• Enfiler un élément :

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\n");
  }
  return f;
}

• Défiler un élément :

File Defiler(File f) {
  if (!EstFileVide(f)) {
    f.Tete = (f.Tete + 1) % MAX;
  } else {
    printf("Erreur : File vide\n");
  }
  return f;
}

Cette méthode optimise l’utilisation de l’espace mémoire et évite les décalages.

Implémentation d’une file en représentation chaînée

La file est ici implémentée par une liste chaînée avec deux pointeurs : Tête (début) et Queue (fin). Cela facilite l’ajout en fin sans parcourir toute la liste.

Définissez la structure :

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

typedef struct file {
  Cellule *Tete;
  Cellule *Queue;
} File;

Implémentez les opérations :

• Création d’une file vide :

File CreerFileVide() {
  File f;
  f.Tete = NULL;
  f.Queue = NULL;
  return f;
}

• Test file vide :

int EstFileVide(File f) {
  return (f.Tete == NULL);
}

• Accès à l’élément en tête :

Type_element LireFile(File f) {
  if (!EstFileVide(f))
    return f.Tete->valeur;
  else
    printf("Erreur : File vide\n");
}

• Enfiler un élément :

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.Tete = NC;
    }
    f.Queue = NC;
  } else {
    printf("Erreur : mémoire insuffisante\n");
  }
  return f;
}

• Défiler un élément :

File Defiler(File f) {
  if (!EstFileVide(f)) {
    Cellule *NC = f.Tete;
    f.Tete = f.Tete->suivant;
    free(NC);
    if (f.Tete == NULL) {
      f.Queue = NULL;
    }
  } else {
    printf("Erreur : File vide\n");
  }
  return f;
}

Cette représentation est très flexible, permettant une taille dynamique, mais nécessite une gestion attentive de la mémoire.

Résultats attendus

• Les piles et files créées doivent se comporter conformément aux principes LIFO et FIFO respectivement.
• Les tests de pile/file vide et pleine doivent retourner les valeurs correctes selon l’état de la structure.
• Les opérations d’empilement/enfilage et de dépilement/défilement doivent modifier correctement la structure sans erreurs.
• Les erreurs doivent être signalées clairement, par exemple lors d’un empilement sur une pile pleine ou un dépilement sur une pile vide.
• La gestion mémoire dans les versions chaînées doit éviter les fuites et les accès invalides.
• Le programme de comparaison entre pile et file doit retourner vrai si les éléments sont identiques dans l’ordre inverse (pile du sommet vers la base, file de la tête vers la queue), sinon faux.

Pièges courants

• Confondre les indices sommet, tête et queue dans les représentations contiguës, ce qui peut provoquer des erreurs d’accès mémoire.
• Oublier de vérifier les conditions de pile/file pleine ou vide avant d’effectuer des opérations.
• Dans la représentation circulaire, ne pas utiliser le modulo MAX lors de l’incrémentation des indices.
• En représentation chaînée, mal gérer l’allocation ou la libération de mémoire, causant des fuites ou des erreurs de segmentation.
• Lors de l’enfilement dans une file chaînée vide, ne pas mettre à jour correctement les deux pointeurs Tête et Queue.
• Dans le programme de comparaison pile-file, ne pas respecter l’ordre des éléments lors de la comparaison.