Cours d'algorithmique : LES PILES - LA TOUR DE HANOI

MODELISATION DE LA STRUCTURE 

Introduction

Une pile est une structure qui stocke de manière ordonnée des éléments, mais rend accessible uniquement  un  seul  d'entre eux,  appelé  le  sommet  de  la  pile. Quant  on  ajoute  un  élément, celui-ci devient  le sommet de  la pile, c'est-à-dire  le seul élément accessible. Quant on retire un  élément  de  la  pile, on  retire  toujours  le  sommet,  et  le  dernier  élément  ajouté  avant lui devient alors le sommet de la pile. Pour résumer, le dernier élément ajouté dans la pile est le premier élément à en être retiré. Cette structure est également appelée une liste LIFO (Last In, First Out). 

Généralement, il y a deux façons de représenter une pile. La première s'appuie sur la structure de liste chaînée vue précédemment. La seconde manière utilise un tableau. 

Modélisation par liste chaînée

La première façon de modéliser une pile consiste à utiliser une liste chaînée en n'utilisant que les  opérations  ajouterTete  et  retirerTete. Dans  ce cas, on  s'aperçoit  que  le  dernier  élément entré  est  toujours  le  premier  élément  sorti. La  figure  suivante  représente  une  pile  par  cette modélisation. La pile contient les chaînes de caractères suivantes qui ont été ajoutées dans cet ordre: "Paris", "Marseille", "Bordeaux", "Lyon" et "Toulouse".  

 

Pour cette modélisation, la structure d'une pile est celle d'une liste chaînée. 

type PILE_LST: LISTE;

Modélisation par tableau

La deuxième manière de modéliser une pile consiste à utiliser un tableau. L'ajout d'un élément se fera à  la suite du dernier élément du  tableau. Le  retrait d'un élément de  la pile se  fera en enlevant  le  dernier  élément  du  tableau.  La  figure  suivante  représente  une  pile  par  cette modélisation. Elle reprend la même pile que pour l'exemple de modélisation par liste chaînée. 

Voici la structure de données correspondant à une pile représentée par un tableau. 

structure PILE_TAB:
 ELEMENT tab[NMAX];
 ENTIER  n;
fin structure;

NMAX est une constante représentant la taille du tableau alloué. n est le nombre d'éléments dans la pile. 

OPERATIONS SUR LA STRUCTURE 

Introduction

A partir de maintenant, nous allons employer  le  type PILE qui  représente une pile au  sens général, c'est-à-dire sans se soucier de sa modélisation. PILE représente aussi bien une pile par  liste chaînée  (PILE_LST)  qu'une  liste  par  pointeurs  (PILE_PTR). Voici les  opérations que nous allons détailler pour ces deux modélisations. 

• initialiserPile(PILE * p) 

Initialise la pile pointée par p, i.e. fait en sorte que la pile soit vide. 

• BOOLEEN <-- pileVide(PILE p) 

Indique si la pile p est vide. 

• ELEMENT  <--  sommet(PILE p) 

Retourne l'élément au sommet de la pile p. 

• BOOLEEN  <--  empilerElement(PILE * p, ELEMENT e) 

Empile l'élément e au sommet de la pile pointée par p. VRAI est retournée si l'opération a réussi. 

• BOOLEEN  <--  depilerElement(PILE * p, ELEMENT * e) 

Dépile et copie à l'adresse e l'élément au sommet de la pile pointée par p. VRAI est retournée si l'opération a réussi. 

Les prototypes de ces opérations (paramètres et  type de retour) sont les mêmes quelque soit la modélisation choisie.  

Opérations pour la modélisation par liste chaînée

Initialiser la pile 

Cette fonction initialise les valeurs de la structure représentant la pile pointée par p, afin que celle-ci  soit  vide. Dans  le  cas d'une  représentation par  liste chaînée,  il  suffit d'initialiser  la liste chaînée qui représente la pile. 

fonction initialiserPile(PILE * p):
 initialiserListe(p);
fin fonction;

Pile vide ? 

Cette fonction indique si la pile p est vide. Dans le cas d'une représentation par liste chaînée, la pile est vide si la liste qui la représente est vide. 

fonction BOOLEEN  <--  pileVide(PILE p):
 rendre listeVide(p);
fin fonction;

Sommet d'une pile

Cette fonction retourne l'élément au sommet de la pile p. Dans le cas d'une représentation par liste chaînée, cela revient à retourner la valeur de l'élément en tête de la liste. A n'utiliser que si la pile p n'est pas vide. 

          
fonction ELEMENT   <-- sommet(PILE p):
 si (non pileVide(p)) alors
  rendre teteListe(p);
 sinon
  /* Erreur */
 fin si;
fin fonction;

Empiler un élément sur une pile

         
Cette fonction empile  l'élément e au sommet de  la pile pointée par p. Pour  la représentation par  liste chaînée, cela revient à ajouter  l'élément e en  tête de  la  liste. VRAI est retournée si l'élément a bien été ajouté. 
         

fonction BOOLEEN  <--  empilerElement(PILE * p, ELEMENT e):
 rendre ajouterTete(p,e);
fin fonction;

Dépiler un élément d'une pile

              
Cette  fonction dépile  l'élément  au  sommet  de  la  pile  pointée  par  p  et  stocke  sa  valeur  à l'adresse  e.  Pour  la  représentation par  liste  chaînée,  cela  revient  à  récupérer  la  valeur  de l'élément en tête de liste avant de le supprimer de cette dernière. VRAI est retournée si la pile n'est pas déjà vide. 

            
fonction BOOLEEN  <--  depilerElement(PILE * p, ELEMENT * e):
 si (non pileVide(*p)) alors
  *e  <--  sommet(*p);
  rendre retirerTete(p);
 sinon

  rendre FAUX;
 fin si;
fin fonction; 

Opérations pour la modélisation par tableau

Initialiser la pile

  
Cette fonction initialise les valeurs de la structure représentant la pile pointée par p, afin que celle-ci soit vide. Dans le cas d'une représentation par tableau, il suffit de rendre n nul. 

      
fonction initialiserPile(PILE * p):
 p --> n  <-- 0;
fin fonction;

Pile vide ?

    
Cette  fonction  indique  si la pile p est vide. Dans  le cas d'une  représentation par  tableau,  la pile est vide si le champ n est nul. 

   
fonction BOOLEEN  <--  pileVide(PILE p):
 rendre (p.n = 0);
fin fonction;

Sommet d'une pile

        
Cette fonction retourne l'élément au sommet de la pile p. Dans le cas d'une représentation par tableau, cela revient à retourner la valeur du nième élément du tableau (i.e. l'élément d'indice n - 1). A n'utiliser que si la pile p n'est pas vide. 

        
fonction ELEMENT  <--  sommet(PILE p):
 si (non pileVide(p)) alors
  rendre (p.tab[p.n - 1]);
 sinon
  /* Erreur */
 fin si;
fin fonction;

Empiler un élément sur une pile 

         
Cette fonction empile  l'élément e au sommet de  la pile pointée par p. Pour  la représentation par  tableau, cela  revient à ajouter  l'élément e à  la  fin du  tableau. S'il  reste de  la place dans l'espace réservé au tableau, la fonction retourne VRAI. 

fonction BOOLEEN  <--  empilerElement(PILE * p, ELEMENT e):
 si (p --> n = NMAX) alors
  rendre FAUX;
 sinon
  p --> tab[p --> n]  <--  e;
  p --> n  <--  p --> n + 1;
  rendre VRAI;
 fin si;

fin fonction; 

Dépiler un élément d'une pile

  
Cette  fonction dépile  l'élément  au  sommet  de  la  pile  pointée  par  p  et  stocke  sa  valeur  à l'adresse e. Pour la représentation par tableau, cela revient à diminuer d'une unité le champ n, et  à  renvoyer  l'élément  d'indice  n du  tableau.  Si la  pile  n'est  pas  déjà  vide,  VRAI  est renvoyée. 

 
fonction BOOLEEN  <--  depilerElement(PILE * p, ELEMENT * e)
 si (non pileVide(*p)) alors
  *e  <--  sommet(*p);
  p --> n  <-- p --> n - 1;
  rendre VRAI;
 sinon
  rendre FAUX;
 fin si;
fin fonction;
  

EXEMPLE: SUPPRESSION DE LA RECURSIVITE 

  

Présentation

Une  image en informatique peut être représentée par une matrice de points m ayant XMAX colonnes et YMAX lignes. Un élément m[x][y] de la matrice représente la couleur du point p de coordonnées (x;y). On propose d'écrire  ici une fonction qui, à partir d'un point p, "étale" une couleur  c  autour  de  ce  point.  La  progression de  la  couleur  étalée  s'arrête  quand  elle rencontre une couleur autre que celle du point p. La figure suivante  illustre cet exemple, en considérent p = (3;4).  

  

On propose  ici  deux  façon d'écrire  cette  fonction.  La  première  solution  est  récursive.  La seconde  reprend  la  première en  éliminant la  récursivité  à  l'aide  d'une  pile.  Par  la  suite, COULEUR sera le type qui représente une couleur, et POINT sera la structure qui représente un point. 

     
structure POINT:
 ENTIER x;
 ENTIER y;
fin fonction; 

Implémentation récursive

La manière récursive consiste à écrire une fonction qui change la couleur d'un point p en une couleur c2 si sa couleur originale vaut c1. Dans le même temps, cette fonction s'appelle elle-même pour  les quatres points  adjacents  à p. Bien  entendu,  il  faut prendre garde de ne pas sortir des limites de la matrice.  

          

fonction remplirR(IMAGE i, POINT p, COULEUR c1, COULEUR c2):
 si (i[p.x][p.y] = c1) alors
  i[p.x][p.y]  <--  c2;
  si (p.x > 0) alors remplirR(i,(p.x - 1;p.y),c1,c2);
  si (p.x < XMAX) alors remplirR(i,(p.x + 1;p.y),c1,c2);
  si (p.y > 0) alors remplirR(i,(p.x;p.y - 1),c1,c2); 

  si (p.y < YMAX) alors remplirR(i,(p.x;p.y + 1),c1,c2);
 fin si;
fin fonction;  

Pour réaliser l'exemple présenté en introduction, la fonction récursive s'utilisera de la manière suivante.  

remplirR(m,(3;4),m[3][4],c);

Implémentation itérative (non récursive)

Quant on appelle une fonction récursivement, il y a "empilement" des appels à cette fonction. En  effet,  chaque  fois  qu'une  fonction  est lancée, on  empile  le  contexte  de  la  fonction appelante de manière à pouvoir y revenir ensuite. Lorsque la fonction se termine, on dépile le dernier contexte empilé et on reprend l'exécution de la fonction appelante.  

L'idée  ici  est  d'identifier  les  données  qui  définissent  le contexte  de  la  fonction  et  de  les empiler  de  manière explicite.  Ensuite,  itérativement,  tant  que  la  pile  n'est  pas  vide, on applique le corps de la fonction récursive sur les données dépilées du sommet de la pile. Un appel initialement  récursif  à  la  fonction  se  traduira  alors  par  l'empilement  de  nouvelles données sur la pile. 

Ici, la donnée cruciale, c'est le point de la matrice que l'on est en train de traiter. On va donc empiler  les  coordonnées  des  différents  points  traités  pour reproduire  un  comportement similaire à l'implémentation récursive qu'est la fonction remplirR. 

        
fonction remplirI(IMAGE i, POINT p, COULEUR c2):
 c1  <--  i[p.x][p.y];
 initialiserPile(&pl);
 empilerElement(&pl,p);

 tant que (non pileVide(pl)) faire
  depilerElement(&pl,&p);

  si (i[p.x][p.y] = c1) alors
   i[p.x][p.y]  <--  c2;
   si (p.x > 0) alors empilerElement(&pl,(p.x - 1;p.y)) 
   si (p.x < XMAX) alors empilerElement(&pl,(p.x + 1;p.y));
   si (p.y > 0) alors empilerElement(&pl,(p.x;p.y - 1)); 
   si (p.y < YMAX) alors empilerElement(&pl,(p.x;p.y + 1));
  fin si;
 fin tant que;
fin fonction; 

       
Pour réaliser l'exemple présenté en introduction, la fonction itérative s'utilisera de la manière suivante. 

remplirI(m,(3;4),c);

UN AUTRE EXEMPLE: LA TOUR DE HANOI  

    

Présentation

Il  s'agit d'un  jeu de  réflexion dont voici la  règle. Des anneaux de diamètres différents sont empilés sur un poteau. Un anneau peut être empilé sur un autre seulement si il a un diamètre inférieur à celui de l'anneau sur lequel il repose.  

       

Le  but  du  jeu  est  de  déplacer  les  anneaux  initialement  empilés  sur  un  seul  poteau vers un autre en respectant les règles et en n'utilisant qu'un seul poteau intermédiaire.  

 

 

Solution

 

Les poteaux sont représentés par des piles d'entiers numérotées 0, 1 et 2. Le  jeu entier sera alors représenté par un tableau t de trois piles. On suppose qu'il y a n anneaux dans le jeu. On attribue  à  chaque  anneau un numéro de manière  à  ce  que  si l'anneau  a  est  plus  petit  que l'anneau b, alors son numéro est plus petit. Au départ, on aura donc: 

 

Voici maintenant la fonction qui réalise le déplacement des anneaux du poteau numéro a au poteau numéro b (on déduit le numéro du poteau intermédiaire c par la formule c = 3 - a - b).

       
Cette  fonction  est  récursive.  S'il  y  a  un  seul  anneau, on  le  déplace  directement,  sinon on déplace les n - 1 premiers anneaux sur le poteau intermédiaire c (appel récursif à la fonction) et le dernier anneau sur le poteau final b (appel récursif à la fonction). Ensuite, on déplace les anneaux du poteau  intermédiaire c sur  le poteau final a (appel récursif à  la fonction). Voici une illustration.  

Et voici maintenant le détail de la fonction qui déplace les anneaux.  

     

fonction deplacerAnneaux(PILE * t, ENTIER n,
                                             ENTIER a, ENTIER b):       
 si (n = 1) alors
  depilerElement(&t[a],&e);
  empilerElement(&t[b],e);
 sinon
  c  <--  3 - a - b; /* Un moyen de trouver le numero du
                     poteau intermediaire. */
  deplacerAnneaux(t,n - 1,a,c);
  deplacerAnneaux(t,1,a,b);
  deplacerAnneaux(t,n - 1,c,b);
 fin si;
fin fonction; 

  c   3 - a - b; /* Un moyen de trouver le numero du
                     poteau intermediaire. */
  deplacerAnneaux(t,n - 1,a,c);
  deplacerAnneaux(t,1,a,b);
  deplacerAnneaux(t,n - 1,c,b);
 fin si;
fin fonction;

CONCLUSION 

Comme  la  pile  ne  permet l'accès  qu'à  un  seul  de  ses  éléments,  son usage est limité. Cependant, elle peut être très utile pour supprimer la récursivité d'une fonction comme nous l'avons  vu précédemment.  La  différence  entre  la  modélisation  par  liste chaînée  et la modélisation par tableau est très faible. L'inconvénient du tableau est que sa taille est fixée à l'avance,  contrairement  à  la  liste chaînée  qui  n'est limitée  que  par  la  taille  de  la mémoire centrale de  l'ordinateur. En contrepartie,  la  liste chaînée effectue une allocation dynamique de  mémoire  à  chaque  ajout  d'élément  et  une  libération de  mémoire  à  chaque  retrait  du sommet de la pile. En résumé, la modélisation par liste chaînée sera un peu plus  lente, mais plus souple quant à sa taille. 

    

------------------------------------------------------------------------------------------------------
 <<< CHAPITRE II : LES LISTE CHAINEES

            >>> CHAPITRE IV : FILES D'ATTENTE