STRUCTURES SÉQUENTIELLES 3 COMPLEXES

PILES

Pour beaucoup d’applications, les seules opérations à effectuer sur les listes sont des insertions et des suppressions aux extrémités. Dans les piles les insertions et les suppressions se font à une seule extrémité, appelée sommet de pile. Les piles sont aussi appelées LIFO, pour Last-In-First-Out, c’est-à-dire dernier entré, premier sorti ; une bonne image pour représenter une pile est une … pile d’assiettes : c’est en haut de la pile qu’il faut prendre ou mettre une assiette ! Les opérations sur les piles sont : tester si une pile est vide, accéder au sommet d’une pile, empiler un élément, retirer l’élément qui se trouve au sommet (dépiler). On peut utiliser pour implémenter les piles toutes les représentations possibles pour les listes. On va parler en détail d’une représentation chaînée, mais il faut comprendre que la représentation contiguë est tout à fait possible. 

Représentation contiguë des piles

Les éléments de la pile sont rangés dans un tableau, et l’on conserve aussi l’indice du sommet de pile. Définition d’une structure de pile réalisée avec un tableau Pseudo code formel STRUCTURE tStack content : T[n] top : entier Implantation C typedef struct tStack { content[n]; int top; } tStack; • Structures séquentielles complexes La pile vide est représentée par tout enregistrement dont le champ top contient –1, car ce champ représente l’indice de la dernière case du tableau content de stockage des données.

Représentation chaînée des piles

Les éléments de la pile sont chaînés entre eux, et le sommet d’une pile non vide est le pointeur vers le premier élément de la liste. Exemple de définition d’une structure de pile chaînée Pseudo code formel STRUCTURE pile sommet : liste nb_elt : entier Implantation C typedef struct pile { liste sommet; int nb_elt; } pile; 

Manipulation d’une pile Initialiser une pile juste déclarée

Déclarations Résultat de type pile En-tête : pile init() Algorithme « initialiser » FONCTION init() : pile VAR p : pile DEBUT p.sommet ← NULL p.nb_elt ← 0 RETOURNER p FIN Tester si la pile est vide Déclarations Donnée : pile p Résultat : de type booléen En-tête en C : int pile_vide (pile p) 88 3.1. Piles Algorithme « pile vide » FONCTION pilevide(p : pile) : booléen VAR vide : booléen DEBUT SI p.nb_elt=0 ALORS vide ← vrai SINON vide ← faux RETOURNER vide FIN Placer un élément au sommet de la pile (empiler) Déclarations Donnée : T elt_à_emp Donnée modifiée : pile *pp En-tête en C : void empiler(T elt_a_emp, pile *pp); Algorithme « empiler » FONCTION empiler(elt_a_emp : T ,*pp : pile) VAR courant : liste DEBUT RESERVER(courant) courant →info ← elt_à_emp // si la pile était vide alors sommet était NULL // et on crée la pile : courant →suivant ← pp →sommet pp →sommet ← courant // rattache ancien sommet pp →nb_elt ← pp →nb_elt + 1 FIN Retirer un élément du sommet de la pile (dépiler) Déclarations Donnée modifiée : pile *pp, T *elt_dep Résultat : de type booléen En-tête en C : int depiler(pile *pp, T *elt_dep); Algorithme « dépiler » FONCTION depiler(*pp :pile, *elt_dep : T) : booléen VAR courant : ptr_poste; ok : booléen; DEBUT SI non pile_vide(*pp) ALORS ok ← vrai *elt_dep ← pp →sommet →info pp →nb_elt ← pp →nb_elt — 1 // libération de l’espace mémoire : courant ← pp →sommet  // si la pile contenait un seul élément, Dunod – La photocopie non autorisée est un délit 89 Chapitre 3 • Structures séquentielles complexes // elle devient vide, et *pp.sommet devient NULL pp→sommet ← pp→sommet→suivant LIBERER (courant) SINON ok ← faux RETOURNER ok FIN 

LES FILES

Dans le cas d’une file on fait les adjonctions à une extrémité, les accès et les suppressions à l’autre extrémité. Par analogie avec les files d’attente on dit que l’élément présent depuis le plus longtemps est le premier, on dit aussi qu’il est en tête. Les files sont aussi appelées FIFO pour First-In-First-Out, c’est-à-dire premier entré, premier sorti. Les opérations sur les files sont : • tester si la file est vide ; • accéder au premier élément de la file ; • ajouter un élément dans la file ; • retirer le premier élément de la file.

Représentation contiguë des files

Dans ce cas on doit conserver l’indice i du premier élément et l’indice j de la première case libre après la file. On fait progresser ces indices modulo la taille lmax du tableau. Le seul point délicat est la détection des débordements. Définition d’une structure de file réalisée avec un tableau Pseudo code formel STRUCTURE file donnée : T[n] tête : entier fin : entier Implantation en C typedef struct file { T donnée[n]; int tête; int fin; } file;