Ecole Sup rieure de Technologie et dInformatique

Cours sur les Piles et les Files

Pour les classes IA1

Mai 2011

Structure de Donn e Avanc e : Pile (Stack)

I/ D finition

Une pile est une liste d l ments de m me type o les ajouts, suppressions, et acc s ne sont

possibles que par rapport un seul l ment : LE SOMMET DE LA PILE.

Le sommet (ou la t te) est le dernier l ment qui a t ajout la pile. Une pile est une

structure de donn es mettant en oeuvre le principe dernier entr , premier sorti (LIFO :

Last-In, First-Out en anglais).

L l ment t (supprim ) de lensemble par lop ration SUPPRESSION est sp cifi

lavance (et donc cette op ration ne prend alors que lensemble comme argument) : l l ment

supprim est celui le plus r cemment ins r . Lop ration INSERTION dans une pile est

commun ment appel e EMPILER, et lop ration SUPPRESSION : D PILER.

Il est facile dimpl menter une pile au moyen dun tableau. La seule difficult dans cette

impl mentation est la gestion des d bordements de pile qui interviennent quand on tente

deffecteur lop ration D PILER sur une pile vide et lop ration EMPILER sur un tableau

codant la pile qui est d j plein. Ce dernier probl me nappara t pas lorsque lon impl mente

les piles au moyen dune structure de donn es dont la taille nest pas fix e a priori (comme

une liste cha n e).

II/Mode de repr sentation contig e

II/1) D finition du type de donn es Pile :

La structure de donn es comprend un tableau et le nombre d l ments significatifs de ce

tableau. Il est n cessaire de fixer d s le d part une valeur maximale du nombre total des

l ments de la Pile. Nous obtenons la structure suivante

#define MAX 100

Typedef struct pile

{Type_element Tableau ;

int sommet ; //compris entre 0 et MAX : cest lindice de la premi re case libre

} Pile ;

II/2) Impl mentation des op rations appliqu es aux Piles :

II/2/1 Cr ation de pile

Pile Cr erPileVide(){Pile P ;

P.sommet=0 ;

Return P ;}

II/2/2 Test pile vide

int EstPileVide()

{Return (P.sommet = = 0) ; }

II/2/3 Test pile pleine

int EstPileVide()

{Return (P.sommet = = Max) ;}

II/2/4 Acc s la t te de la Pile

Type_element tete (Pile P)

{if ( !EstPileVide(P))

return (P.Tableau )

else

printf("Erreur : Pile vide ") ;}

II/2/5 Empiler un l ment

Pile Empiler (Pile P, Type_element e)

{if ( ! EstPilePleine(P)){ p.Tableau = e ;

P.Sommet ++ ;}

Else printf("Erreur : Pile pleine ") ;

Return (P) ;}

II/2/6 D piler un l ment

Pile Depiler (Pile P)

{if ( ! EstPileVide(P))

P.Sommet-- ;

else

printf("Erreur : Pile Vide ") ;

return (P) ;}

II/2/7 Test de pile vide

int EstPileVide (Pile P)

{return (P.Sommet = = 0) ;}

II/2/8 Test de pile pleine

int EstPilePleine (Pile P)

{return (P.Sommet > MAX) ;}

III Impl mentation cha n e

Pour impl menter une pile cha n e, nous allons reprendre la m me structure de donn es que

nous avons d finie pour les listes cha n es.

Dans ce sch ma une pile est une succession de cellules. Chaque cellule de la pile contient

deux champs :

" un champ pour linformation,

" un champ pointeur sur l l ment suivant.

Lidentificateur de la pile (p) repr sente le sommet (t te) de la pile. Les l ments sont cha n s

gr ce au pointeur (suivant), le dernier l ment de la pile (le premier qui a t ins r ) est suivi

par la valeur NULL.

III/1 D finition cha n e du type de donn es Pile :

La structure de donn es pile est la m me que la structure de donn es liste.

Typedef struct cellule

{Type_element Val ;

Cellule * succ ;} Cellule ;

Typedef Cellule * Pile ;

III/2 Impl mentation des op rations appliqu es aux Piles :

III/2/1 Cr ation de pile

Pile Cr erPileVide()

{Pile P ;

P=NULL; Return P ;}

III/2/2 Test pile vide

int EstPileVide()

{Return (P==NULL) ;}

III/2/3 Acc s la t te de la Pile

Type_element tete (Pile P)

{if ( !EstPileVide(P))

return (P Val);

else printf("Erreur : Pile vide ") ;}

III/2/4 Empiler un l ment

Pile Empiler (Pile P, Type_element e)

{Cellule * NC ;

if(NC)

{NC=(Cellule *)malloc(sizeof(NC)) ;

NC Val=e;

NC succ=P;

P=NC;}

Else printf("Erreur : m moire insuffisante ") ;

Return (P) ;}

III/2/5 D piler un l ment

Pile Depiler (Pile P)

{Cellule * NC ;

if ( ! EstPileVide(P))

{NC=P;

p=p succ ;

free(NC) ;}

else printf("Erreur : Pile Vide ") ;

return (P) ;}

IV Conclusion

Les piles sont des structures de donn es tr s fr quentes en informatique, lun de leurs

principaux int r ts est d viter d crire des algorithmes r cursifs. Linconv nient majeur de la

r cursivit , cest quelle peut rendre les programmes tr s lents. Les piles permettent de

r soudre ce probl me. En effet lemploi dune pile permet de passer dun algorithme r cursif

un algorithme it ratif. Une autre des applications des piles est l valuation dexpressions

arithm tiques. Du point de vue impl mentation des piles, et tant donn le type des op rations

effectu es (ajout, suppression et acc s au sommet), les repr sentations cha n e et contigu

sont quivalentes sur le plan de la complexit temporelle.

Par contre le probl me de limitation de la m moire dans le cas dune pile contig e reste pos ,

ainsi que le probl me de gestion de la m moire dans le cas dune pile cha n e : les pointeurs

rendant cette gestion plus lourde.

Structure de Donn e Avanc e : File (Queue)

I/ D finition dune File

Une file est une structure lin aire o lajout dun l ment se fait en fin tandis que la lecture et

la suppression se font au d but. Les files suivent le principe F.I.F.O (First In First Out) : le

premier arriv est le premier tre servi. En informatique, la structure de file est une liste qui

nautorise que les op rations suivantes :

" ajout en fin de la liste,

" retrait au d but de la liste,

" acc s l l ment en d but de liste.

Comme pour les listes et pour les piles, les deux modes de repr sentation cha n e et

contigue sont utilis es pour impl menter une file. Pour bien comprendre limpl mentation

utilisant la repr sentation contigu , un exemple complet sera trait . En effet, il est possible

dimpl menter les files en utilisant les tableaux de deux mani res diff rentes :

" Mode de repr sentation lin aire,

" Mode de repr sentation circulaire

Les tableaux g r s lin airement pr sentent un d faut, et les tableaux g r s circulairement

permettent dexploiter au mieux

la capacit maximale en nombre d l ments, et

dimpl menter une file de fa on optimale.

II/1) Impl mentation contigu lin aire

Dans une file lajout se fait la fin, tandis que la lecture et la suppression se font au d but. Si

lon utilise un tableau, cela va se traduire par un d calage de tous les l ments lors de la

suppression (ou lors de lajout : cela d pend de comment on d cide dorganiser les donn es

dans la file). Etant donn que les suppressions ainsi que les ajouts sont fr quents, cette

m thode nest pas optimale. Pour supprimer un l ment (ou lajouter) dans une file de n

l ments, il faut chaque fois faire n op rations de d calage. Etant donn que lop ration de

suppression risque de se r p ter plusieurs fois, cette m thode nest pas avantageuse.

II/2) Impl mentation contigu circulaire

Il faut circulariser le tableau en raisonnant en terme de modulo MAX quand on

incr mente les indices T te et Queue. Dans ce cas nous allons consid rer que le premier

indice du tableau est gal z ro ( cause du calcul fait en fonction de modulo MAX).

Un tableau de capacit MAX naccueillera en fait que MAX-1 l ments. Dans ce type

dimpl mentation :

" si T te = Queue alors la file est vide, cela se produit apr s la cr ation dune file ou apr s des

d filements successifs.

" si (Queue + 1) modulo MAX = T te alors la file est pleine.

Le tableau a une capacit maximale de 8 l ments,

" les l ments effectifs dans la file sont au nombre de 7,

" lindice T te a pour valeur 5,

" lindice Queue a pour valeur 4,

" si on d file successivement 7 fois de la file, lindice T te va prendre comme valeur (5+7)

modulo 8 = 4 qui est gal Queue -> la file est nouveau vide.

III/1)D finition contigu du type de donn es File :

Le type file int gre dans une m me structure :

" le tableau des donn es de capacit MAX l ments,

" lindice correspondant la t te de la file,

" lindice correspondant la queue de la file.

#define Max = 100

Typedef struct file

{Type_element Tab ;

int T te ;int Queue ;}File ;

III/2) Impl mentation des op rations appliqu es aux Files :

III/2/1 Cr ation dune file

File Cr erFileVide ()

{File f ;

f.T te = 0 ;

f.Queue = 0 ;

return(f) ;}

III/2/2 Est File vide

int EstFileVide (File f)

{return (f.T te= = f.Queue) ;}

III/2/3 Est File pleine

Une file est pleine, si elle a atteint sa capacit maximale en nombre d l ments.

Int FilePleine (File f)

{return ((f.Queue + 1) % Max == f.T te) ;}

III/2/4 Acc s un l ment

Type_element LireFile(File f)

{if ( ! EstFileVide (f))

return (f.Tab )

else printf(Erreur : File vide );}

III/2/5 Enfiler un l ment

Il faut v rifier que la file nest pas pleine avant dajouter un l ment.

File Enfiler(type_element e, File f)

{if ( ! EstFilePleine (f))

{f.Tab = e ;

f.Queue = (f.Queue + 1) % Max ;}

else Printf( Erreur File pleine );

return (f) ; }

III/2/6 D filer un l ment

File D filer ( File f)

{if ( ! EstFileVide (f))

{f.T te= (f.T te + 1) % Max ;}

Else Printf( Erreur File vide );

return(f) ;}

IV/ Impl mentation cha n e

Le choix de la structure de donn es dans ce cas est facile faire, il suffit dune liste cha n e et

de deux pointeurs :

" un pointeur pour indiquer la cellule de t te de la file,

" et un pointeur pour indiquer la cellule de fin de la file.

Le pointeur Queue permettra de faciliter les ajouts la fin de la file. Au lieu de parcourir toute

la file la recherche du dernier l ment, nous disposons dun pointeur qui permet dajouter

directement cette adresse. Le pointeur T te permettra dacc der la cellule de T te pour lire

la valeur qui sy trouve ou pour d filer l l ment.

Typedef struct cellule

{Type_El ment Valeur ;

struct cellule * suivant ;

}Cellule ;

Typedef file

{Cellule * T te ;

Cellule * Queue ;}File ;

IV/1 Impl mentation cha n e des op rations appliqu es aux Files :

IV/1/1 Cr ation dune file

Pour cr er une nouvelle file il suffit dinitialiser les pointeurs T te et Queue la valeur NULL.

File Cr erFileVide ()

{File f ;

f.T te = NULL ;

f.Queue =NULL ;

return (f) ;}

IV/1/2 File vide int EstFileVide (file f) {Return (f.T te= = NULL) ;}

IV/1/3 Acc s un l ment

Type_El ment LireFile(f : File)

{ if ( ! EstFileVide (f))

return (f.T te valeur) ;

else Printf( Erreur File vide );}

IV/1/4 Enfiler un l ment

Le sch ma ci-dessus illustre lenfilement dun l ment dans une file non vide, ainsi que la

succession d tapes suivre.

1) allouer une nouvelle cellule NC,

2) renseigner la valeur ainsi que le suivant de NC e et NULL,

3) mettre jour le suivant du dernier l ment de la file NC,

5) mettre jour le pointeur Queue NC.

le cas denfilement dun l ment dans une file vide au d part : La t te et la queue taient

gales NULL. Les tapes suivre sont un peu diff rentes :

1) allouer NC,

2) renseigner la valeur et le suivant de NC e et NULL,

4) mettre jour le pointeur T te NC,

5) mettre jour le pointeur Queue NC.

File Enfiler(El ment e, File f)

{cellule * NC ;

(1) NC=(Cellule*)malloc(sizeof(Cellule) );

if (NC)

{ (2) NC valeur =e ;

(2) NC suivant = NULL ;

if ( ! EstFileVide (f))

{(3) f.Queue suivant = NC ;}

Else (4) f.T te = NC ;

(5) f.Queue (cid:2) NC ;}

Return (f) ;}

IV/1/5 D filer un l ment

Pour d filer un l ment deux cas se pr sentent :

" la file contient 2 ou plusieurs l ments,

" la file contient un seul l ment, et devient vide suite au d filement.

File D filer (File f)

{Cellule*NC ;

if ( ! EstFileVide (f))

{(1) NC = f.T te ;

(2) f.T te = f.T te suivant ;

(3) free (NC) ;

if (f.T te == NULL)

(4) f.Queue = NULL ;}

Else printf("Erreur File vide ") ;

Return (f) ;}

V/ Conclusion

Les files sont utilis es dans plusieurs domaines en informatique, nous avons parl au d but du

chapitre de la gestion des v nements par exemple. Les caract res tap s sur le clavier doivent

tre trait s dans leur ordre darriv e, ils sont donc stock s dans une file. La file est une

structure qui est tr s employ e par les syst mes dexploitation. Ces structures de donn es

complexes sont utilis es pour parcourir les graphes ou les arbres. En r sum nous pouvons

dire que les files et les piles servent surtout stocker des donn es en attente dun traitement,

seule la priorit est diff rente : pour les files, le premier arriv est prioritaire, tandis que pour

les piles cest le dernier qui lest. Les deux types de repr sentation que nous avons tudi s,

c'est- -dire la repr sentation contigu circulaire, et la repr sentation cha n e, sont compar es

de la m me mani re que pour les listes et les piles.

La repr sentation contigu est tr s efficace du point de vue gestion de la m moire, mais elle

est limit e quant lutilisation de cet espace m moire. La complexit des op rations pour

cette repr sentation est optimale.

Tandis que la repr sentation cha n e est tr s souple quant l'emploi de la m moire, il est

possible dajouter autant d l ments que possible. Lespace occup est toutefois plus

important.

Le choix dune m thode de repr sentation se fera donc n cessairement en fonction des

besoins de lapplication.

Exercice Ecrire un programme qui permet de comparer entre le contenu dune pile et celui

dune file. Si les l ments de la pile de son sommet vers sa base, sont les m mes que ceux de

la file de sa t te vers sa queue, alors le programme retourne la valeur vrai, sinon il retourne

faux. Donner une version it rative et une version r cursive de ce programme.