Cours d'algorithmique : LES PILES - LA TOUR DE HANOI | Examens, Exercices, Astuces tous ce que vous Voulez

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