Les Piles & Les Files

comprenant :

(cid:73) type de données qu’on peut mettre en mémoire

(cid:73) description des opérations possibles sur ces données

(cid:73) conditions d’erreurs associées aux opérations

Sana HAMDI (ISSAT-M)

4/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Plan

1 Objectifs

2 Rappels

3 Abstraction

4 Type abstrait de données PILE

Sana HAMDI (ISSAT-M)

4/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Les Piles

(cid:136) Garde en mémoire des objets arbitraires

(cid:136) Les insertions et suppressions se font dans l’ordre ”dernier arrivé, premier

servi”

(cid:136) Principales opérations :

(cid:73) empiler(objet) insère un objet sur la pile

(cid:73) dépiler():objet retire et retourne l’objet en haut de la pile

Sana HAMDI (ISSAT-M)

5/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Les Piles

(cid:136) Garde en mémoire des objets arbitraires

(cid:136) Les insertions et suppressions se font dans l’ordre ”dernier arrivé, premier

servi”

(cid:136) Principales opérations :

(cid:73) empiler(objet) insère un objet sur la pile

(cid:73) dépiler():objet retire et retourne l’objet en haut de la pile

(cid:136) opérations auxiliaires :

(cid:73) sommet():objet retourne l’objet en haut de la pile sans le retirer

(cid:73) taille():entier retourne le nombre d’objets de la pile

(cid:73) pileVide():booléen indique si la pile est vide ou non

(cid:73) pilePleine():booléen indique si la pile est pleine ou non (cas contiguë)

(cid:136) 2 implémentations

(cid:73) Représentation contiguë

(cid:73) Représentation chaˆınée

Sana HAMDI (ISSAT-M)

6/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Piles en représentation contiguë : tableaux

Type Élément = . . . //dépend du problème

Type Tab = tableau [1 à MAX] de Élément

Type

Structure Pile

corps : Tab

taille : Entier //nombre d’élément

finStructure Pile

procédure créerPile (var p : Pile)

p.taille ← 0

Fin Procédure

Sana HAMDI (ISSAT-M)

7/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Piles en représentation contiguë : tableaux

Fonction pileVide (p : Pile) : Booléen

pileVide ← (p.taille = 0)

Fin Fonction

Fonction pilePleine (p : Pile) : Booléen

pilePleine ← (p.taille = Max)

Fin Fonction

Fonction sommet (p : Pile) : Élément

Si pileVide (p) Alors

Erreur

Sinon

retourner p.corps[p.taille]

Fin Si

Fin Fonction

Sana HAMDI (ISSAT-M)

8/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Piles en représentation contiguë : tableaux

Procédure empiler (e : Élément, var p:Pile)

Si (p.taille < MAX) Alors

p.taille ← p.taille + 1

p.corps[p.taille] ← e

Sinon

Erreur //possibilité de ré-allocation du tableau

Fin Si

Fin Procédure

Fonction dépiler (var p :Pile): Element

Si pileVide (p) Alors Erreur

Sinon

p.taille ← p.taille - 1

dépiler ← p.corps[p.taille]

Fin Si

Fin Procédure

Sana HAMDI (ISSAT-M)

9/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Piles en représentation chaˆınée : listes chaˆınées

Type Élément = . . . //dépend du problème

Type PtrM = Maillon *

Type

Structure Maillon

valeur : Élément

next : PtrM

finStructure Maillon

procédure créerPile (var Pile : PtrM)

Pile ← Nil

Fin Procédure

Fonction pileVide (Pile : PtrM) : Booléen

pileVide ← (Pile = Nil)

Fin Fonction

Sana HAMDI (ISSAT-M)

10/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Piles en représentation chaˆınée : listes chaˆınées

Fonction taille (Pile : PtrM) : entier

Variables

p : PtrM

n : entier

Début

p ← Pile

n ← 0

Si pileVide(Pile) = Faux Alors

n ← 1

Tant que *p.next (cid:54)= Nil Faire

n ← n + 1

p ← *p.next

Fin Tant que

Fin Si

taille ← (n)

Fin Fonction

Sana HAMDI (ISSAT-M)

11/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Piles en représentation chaˆınée : listes chaˆınées

Fonction Recherche (Pile : PtrM, pos : entier) : PtrM

Variables

p : PtrM, n : entier

Début

p ← Pile ; pred ← Nil ;n ← 0

Si pileVide (p) Alors Recherche ← Nil

Sinon

Tant que *p.next (cid:54)= Nil et n (cid:54)= pos Faire

n ← n + 1

pred ← p

p ← *p.next

Fin Tant que

Si p = Nil Alors Recherche ← Nil

Sinon Recherche ← Pred

Fin Si

Fin Si

Fin Fonction

Sana HAMDI (ISSAT-M)

12/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Piles en représentation chaˆınée : listes chaˆınées

Fonction ValSommet (Pile : PtrM) : Élément

Variables

p : PtrM

Début

Si pileVide(Pile) Alors

Erreur

Sinon

p ← Recherche (Pile, taille(Pile))

ValSommet ← *p.valeur

Fin Si

Fin Fonction

Sana HAMDI (ISSAT-M)

13/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Piles en représentation chaˆınée : listes chaˆınées

Procédure Empiler (var Pile : PtrM, x : Élément)

Variables

pt : PtrM

Début

p ← réserver(tailleDe(Maillon))

*p.valeur ← x

*p.next ← Nil

Si Pile = Nil Alors

Pile ← p

Sinon

pt ← Recherche (Pile, taille(Pile))

*pt.next ← p

Fin Si

Fin Procédure

Sana HAMDI (ISSAT-M)

14/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Piles en représentation chaˆınée : listes chaˆınées

Procédure Dépiler (var Pile : PtrM)

Variables

p, pred : PtrM

Début

Si pileVide(Pile) Alors Erreur

Sinon

pred ← Recherche (Pile, taille(Pile)-1)

Si pred = Nil Alors

p ← Pile

Pile ← Nil

Sinon

p ← *pred.next

*pred.next ← Nil

Fin Si

Libérer(p)

Fin Si

Fin Procédure

Sana HAMDI (ISSAT-M)

15/ 16

Objectifs

Rappels

Abstraction

Type abstrait de données PILE

Application

Remplissage d’une zone d’une image

Une image en informatique peut être représentée par une matrice de points

”Image” ayant M colonnes et N lignes. Un élément Image[x, y] de la matrice

représente la couleur du point p de coordonnées (x, y). On propose d’écrire ici une

fonction qui, à partir d’un point p, étale une couleur c autour de ce point. La

progression de la couleur étalée s’arrête quand elle rencontre une couleur autre que

celle du point p. La figure suivante illustre cet exemple, en considérant p = (3, 4).

Pour effectuer le remplissage, on doit aller dans toutes les directions à partir du

point p. Ceci ressemble au parcours d’un arbre avec les noeuds de quatre fils. La

procédure suivante permet de résoudre le problème en utilisant une pile.

Sana HAMDI (ISSAT-M)

16/ 16

Merci pour votre attention !

Sana Hamdi

Assistante en Informatique à ISSAT Mateur

Membre du Laboratoire LIPAH (FST-Tunisie) et

du Laboratoire SAMOVAR (Télécom SudParis-France)

Sana HAMDI (ISSAT-M)

16/ 16