Chapitre IV - Les piles

Ce matériel couvre les piles, une structure de données fondamentale en informatique, en présentant leur définition, leur spécification, leur implémentation en représentation chaînée et contiguë, ainsi que des exemples d’utilisation. Il s’adresse aux étudiants en informatique ou en programmation souhaitant comprendre et manipuler les piles en langage C.

Définition d’une pile

Une pile (en anglais stack) est une structure de données basée sur le principe « dernier arrivé, premier sorti » (LIFO pour Last In, First Out). Cela signifie que le dernier élément ajouté à la pile sera le premier à être utilisé. Cette organisation est comparable à une pile d’assiettes : on empile les assiettes les unes sur les autres, et on les récupère dans l’ordre inverse, en commençant par la dernière ajoutée.

Une pile peut être implémentée de manière similaire à une liste chaînée. En représentation chaînée, une pile est un pointeur vers la cellule sommet de la pile, ou NULL si la pile est vide. Chaque cellule contient une information ainsi que l’adresse de la cellule suivante. La dernière cellule (la première ajoutée) pointe vers NULL.

Les opérations standard sur une pile sont :

• création : creer_pile
• consultation : vide_pile (vérifier si la pile est vide), sommet_pile (accéder à l’élément au sommet)
• modification : empiler (push, ajouter un élément), depiler (pop, retirer l’élément au sommet)

Spécification d’une pile chaînée : fichier pile.h

/* fichier pile.h */
typedef int element;

typedef struct cellule{
  element information;
  struct cellule * suivant;
} cellule;

typedef struct cellule * pile;

void creer_pile(pile*);
element sommet_pile(pile); /* sommet d’une pile non vide */
int vide_pile(pile);
void empiler_pile(pile* , element);
void depiler_pile(pile*); /* supprime le sommet d’une pile non vide */

Implémentation d’une pile chaînée : fichier pile.c

Voici l’implémentation des fonctions de gestion d’une pile chaînée en C :

/* fichier pile.c */
#include "pile.h"
#include <stdlib.h>

void creer_pile(pile* p){
  *p = NULL;
}

element sommet_pile(pile p){
  return p->information;
}

int vide_pile(pile p){
  return p == NULL;
}

void empiler_pile(pile* p , element e){
  cellule* n;
  n = (cellule*)malloc(sizeof(cellule));
  n->information = e;
  n->suivant = *p;
  *p = n;
}

void depiler_pile(pile* p){
  cellule* n = *p;
  *p = (*p)->suivant;
  free(n);
}

Explication

• creer_pile initialise la pile à NULL, indiquant qu’elle est vide.
• sommet_pile retourne l’information contenue dans la cellule au sommet.
• vide_pile teste si la pile est vide en vérifiant si le pointeur est NULL.
• empiler_pile crée une nouvelle cellule, y stocke l’élément, la lie au sommet actuel, puis met à jour le sommet.
• depiler_pile supprime la cellule au sommet et libère sa mémoire.

Exemple d’utilisation d’une pile chaînée

Le programme suivant crée une pile, y empile les entiers de 0 à 4, puis dépile et affiche chaque élément :

/* fichier main.c */
#include <stdio.h>
#include "pile.h"

void main() {
  pile p1;
  int i;

  creer_pile(&p1);
  for(i = 0 ; i < 5 ; i++)
    empiler_pile(&p1 , i);

  while(!vide_pile(p1)){
    printf("%d\t", sommet_pile(p1));
    depiler_pile(&p1);
  }
}

Résultat de l’exécution :

4 3 2 1 0

Pile en représentation contiguë (tableau)

Une autre manière d’implémenter une pile est d’utiliser un tableau fixe, appelé représentation contiguë. La pile est alors un tableau d’éléments avec un indice indiquant la position du sommet.

Spécification : fichier pile_contig.h

/* fichier pile_contig.h */
#define taille_max 100

typedef int element;
typedef struct pile{
  element information[taille_max];
  int sommet;
} pile;

void creer_pile(pile*);
int vide_pile(pile);
element sommet_pile(pile);
void depiler(pile*);
void empiler(pile* , element);

Implémentation : fichier pile_contig.c

#include "pile_contig.h"

void creer_pile(pile * p){
  p->sommet = -1;
}

int vide_pile(pile p){
  return p.sommet == -1;
}

element sommet_pile(pile p){
  return p.information[p.sommet];
}

void depiler(pile * p){
  p->sommet--;
}

void empiler(pile * p , element e){
  if(p->sommet < taille_max-1){
    p->sommet++;
    p->information[p->sommet] = e;
  }
}

Explication

• La pile est initialisée avec sommet = -1 pour indiquer qu’elle est vide.
• vide_pile teste si sommet == -1.
• sommet_pile retourne l’élément à l’indice sommet du tableau.
• depiler décrémente l’indice sommet, retirant ainsi l’élément du sommet.
• empiler incrémente sommet puis stocke l’élément à cette position, si la pile n’est pas pleine.

Exemple d’utilisation d’une pile contiguë

/* fichier main.c */
#include <stdio.h>
#include "pile_contig.h"

void main() {
  pile p1;

  creer_pile(&p1);
  empiler(&p1 , 0);
  empiler(&p1 , 1);
  empiler(&p1 , 2);
  empiler(&p1 , 3);
  empiler(&p1 , 4);

  while(!vide_pile(p1)){
    printf("%d\t", sommet_pile(p1));
    depiler(&p1);
  }
}

Résultat de l’exécution :

4 3 2 1 0

Glossaire des termes clés

• Pile (stack) : structure de données LIFO où le dernier élément ajouté est le premier retiré.
• Empiler (push) : opération d’ajout d’un élément au sommet de la pile.
• Dépiler (pop) : opération de retrait de l’élément au sommet de la pile.
• Sommet de la pile : élément actuellement au sommet, accessible en priorité.
• Représentation chaînée : implémentation d’une pile avec des cellules liées par des pointeurs.
• Représentation contiguë : implémentation d’une pile avec un tableau et un indice sommet.
• NULL : valeur indiquant l’absence d’un pointeur valide, utilisée pour marquer la fin d’une pile chaînée vide.

Points clés à retenir

• La pile fonctionne selon le principe LIFO : dernier arrivé, premier sorti.
• Elle peut être implémentée en liste chaînée ou en tableau contigu.
• Les opérations principales sont la création, l’empilement, le dépilement, la consultation du sommet et la vérification de la pile vide.
• En représentation chaînée, chaque cellule contient une information et un pointeur vers la cellule suivante.
• En représentation contiguë, la pile est un tableau avec un indice indiquant la position du sommet.
• Les exemples en C montrent comment manipuler ces structures et afficher leur contenu.