Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
En pratique : Algorithmes et structures de données - Les piles
(Article écrit par Lucien Turski-Marcon et Bruno Bailluet et extrait d'Amiga News Tech - février 1992)
|
|
Définition : une pile est une structure de données dans laquelle il n'est possible d'ajouter ou de retirer
un élément que par son sommet (méthode dite LIFO : Last In First Out).
Si vous avez bien compris cette petite définition, alors les piles n'auront plus aucun secret pour vous...
Elles sont le plus souvent représentées par un tableau, mais comme nous maîtrisons maintenant les
listes chaînées, nous allons étudier les deux cas.
Primitives pour les tableaux
Les deux premières primitives (en pseudo-code) que nous vous proposons, permettent de tester l'état de la
pile, à savoir si elle est pleine ou au contraire vide.
Ces deux fonctions permettent de savoir si nous dépassons les limites du tableau. "Taille_Pile"
est le plus souvent une constante qui détermine le nombre de cases du tableau. Quant à "Limite_Inférieure",
il s'agit comme son nom l'indique de la borne inférieure du tableau. Ainsi, nous pouvons parfaitement
n'utiliser qu'un seul grand tableau que nous partagerons en plusieurs piles.
La procédure "Empile" ajoute l'élément qu'elle a reçu en paramètre après avoir testé l'état de la pile (pleine ?)
et incrémenté le sommet. Le retrait d'un élément de la pile se fait après avoir testé l'état de la pile (vide ?)
et avant de décrémenter le sommet.
Nous aurions pu choisir une autre méthode pour empiler, qui consiste à mettre la valeur dans le tableau avant
d'augmenter le sommet. De ce fait, il aurait fallu être cohérent avec soi-même en modifiant en conséquence les
autres fonctions, ainsi que les différentes bornes (essayez pour voir, c'est un bon exercice).
Primitives pour les listes chaînées
Comme vous avez pu le constater, si l'on représente une pile sous forme de tableau, il est nécessaire d'avoir
une variable (appelée sommet) indiquant l'indice du dernier élément de la pile. Par contre, si l'on utilise
une liste chaînée, cette variable devient inutile. Pourquoi ?
Créons un noeud vide que nous appelons "DEBUT" et qui est le point de départ de notre liste. Puis, à chaque fois
qu'un élément devra être empilé, il sera inséré entre "DEBUT" et d'éventuels autres éléments précédemment empilés.
La variable indiquant le sommet de la pile devient inutile puisque nous savons toujours où se trouve le dernier
élément empilé. Il en est de même pour dépiler : nous prennons le noeud qui suit "DEBUT". Une liste simplement
chaînée suffit amplement, car nous ne la parcourerons pas. Nous n'avons donc pas besoin de conserver la trace
du noeud précédent (intérêt de la liste double).
Pour empiler, il suffit d'insérer le nouveau noeud après "DEBUT". Nous devons donc affecter à "nouveau.suivant"
l'adresse du noeud qui suit "DEBUT" (cette adresse se trouve dans "DEBUT.suivant"). Ensuite, nous affectons
à "DEBUT.suivant" l'adresse du nouveau noeud (ce dernier devient donc le successeur immédiat du noeud "DEBUT").
Ces deux étapes doivent se faire dans cet ordre sous peine de perdre le contenu de "DEBUT.suivant".
Le test "Pile_Pleine" se fait au moment de l'allocation mémoire du nouveau noeud. Si celle-ci échoue, on
considère la pile pleine.
Si la pile n'est pas vide, nous repérons l'adresse de l'élément à dépiler (ceci nous est très facile puisqu'il
s'agit toujours du successeur de "DEBUT"). Puis nous sauvegardons sa valeur dans une variable intermédiaire
(variable valeur dans notre primitive). Enfin, pour le supprimer de la liste, nous le court-circuitons en
faisant pointer "DEBUT.suivant" sur le successeur du noeud à dépiler (il s'agit de "noeud_temp.suivant").
Si "DEBUT.suivant" est égal à NIL, la liste ne contient aucun élément hormis le premier noeud "DEBUT"
qui ne contient pas d'information pertinente.
Pratique
Pour se familiariser avec la pile, nous vous proposons ce mois-ci un petit programme permettant
l'évaluation d'une expression parenthésée. Cependant, quelques contraintes sont imposées :
- Un membre se compose de deux opérandes séparés par un signe.
- Tout membre doit être mis entre parenthèses.
- Les opérandes peuvent être des membres.
Ainsi, on entrera ((a+b)*c) et non (a+b)*c.
|
