Les Piles & Les Files

Cette conférence porte sur les structures de données fondamentales que sont les piles et les files, en particulier leur définition, leurs opérations principales, ainsi que leurs deux principales formes d’implémentation : contiguë (tableaux) et chaînée (listes chaînées). Elle s’inscrit dans un cours d’informatique consacré aux structures de données dynamiques et à l’abstraction des types de données.

Rappels sur les structures dynamiques et récursives

Une structure dynamique est une structure dont la taille peut varier pendant l’exécution d’un programme. On distingue deux grandes catégories :

• Les structures non récursives, comme les files.
• Les structures récursives, qui se définissent par une référence à elles-mêmes, telles que les listes, piles et files.

Les structures récursives peuvent être linéaires, avec une seule référence (comme les listes chaînées), ou non linéaires, avec plusieurs références. Ces références sont généralement gérées à l’aide de pointeurs.

Concept d’abstraction et type abstrait de données

Lorsqu’on utilise une structure de données, l’essentiel est de connaître les opérations possibles sur ces données, sans se soucier de leur implémentation interne. Cette idée est formalisée par le concept de type abstrait de données (TAD), qui décrit :

• Le type de données pouvant être stocké.
• Les opérations possibles sur ces données.
• Les conditions d’erreur associées à ces opérations.

Les piles : définition et opérations principales

Une pile est une structure qui stocke des objets arbitraires selon le principe « dernier arrivé, premier servi » (LIFO). Les opérations fondamentales sont :

• empiler(objet) : insère un objet au sommet de la pile.
• dépiler() : retire et retourne l’objet au sommet de la pile.

On distingue aussi des opérations auxiliaires :

• sommet() : retourne l’objet au sommet sans le retirer.
• taille() : retourne le nombre d’objets dans la pile.
• pileVide() : indique si la pile est vide.
• pilePleine() : indique si la pile est pleine (dans le cas d’une représentation contiguë).

Deux types d’implémentation sont possibles : contiguë (tableaux) et chaînée (listes chaînées).

Implémentation contiguë des piles avec tableaux

On définit un type élément selon le problème, puis un tableau Tab de taille MAX pour contenir les éléments. La pile est représentée par une structure contenant :

• corps : le tableau Tab
• taille : un entier indiquant le nombre d’éléments présents

Les principales procédures et fonctions sont :

procédure créerPile(var p : Pile)
  p.taille ← 0
Fin procédure

fonction pileVide(p : Pile) : Booléen
  pileVide ← (p.taille = 0)
Fin fonction

fonction pilePleine(p : Pile) : Booléen
  pilePleine ← (p.taille = MAX)
Fin fonction

fonction sommet(p : Pile) : Élément
  Si pileVide(p) Alors
    Erreur
  Sinon
    retourner p.corps[p.taille]
  Fin Si
Fin fonction

procédure empiler(e : Élément, var p : Pile)
  Si (p.taille < MAX) Alors
    p.taille ← p.taille + 1
    p.corps[p.taille] ← e
  Sinon
    Erreur // possibilité de réallocation du tableau
  Fin Si
Fin procédure

fonction dépiler(var p : Pile) : Élément
  Si pileVide(p) Alors
    Erreur
  Sinon
    p.taille ← p.taille - 1
    dépiler ← p.corps[p.taille + 1]
  Fin Si
Fin fonction

Implémentation chaînée des piles avec listes chaînées

On définit un type Élément selon le problème, puis un pointeur PtrM vers un maillon structuré ainsi :

Champ	Type
valeur	Élément
next	PtrM (pointeur vers le maillon suivant)

Les opérations principales sont :

procédure créerPile(var Pile : PtrM)
  Pile ← Nil
Fin procédure

fonction pileVide(Pile : PtrM) : Booléen
  pileVide ← (Pile = Nil)
Fin fonction

Pour connaître la taille de la pile :

fonction taille(Pile : PtrM) : entier
  Variables
    p : PtrM
    n : entier
  Début
    p ← Pile
    n ← 0
    Si pileVide(Pile) = Faux Alors
      n ← 1
      Tant que p.next ≠ Nil Faire
        n ← n + 1
        p ← p.next
      Fin Tant que
    Fin Si
    taille ← n
  Fin fonction

Pour rechercher un maillon à une position donnée :

fonction Recherche(Pile : PtrM, pos : entier) : PtrM
  Variables
    p : PtrM, n : entier
  Début
    p ← Pile ; pred ← Nil ; n ← 0
    Si pileVide(p) Alors
      Recherche ← Nil
    Sinon
      Tant que p.next ≠ Nil et n ≠ pos Faire
        n ← n + 1
        pred ← p
        p ← p.next
      Fin Tant que
      Si p = Nil Alors
        Recherche ← Nil
      Sinon
        Recherche ← pred
      Fin Si
    Fin Si
  Fin fonction

Pour obtenir la valeur au sommet :

fonction ValSommet(Pile : PtrM) : Élément
  Variables
    p : PtrM
  Début
    Si pileVide(Pile) Alors
      Erreur
    Sinon
      p ← Recherche(Pile, taille(Pile))
      ValSommet ← p.valeur
    Fin Si
  Fin fonction

Pour empiler un élément :

procédure Empiler(var Pile : PtrM, x : Élément)
  Variables
    p, pt : PtrM
  Début
    p ← réserver(tailleDe(Maillon))
    p.valeur ← x
    p.next ← Nil
    Si Pile = Nil Alors
      Pile ← p
    Sinon
      pt ← Recherche(Pile, taille(Pile))
      pt.next ← p
    Fin Si
  Fin procédure

Pour dépiler un élément :

procédure Dépiler(var Pile : PtrM)
  Variables
    p, pred : PtrM
  Début
    Si pileVide(Pile) Alors
      Erreur
    Sinon
      pred ← Recherche(Pile, taille(Pile) - 1)
      Si pred = Nil Alors
        p ← Pile
        Pile ← Nil
      Sinon
        p ← pred.next
        pred.next ← Nil
      Fin Si
      Libérer(p)
    Fin Si
  Fin procédure

Application : remplissage d’une zone d’une image

Une image informatique peut être représentée par une matrice de points, avec M colonnes et N lignes. Chaque élément Image[x, y] correspond à la couleur du point de coordonnées (x, y). Le problème consiste à étaler une couleur c à partir d’un point p donné, en remplaçant la couleur initiale du point p par c, puis en étendant cette couleur dans toutes les directions tant que la couleur rencontrée est la même que celle du point p.

Cette opération s’apparente à un parcours d’arbre où chaque nœud a quatre fils (les quatre directions possibles). Pour résoudre ce problème, on utilise une pile afin de gérer les points à traiter successivement, ce qui permet de contrôler l’ordre d’exploration et d’arrêter la propagation lorsque la couleur diffère.

Points clés

• Une pile est une structure de données dynamique de type LIFO avec des opérations d’empilement et de dépilement.
• Les piles peuvent être implémentées par tableaux (représentation contiguë) ou par listes chaînées (représentation chaînée).
• Le type abstrait de données (TAD) décrit les opérations possibles sans révéler l’implémentation.
• Les opérations auxiliaires permettent de connaître le sommet, la taille, et l’état (vide ou pleine) de la pile.
• La représentation chaînée utilise des maillons avec un champ valeur et un pointeur vers le maillon suivant.
• La gestion d’une pile chaînée nécessite des fonctions pour créer la pile, vérifier si elle est vide, empiler, dépiler, et accéder au sommet.
• Une application pratique des piles est le remplissage d’une zone d’image, en utilisant une pile pour gérer les points à colorier selon une condition de couleur.