IFT-10541A : Hiver 2003

Semaine 5 :Piles et files

2

Piles Piles :

LIFO : last in, first outDAPS : dernier arrivé, premier sorti

ex. : assietteslivresfacturespile d’exécutionévaluation d’expressions

in out

pile

3

Files Files :

FIFO : first in, first outPAPS : premier arrivé, premier sorti

ex. : assiettesfacturesbanquechaîne de montageimprimantetâches à exécuter

out in

file

4

Piles et files structures de données auxiliaires

car utilisées par d’autres structures(comme les listes ordonnées)

utilité : support à des applications support à d’autres structures de données modélisation de la réalité en informatique : système d’exploitation

     gestion interne     évaluation d ’expressions     etc.

5

Piles espace de mémorisation temporaire, avec

conventions de manipulation (gestion) : ajouter un nouvel élément sur la pile (empiler) enlever un élément de la pile (dépiler) regarder le premier élément de la pile indiquer si la pile est vide regarder si un élément est sur la pile remplacer un élément sur la pile

pile

6

manipulations (empiler et dépiler) par le même point d’accès

in

out

pilepile

out

in

Pile = liste + gestion adaptée

7

Pile = liste + gestion adaptée

empiler (push) :

dépiler (pop) :

sommet (top) :

pile vide ?

élément sur la pile (peep) ?

remplacer un élément sur la pile

8

Piles : spécifications formelles Une pile est une structure monolithique,

c.-à-d. qu’elle n'est pas construite à l'aide de sous-piles.

Les opérations ne vont pas créer de nouvel objet de type pile.

La pile passée en paramètre (par référence) sera mise à jour (au besoin).

9

Piles : spécifications formelles empiler : p p + x

Pile empiler(Pile p, TypeEl x, int *err) dépiler : -p

Pile depiler(Pile p, TypeEl *x, int *err); sommet : !p

TypeEl sommet(Pile p, int *err);

10

Piles : spécifications formelles pile vide : p = ?

Bool pileVide(Pile p, int *err); appartenance : x p?

Bool appartientP(Pile p, TypeEl x, int *err);

remplacement : p p - x/y Pile remplacerPile(Pile p, TypeEl x,

TypeEl y, int *err);

11

Piles : autres fonctions création et initialisation :

Pile p1, p2;int err;p1 = initPile(&err);p2 = initPile(&err);

vider une pile :Pile viderPile(Pile p, int *err);ou : while(! (p = ?) ) p -p;

 typedef struct{

} Pile;

12

en tableau : (accès : indice 0)

0 1 2 3 4 ... 99

pile

Piles : modèles d’implantation

13

en tableau : (accès par la fin)

0 1 2 3 4 ... 99

pile

Piles : modèles d’implantation

14

-1

-1

pile

pile

Piles : implantation en tableau #define MAX_PILE 100

typedef struct{ int top;

TypeEl tab[MAX_PILE];} Pile;

#define MAX_PILE 100typedef struct{ int taille

int top;TypeEl * tab;

} Pile;

15

création :Pile p1;int erreur;

initialisation : pile initPile(int taille, int *err);

p1 = initPile(2000,&erreur);

Piles : création et initialisation

-1

pile

16

liste chaînée

debut

pile

Piles : modèles d’implantation

17

3

pile

Piles : implantation par listes #define MAX_PILE 100

typedef struct{ elem * debut;

int cpt;} Pile;

18

création :Pile p1;int erreur;

initialisation : Pile initPile(int *err);

p1 = initPile(&erreur);

0

p1

Piles : création et initialisation

19

Gestion de piles par listes Gestion simple :

empiler dépiler sommet pileVide ? appartenance remplacement

20

approches hybrides : implantation par tableau (par nœud) implantation par listes (globalement)

114 4 3

p1

Ratio : info admin./espace total

21

Comment accéder au sommet ? Comment ajouter un élément ? Comment enlever un élément ?

p1

pile

fin

cptcpt

tab

suiv

nœud... en-tête(header)

114 4 3

Modèles hybrides

22

Applications des piles gestion de l’ordre d’exécution des fonctions

où TypeEl =struct { adresse de retour dans la fonction; variables de la fonction;}

f1 appelle f2: avant l’appel : la struct décrivant f1 est mise sur la pile au retour, on dépile et on continue avec les variables

dépilées et à partir de l’adresse indiquée

23

Applications des piles On peut donc simuler la pile.

On peut alors transformer une fonction récursive en fonction itérative avec gestion explicite d’une pile.

Avantages versus désavantages ???

24

Vérification d’imbrication {, (, [ doit correspondre à }, ) et ] respectivement

i 1Tantque i < nb de caractères faire

Si caractère[i] est '(' ou '{' ou ' [' alorsempiler caractère[i]

SinonSi caractère[i] est ') ' ou '}' ou ']' alors

Si caractère[i] = symétrique sommet de la pile alors dépiler la pile

SinonERREUR

i i + 1Fin Tantque

25

Vérification d’imbrication Exemples :

3*(2-[4 / (2 +x)] * y) 3*(2-[4 / (2 +x]) * y)((((x + 4 / 3 * (-5)))))

26

Notation polonaise inversée

AB+ ; CD- ; EF* ; GH/

3*(2-[4 / (2 +x)] * y)

3 (2-[4 / (2 +x)] * y) *

3 (2-[4 / (2 +x)] * y) *

3 (2 [4 / (2 +x)] * y-) *

3 (2 [4 / (2 +x)] * y-) *

3 (2 [4 (2 +x)/] * y-) *

3 (2 [4 (2 +x)/] * y-) *

3*(2-[4 / (2 +x)] * y) 3 (2 [4 (2 x +)/] * y-) *

3 (2 [4 (2 x +)/] * y-) *

3 (2 [4 (2 x +)/] y * -) *

3 (2 [4 (2 x +)/] y * -) *

3 2 4 2 x + / y * - *

27

3*(2-[4 / (2+x)] * y) 3 2 4 2 x + / y * - *

Évaluation d’expr. arithmétiques

28

évaluation d’expressions suffixées voir manuel de cours p.97

(pour opérateurs binaires mais pourrait être étendu  pour opérateurs n-aires)

production d’expressions suffixées voir manuel de cours p.99

Algorithmes à lire

29

Files espace de mémorisation temporaire, avec

conventions de manipulation (gestion) : ajouter un nouvel élément sur la file (enfiler) enlever un élément de la pile (défiler) regarder le premier élément de la file regarder le dernier élément de la file indiquer si la file est vide regarder si un élément est sur la file remplacer un élément sur la file

out in

file

30

Files : spécifications formelles enfiler : f f + x

File enfiler(File f, TypeEl x, int *err);

défiler : -f File defiler(File f, TypeEl *x, int *err);

premier : !f TypeEl premier(File f, int *err);

31

Files : spécifications formelles dernier : !!f

TypeEl dernier(File f, int *err); file vide : f = ?

Bool fileVide(File f, int *err); appartenance : x f?

Bool appartientFile(File f, TypeEl x, int *err); remplacement : f f - x/y

File remplacerFile(File f, TypeEl x, TypeEl y, int *err);

32

in out

file

out in

file

File = liste + gestion adaptée manipulations (enfiler et défiler)

par des points d’accès opposés

33

File = liste + gestion adaptée

enfiler :

défiler :

premier :

dernier :

file vide ?

élément sur la file ?

remplacer un élément sur la file :

34

Files : autres fonctions création et initialisation :

File f1, f2;f1 = initFile(int *err);f2 = initFile(int *err);

vider une file :file viderFile(File f, int *err);ou : while(! (f = ?) ) f -f;

 typedef struct{

} File;

35

T ê t e Q u e u e

Insérer 'Robert'

T Q

P a u l

R e n é

M a r c

P a u l

P a u l R e n é

R e n é M a r c

M a r c

M a r c

M a r c

M a r c

J e a n

J e a n

J e a n

A n n e

A n n e

T

T

T

T

T

T

T

Q

Q

Q

Q

Q

Q

QD ébordement

V ide

Insérer 'Paul'

Insérer 'Jean'

Insérer 'René'

Extraire 'Paul'

Extraire 'René'

Insérer 'A nne'

Insérer 'Marc'

Implantation par tableau

36

Implantation : liste circulaire

q = (q + 1) modulo MAXELT

37

#define MAXELT 100typedef struct{ int tete;

int queue;TypeEl * tab;int taille;

} File;

0

file

0

0

0 1 2 ... 99

Files : implantation en tableau

38

création :file f1;int erreur;

f1

tete

queue

tab

taille

Files : création et initialisation

39

création :File f1;int erreur;

initialisation : File initFile(int taille, int *err);

f1 = initFile(2000,&erreur);

file

0 1 2 ... 99

f1

tete

queue

tab

0

0

0

taille

Files : création et initialisation

40

Gestion de listes circulaires

enfiler défiler premier dernier file vide? appartenance remplacer

41

Files : implantation par listes

tete

el

suivant

el

suivant

el

suivant

cptqueue

3

typedef struct{ elem *tete;

int cpt;elem *queue;

} File;

42

Files : implantation par listes

tete

el

suivant

el

suivant

el

suivant

cptqueue

3

enfilerdéfilerpremierdernierfile vide?appartientremplacer

43

cpt

tab

suiv

4 4 3

tete

cpt

queue

11

enfilerdéfilerpremierdernierfile vide?appartientremplacer

Modèles hybrides

44

Files prioritaires gestion d’une seule file

insertion se fait selon la priorité éléments toujours triés selon leur priorité

in

file

41 84 1in

file

11 44 8

45

Files prioritaires gestion de plusieurs files

1 file par niveau de priorité (sous-liste) une liste triée selon le niveau de priorité

avec un bloc descripteur pour la sous-liste correspondante

A B C D

D1 D2

B1 B2 B3 B4

A1 A2 A3

… … …

46

Applications des files Modélisation du phénomène :

banque chaîne de montage etc.

En informatique : traitement « batch » (en lots) gestion des listes d’impression

47

Traitement « batch » (en lots)

Tantque toujours fairesi f n’est pas vide alors:

tâche = defile(f);exécuter tâche;

Fin Tantque

Si exécution(tâche) alors:f = enfiler(tâche,f);

Processus consommateur

Processus producteur

48

simulation : élément = <événement,temps> priorité = temps

in

file

41 84 1in

file

11 44 8

Application des files prioritaires

49

Simulation exemple :

banque : 4 guichets automatiques revenus associés à chaque transaction 1 seule file d’attente pour tous les guichets taux d’arrivée des clients (hres de pointe) temps de service moyen temps d’attente d’un client versus sa

position dans la file modèle de simulation

50

Simulation bancaire processus :

arrivée d’un client : enfile (1 processus si 1 seule file) à une certaine fréquence : loi de Poisson heure d’entrée dans la file : horloge centrale temps de transaction requis nombre de transactions revenus par client tolérance au temps d’attente

traitement d’un client (par guichet) : défile (4 processus) temps de transaction selon le client mise à jour des statistiques

l’horloge (1) : mise à jour de l’horloge et de la file d’attente

51

Simulation de files d’attente

on évalue certaines métriques : la longueur moyenne de la file le nombre de clients perdus les revenus obtenus/perdus pendant la simulation le temps d’utilisation des guichets

on modifie certains paramètres et on recommence !

in

file

41 84 1in

file

11 44 8Guichet no1

Guichet no2

Guichet no3

Guichet no4

Création