Motivation 2 Pour de nombreux algorithmes et SDD squentielles
Oprations limites et contraintes Ajout et retrait seulement aux
extrmits (tte, queue) Ecrire : crer un maillon, copier llment,
ajouter le maillon Lire : retirer le maillon, copier llment,
supprimer le maillon Deux structures fondamentales Ajout et retrait
seulement en tte : pile Ajout resp. retrait en queue resp. en tte :
file
Page 3
Vocabulaire 3 Dsignation comportementale FIFO/LIFO First In
First Out = une file (EN : queue) Last In First Out = une pile (EN
: stack) Extrmits Ttes Pile : sommet (EN : top) File : sortie
Queues Pile : base File : entre Oprations EN : push/pop FR :
empiler/dpiler resp. enfiler/dfiler Dimensions Hauteur dune pile
vs. longueur dune file
Page 4
Reprsentation 4 Sommet Base Sortie Entre PUSHPOP PUSHPOP
Page 5
Applications types 5 De manire gnrale La pile sert mmoriser des
rsultats intermdiaires Pile dappels, analyseur syntaxique La file
sert en temporiser des flux Tampons pour la communication inter
processus En algorithmique Structures auxiliaires lmentaires les
plus courantes Algorithme gnrique de parcours itratif dun arbre
Utilisation dune pile : parcours en profondeur Utilisation dune
file : parcours en largeur
Page 6
5 oprations (et pas davantage) 6 Spcification Cration et
supression Tester si la _ile est vide E__iler (push) D_iler (pop)
Implmentation Statique avec tableau Dynamique avec chanage
Lutilisation dune LSC ? Pertinent !
Page 7
Implmentation statique de la pile 7 Limite n lments Tableau
P[1..n] et attribut sommet Llment situ la base de la pile : P[1]
Llment situ au sommet de la pile : P[sommet] La pile est vide ssi
sommet = 0 Un empilement peut avoir lieu ssi sommet < n sommet
est alors incrment Un dpilement peut avoir lieu ssi sommet > 0
sommet est alors dcrment
Page 8
Implmentation statique de la pile En langage
algorithmiqueExemple de traduction en C 8 typedef struct pile { T
donne[n]; int sommet; } pile; typedef pile *pile_adr;
Page 9
Crer une pile 9
Page 10
Test de pile vide 10
Page 11
Empiler 11
Page 12
Dpiler 12
Page 13
Implmentation statique de la file 13 Tableau P[1..n] et
attributs entre : index de la position libre suivante sortie :
index de llment de tte Oprations sur les index : modulo n Principe
similaire ce qui a t vu pour le buffer clavier Reprage Llment situ
lentre de la file : P[entre 1] Llment situ la sortie de la file :
P[sortie] Difficult : gestion des dbordements positif et ngatif
File vide ssi entre = index Et pour la file pleine ? Pourquoi la
capacit est-elle limite n 1 ?
Page 14
Implmentation dynamique de la pile 14 Deux possibilits A)
Utiliser simplement une LSC B) Composer dans une structure une LSC
un champ profondeur Dans les deux cas, la tte joue le rle de
sommet
Page 15
Implmentation dynamique de la pile En langage
algorithmiqueExemple de traduction en C 15 typedef struct pile {
liste sommet; unsigned hauteur; // option } pile; typedef pile
*pile_adr;
Page 16
Crer une pile 16
Page 17
Test de pile vide 17
Page 18
Empiler 18
Page 19
Dpiler 19
Page 20
Implmentation dynamique de la file 20 Structure Une LSC Deux
adresses : La sortie de file (la tte de la LSC) Option un champ
largeur On ne prsente ci-aprs que la version sans largeur Pour
adapter vos algos cf. pile
Page 21
Implmentation dynamique de la file En langage
algorithmiqueExemple de traduction en C 21 typedef struct file {
liste entree; liste sortie; } file; typedef file *file_adr;
Page 22
Crer une file 22
Page 23
Test de file vide 23
Page 24
Enfiler 24 Algorithme 37 : Enfiler (f : file_adr, e : T)
(version dynamique Donne : ladresse de la file f Donne : llment e
enfiler dans f Variable locale : Ladresse m du maillon crer pour
stocker e dbut m rserver maillon m info e m succ nul si EstFileVide
(f) alors f sortie m sinon f entre succ m fin f entre m fin
Page 25
Dfiler 25 Algorithme 38 : Defiler (f : file_adr) : T (version
dynamique Donne : ladresse de la file f Variable locale : Llment e
dfil de f Variable locale : Ladresse m du maillon supprimer aprs
lextraction de e dbut si EstFileVide (f) alors erreur dbordement
ngatif sinon m f sortie f sortie m succ si f sortie = nul alors f
entre nul fin e m info librer m retourner e fin
Page 26
Simuler la rcursivit avec une pile 26 Soit lalgorithme rcursif
suivant : En donner la version itrative qui simule la rcursivit Tip
Utiliser une pile auxiliaire comme pile dappels