Ecole Supérieure en Sciences et Technologies
de l’Informatique et du Numérique
Chapitre II: Les Files et Les Piles
Algorithmique et Structures de
Données Dynamiques
1re année Ecole Prépa. De l’ESTIN de Bejaia
Année: 2020-2021
Chapitre II: Les Files et Les Piles
Les Files
Définition :
Une file est une structures de données définie comme une collection
d’éléments dans laquelle tout nouvel élément est inséré à la fin et un
élément ne peut être supprimé que du début de la liste. Règle du
premier arrivé premier sorti(Servi), ou encore FIFO (First In First Out).
2
Chapitre II: Les Files et Les Piles
Les Files
Domaine d’application :
Les files sont utilisées aussi bien dans la vie courante que dans les
systèmes informatiques. Par exemple, elle modélise la file d’attente
des clients devant un guichet. On retrouve également les files d’attente
dans les programmes de traitement de transactions telle que les
réservations.
Les files sont très utilisées aussi dans les systèmes d'exploitation des
ordinateurs (gestion de processeur, gestion de la mémoire, …).
Nous verrons également que les files peuvent être utilisées pour le parcours
des arbres et pour résoudre tant d'autres problèmes.
3
Chapitre II: Les Files et Les Piles
Les Files
Ajout de nouveaux éléments à la file
e1 e2 e3 e4 Nil
Ajout en
queue de
Tête Queue
liste
x
Suppression d’éléments de la file
e1 e2 e3 e4 Nil
Suppression
Tête Queue
en tête de
liste
4
Chapitre II: Les Files et Les Piles
Les Files
Modèle :
Le modèle abstrait pour les files inclue l'ensemble des opérations de
gestion des files, définies comme suit :
— CréerFile(F) : créer une file vide.
— Enfiler(F, Val): ajouter val en queue de la file.
— Défiler(F, Val): retirer dans val l’élément en tête de file.
— FileVide(F): vérifier si la file est vide.
— FilePleine(F): vérifier si la file est pleine.
5
Chapitre II: Les Files et Les Piles
Les Files
Implémentation :
Une file peut être implémentée par une liste chaînée, ou par un
tableau avec une gestion circulaire. Cependant la gestion par
tableaux présente l’inconvénient que la file a une capacité
limitée, contrairement à la gestion par listes chaînées.
6
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
À l'initialisation : Tête = Queue = 0
Max = 4
Opérations :
1 2 3 4
Enfiler(5)
Enfiler(3)
Enfiler(-1)
Enfiler(10) Tête Queue
7
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
À l'initialisation : Tête = Queue = 0
Max = 4
Opérations :
1 2 3 4
Enfiler(5)
Enfiler(3) 5
Enfiler(-1)
Enfiler(10) Tête Queue
Tête ← Tête +1
Queue ← Queue +1
8
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
À l'initialisation : Tête = Queue = 0
Max = 4
Opérations :
1 2 3 4
Enfiler(5)
Enfiler(3) 5 3
Enfiler(-1)
Enfiler(10) Tête Queue
Queue ← Queue +1
9
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
À l'initialisation : Tête = Queue = 0
Max = 4
Opérations :
1 2 3 4
Enfiler(5)
Enfiler(3) 5 3 -1
Enfiler(-1)
Enfiler(10) Tête Queue
Queue ← Queue +1
10
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
À l'initialisation : Tête = Queue = 0
Max = 4
Opérations :
1 2 3 4
Enfiler(5)
Enfiler(3) 5 3 -1 10
Enfiler(-1)
Enfiler(10) Tête Queue
Queue ← Queue +1
Queue = Max => File pleine, on ne peut plus insérer des éléments
11
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
À l'initialisation : Tête = Queue = 0
Max = 4
Opérations :
1 2 3 4
Enfiler(5)
Enfiler(3) 5 3 -1 10
Enfiler(-1)
Enfiler(10) Tête Tête Queue
Défiler() Tête ← Tête +1
Défiler()
12
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
À l'initialisation : Tête = Queue = 0
Max = 4
Opérations :
1 2 3 4
Enfiler(5)
Enfiler(3) 5 3 -1 10
Enfiler(-1)
Enfiler(10) Tête Tête Queue
Défiler() Tête ← Tête +1
Défiler()
13
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
À l'initialisation : Tête = Queue = 0
Max = 4
Opérations :
1 2 3 4
Enfiler(5)
Enfiler(3) 5 3 -1 10
Enfiler(-1)
Enfiler(10) Tête Queue
Défiler()
Défiler()
Comment réutiliser les cases des éléments défilés ?
14
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
À l'initialisation : Tête = Queue = 0
Max = 4
Opérations :
1 2 3 4
Enfiler(5)
Enfiler(3) 5 3 -1 10
Enfiler(-1)
Enfiler(10) Tête Queue
Défiler() Queue (Queue mod Max) +1
Défiler()
Tête (Tête mod Max) +1
Comment Savoir si la file est pleine ?
Tête = (Queue mod Max) + 1
15
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
{Déclaration}
Const Max = 100
Type File = Structure
Elements : tableau[1..Max] de Typeqq
Tête, Queue: Entier
Fin Structure
Var F : File
— Exercice d’application : en se basant sur cette déclaration,
définissez les primitives du modèle abstrait (CréerFile(F),
FileVide(F), FilePleine(F), Enfiler(F, Val) et Défiler(F, Val)).
16
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
{Création d’une file (initialisation)}
Procédure CréerFile(Var F : File)
Début
F.Tête ← 0
F.Queue ← 0
Fin
17
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
{Vérification File vide}
Fonction FileVide( F :File) : Booléen
Début
Si (F.Tête = 0) Et (F.Queue = 0) Alors
FileVide ← Vrai
Sinon
FileVide ← Faux
FinSi
Fin
18
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
{Vérification File pleine}
Fonction FilePleine(F :File) : Booléen
Début
{Si la Queue précède la Tête}
Si (F.Tête = (F.Queue Mod Max) +1) Alors
FilePleine ← Vrai
Sinon
FilePleine ← Faux
FinSi
Fin
19
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
{Insertion d’un nouvel élément dans la file}
Procedure Enfiler(Var F : File ; V : Typeqq)
Début
Si non FilePleine(F) Alors
Si FileVide(F) Alors
F.Tête ← 1
F.Queue ← 1
Sinon
F.Queue ←(F.Queue Mod Max) +1
Finsi
F.Elements[F.Queue] ← V
Sinon
Ecrire (‘La file est pleine’)
Finsi
Fin 20
Chapitre II: Les Files et Les Piles
Les Files
implémentation :
Par Tableau circulaires :
{Retrait d’un élément de la file}
Procedure Défiler(Var F : File ; Var V : Typeqq)
Début
Si non FileVide(F) Alors
V ← F.Elements[F.Tête]
Si F.Tête = F.Queue Alors
F.Tête ← 0
F.Queue ← 0
Sinon
F.Tête ← (F.Tête Mod Max) +1
FinSi
Sinon
Ecrire (‘La file est vide’)
FinSi
Fin 21
Chapitre II: Les Files et Les Piles
Les Files
Implémentation :
Par Liste chainée :
{Déclaration}
Type
Element = Structure
Val : Typeqq
Suiv: Pointeur(Element)
Fin Structure
File = Structure
Tête, Queue: Pointeur(Element)
Fin Structure
Var F : File
— Exercice d’application : en se basant sur cette déclaration,
définissez les primitives du modèle abstrait (CréerFile(F),
FileVide(F), Enfiler(F, Val) et Défiler(F, Val)).
22
Chapitre II: Les Files et Les Piles
Les Files
Implémentation :
Par Liste chainée :
{Création d’une file (initialisation)}
Procédure CréerFile(Var F : File)
Début
F.Tête ← Nil
F.Queue ← Nil
Fin
23
Chapitre II: Les Files et Les Piles
Les Files
Implémentation :
Par Liste chainée :
{Vérification File vide}
Fonction FileVide( F :File) : Booléen
Début
Si (F.Tête = Nil) Alors
FileVide ← Vrai
Sinon
FileVide ← Faux
FinSi
Fin
24
Chapitre II: Les Files et Les Piles
Les Files
Implémentation :
Par Liste chainée :
{Insertion d’un nouvel élément dans la file}
Procedure Enfiler(Var F : File ; X : Typeqq)
Var Q: Pointeur(Element)
Début
Allouer(Q)
Q.Val ← X
Q.Suiv ← Nil
Si Non (FileVide(F)) Alors
F.Queue.Suiv ← Q
Sinon
F.Tête ← Q
Finsi
F.Queue ← Q
Fin
25
Chapitre II: Les Files et Les Piles
Les Files
Implémentation :
Par Liste chainée :
{Retrait d’un élément de la file}
Procedure Défiler(Var F : File ; Var X : Typeqq)
Var P: Pointeur(Element)
Début
Si Non (FileVide(F)) Alors
P ← F.Tête
X ← F.Tête.Val
F.Tête ← F.Tête.Suiv
Libérer(P)
Sinon
Ecrire(" la liste est vide ")
Finsi
Fin
26
Chapitre II: Les Files et Les Piles
Les Files
Exercice 1 :
Soit F une file de d’entier. Que serait il le contenu de la file
à la fin d’exécution de ces primitives?
CréerFile(F)
Enfiler(F,5)
Enfiler(F,-1)
Enfiler(F,4)
Défiler(F,E1)
Défiler(F,E2)
Enfiler(F,10)
27
Chapitre II: Les Files et Les Piles
Les Files
Solution :
CréerFile(F)
Enfiler(F,5)
Enfiler(F,-1)
Enfiler(F,4)
Défiler(F,E1)
Défiler(F,E2)
Enfiler(F,10)
28
Chapitre II: Les Files et Les Piles
Les Files
Solution :
CréerFile(F)
Enfiler(F,5) T, Q
Enfiler(F,-1)
Enfiler(F,4)
Défiler(F,E1)
Défiler(F,E2)
Enfiler(F,10)
29
Chapitre II: Les Files et Les Piles
Les Files
Solution :
CréerFile (F)
Enfiler(F,5) T, Q
Enfiler(F,-1) Q
T
Enfiler(F,4)
Défiler(F,E1)
Défiler(F,E2)
Enfiler(F,10)
30
Chapitre II: Les Files et Les Piles
Les Files
Solution :
CréerFile(F)
Enfiler(F,5) T, Q
Enfiler(F,-1) Q
T
Enfiler(F,4)
T Q
Défiler(F,E1)
Défiler(F,E2)
Enfiler(F,10)
31
Chapitre II: Les Files et Les Piles
Les Files
Solution :
CréerFile(F)
Enfiler(F,5) T, Q
Enfiler(F,-1) Q
T
Enfiler(F,4)
T Q
Défiler(F,E1) E1 = 5
T Q
Défiler(F,E2)
Enfiler(F,10)
32
Chapitre II: Les Files et Les Piles
Les Files
Solution :
CréerFile(F)
Enfiler(F,5) T, Q
Enfiler(F,-1) Q
T
Enfiler(F,4)
T Q
Défiler(F,E1) E1 = 5
T Q
Défiler(F,E2) E2 = -1
T Q
Enfiler(F,10)
33
Chapitre II: Les Files et Les Piles
Les Files
Solution :
CréerFile(F)
Enfiler(F,5) T, Q
Enfiler(F,-1) Q
T
Enfiler(F,4)
T Q
Défiler(F,E1) E1 = 5
T Q
Défiler(F,E2) E2 = -1
T Q
Enfiler(F,10)
T Q
34
Chapitre II: Les Files et Les Piles
Les Files
Exercice 2 :
Soit F une file de caractères alphanumériques, écrivez un
algorithme permettant d’éclater la file F en deux autres files
FL et FC, tel que :
FL : File de caractères alphabétiques
FC : File de caractères numériques
35
Chapitre II: Les Files et Les Piles
Les Files
Solution :
Algorithme File_Caractères
Type
Element = Structure
Val : Caractère
Suiv : Pointeur(Element)
Fin Structure
File = Structure
Tête, Queue : Pointeur(Element)
Fin Structure
Var F, FL, FC : File
V: Caractère
36
Chapitre II: Les Files et Les Piles
Les Files
Solution :
Début
{Création de la file de caractères}
CréerFile(F)
Repeter
Ecrire( "Introduire un caractère ")
Lire(V)
V ← UpCase(V)
Si (V Dans [‘A’ .. ‘Z’]) OR (V Dans [0 .. 9] ) Alors
Enfiler(F, V)
Ecrire( " Voulez vous saisir d’autres éléments ? Tapez 1 si oui " )
Lire(Rép)
Jusqu’à (Rep ≠ 1)
Fin
37
Chapitre II: Les Files et Les Piles
Les Files
Solution :
Début
{Eclatement de la file F en file de lettres et file de chiffres}
CréerFile(FL)
CréerFile(FC)
TantQue Non (FileVide(F)) Faire
Défiler(F, V)
Si V dans [‘A’ .. ‘Z’] Alors
Enfiler(FL, V)
Sinon
Enfiler(FC, V)
FinSi
FinTantQue
Fin 38
Chapitre II: Les Files et Les Piles
Les Files
Exercice 3:
Ecrire un algorithme qui permet de :
— Créer une file F d’entiers au moyen des LLC,
— Afficher les éléments de la file F,
39
Chapitre II: Les Files et Les Piles
Les Files
Solution : Algorithme File_Entier
Type
Element = Structure
Val : Entier
Suiv : Pointeur(Element)
Fin Structure
File = Structure
Tête, Queue : Pointeur(Element)
Fin Structure
Var F : File
40
Chapitre II: Les Files et Les Piles
Les Files
Solution :
Procedure Remplir(Var F: File)
Var V, Rep: Entier
Debut
CréerFile(F) {Création de la file d’entiers}
Repeter
Ecrire( "Introduire un entier ")
Lire(V)
Enfiler(F, V)
Ecrire( " Voulez vous saisir d’autres éléments ? Tapez 1 si oui " )
Lire(Rep)
Jusqu’à (Rep ≠ 1)
Fin
41
Chapitre II: Les Files et Les Piles
Les Files
Solution :
Procedure Afficher(F: File)
Var F1: File
Début
CréerFile(F1)
{Affichage des éléments de la file}
TantQue Non (FileVide(F)) Faire
Défiler(F, V)
Ecrire( V, " - " )
Enfiler(F1,V)
FinTantQue
….
42
Chapitre II: Les Files et Les Piles
Les Files
Solution :
…
TantQue Non (FileVide(F1)) Faire
Défiler(F1, V)
Enfiler(F,V)
FinTantQue
Fin
Début {Programme principal}
Remplir(F)
Afficher(F)
Fin
43
Chapitre II: Les Files et Les Piles
Les Piles
Définition :
Une Pile est une structures de données définie comme une collection
d’éléments dans laquelle tout élément ne peut être inséré ni supprimé
que d’une seule extrémité (Sommet). Règle du dernier arrivé premier
sorti(Servi), ou encore LIFO (Last In First Out).
44
Chapitre II: Les Files et Les Piles
Les Piles
Domaine d’application :
La pile constitue l'un des concepts les plus utilisés dans la science des
ordinateurs.
La pile est très utilisée dans le domaine de la compilation : Appels
récursifs, évaluation d'expressions, etc..
Nous verrons également que les Piles peuvent être utilisées pour le
parcours des arbres et pour résoudre tant d'autres problèmes.
45
Chapitre II: Les Files et Les Piles
Les Piles
Ajout de nouveaux éléments à la pile
e4 e3 e2 e1 Nil
Ajout au
Sommet
sommet de
la pile
Suppression d’éléments de la pile
Suppression
x
e4
Sommet
e3
Sommet
e2 e1 Nil
de sommet
de la pile
46
Chapitre II: Les Files et Les Piles
Les Piles
Modèle :
Le modèle abstrait pour la gestion des piles inclue l'ensemble des
opérations suivantes:
— CréerPile(P) : créer une pile vide.
— Empiler(P, Val): ajouter val au sommet de la pile.
— Dépiler(P, Val): retirer dans val l’élément en sommet de la pile.
— PileVide(P): vérifier si la pile est vide.
— PilePleine(P): vérifier si la pile est pleine.
47
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Une pile peut être implémentée par une liste chaînée, ou par un
tableau. Cependant, de même que pour les cas des files, la
gestion par tableaux présente l’inconvénient que la pile a une
capacité limitée, contrairement à la gestion par listes chaînées.
48
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
À l'initialisation : Sommet = 0
Max = 4
Opérations :
Empiler(5) 1 2 3 4
Empiler(3)
Empiler(-1)
Empiler(10) Sommet
49
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
À l'initialisation : Sommet = 0
Max = 4
Opérations :
Empiler(5) 1 2 3 4
Empiler(3) 5
Empiler(-1)
Empiler(10) Sommet
Sommet ← Sommet +1
50
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
À l'initialisation : Sommet = 0
Max = 4
Opérations :
Empiler(5) 1 2 3 4
Empiler(3) 5 3
Empiler(-1)
Empiler(10) Sommet
Sommet ← Sommet +1
51
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
À l'initialisation : Sommet = 0
Max = 4
Opérations :
Empiler(5) 1 2 3 4
Empiler(3) 5 3 -1
Empiler(-1)
Empiler(10) Sommet
Sommet ← Sommet +1
52
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
À l'initialisation : Sommet = 0
Max = 4
Opérations :
Empiler(5) 1 2 3 4
Empiler(3) 5 3 -1 10
Empiler(-1)
Empiler(10) Sommet
Sommet ← Sommet +1
Sommet = Max => Pile pleine, on ne peut plus insérer des éléments
53
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
À l'initialisation : Sommet = 0
Max = 4
Opérations :
Empiler(5) 1 2 3 4
Empiler(3) 5 3 -1 10
Empiler(-1)
Empiler(10) Sommet
Dépiler() Sommet ← Sommet - 1
Dépiler(10)
54
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
À l'initialisation : Sommet = 0
Max = 4
Opérations :
Empiler(5) 1 2 3 4
Empiler(3) 5 3 -1 10
Empiler(-1)
Empiler(10) Sommet
Dépiler() Sommet ← Sommet - 1
Dépiler()
55
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
{Déclaration}
Const Max = 100
Type Pile = Structure
Elements : tableau[1..Max] de Typeqq
Sommet: Entier
Fin Structure
Var P : Pile
— Exercice d’application : en se basant sur cette déclaration,
définissez les primitives du modèle abstrait (CréerPile(P),
PileVide(P), PilePleine(P), Empiler(P, Val) et Dépiler(P, Val)).
56
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
{Création d’une pile (initialisation)}
Procédure CréerPile(Var P : Pile)
Début
P.Sommet ← 0
Fin
57
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
{Vérification Pile vide}
Fonction PileVide( P :Pile) : Booléen
Début
Si (P. Sommet = 0) Alors
PileVide ← Vrai
Sinon
PileVide ← Faux
FinSi
Fin
58
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
{Vérification Pile pleine}
Fonction PilePleine(P :Pile) : Booléen
Début
{Si Sommet = taille maximale du tableau}
Si (P.Sommet = Max) Alors
PilePleine ← Vrai
Sinon
PilePleine ← Faux
FinSi
Fin
59
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
{Insertion d’un nouvel élément dans la pile}
Procedure Empiler(Var P : Pile ; V : Typeqq)
Début
Si non PilePleine(P) Alors
P.Sommet ←P.Sommet + 1
P.Elements[P.Sommet] ← V
Sinon
Ecrire (‘La pile est pleine’)
Finsi
Fin
60
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’un tableau :
{Retrait d’un élément de la pile}
Procedure Dépiler(Var P : Pile ; Var V : Typeqq)
Début
Si non PileVide(P) Alors
V ← P.Elements[P.Sommet]
P.Sommet ← P.Sommet - 1
Sinon
Ecrire (‘La Pile est vide’)
FinSi
Fin
61
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’une liste chainée :
{Déclaration}
Type
Element = Structure
Val : Typeqq
Suiv: Pointeur(Element)
Fin Structure
File = Structure
Sommet: Pointeur(Element)
Fin Structure
Var P : Pile
— Exercice d’application : en se basant sur cette déclaration,
définissez les primitives du modèle abstrait (CréerPile(P),
PileVide(P), Empiler(P, Val) et Dépiler(P, Val)).
62
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’une liste chainée :
{Création d’une pile (initialisation)}
Procédure CréerPile(Var P : Pile)
Début
P.Sommet ← Nil
Fin
63
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’une liste chainée :
{Vérification Pile vide}
Fonction PileVide( P : Pile) : Booléen
Début
Si (P.Sommet = Nil) Alors
PileVide ← Vrai
Sinon
PileVide ← Faux
FinSi
Fin
64
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’une liste chainée :
{Insertion d’un nouvel élément dans la pile}
Procedure Empiler(Var P : Pile ; X : Typeqq)
Var Q: Pointeur(Element)
Début Note :
Allouer(Q) L‘ajout d’une valeur à
Q.Val ← X une pile dynamique
Q.Suiv ← P.Sommet revient à une insertion
P.Sommet ← Q en début de liste si l’on
Fin considère que le
sommet est la tête de
la liste. 65
Chapitre II: Les Files et Les Piles
Les Piles
Implémentation :
Au moyen d’une liste chainée :
{Retrait d’un élément de la pile}
Procedure Dépiler(Var P : Pile ; Var X : Typeqq)
Var Q: Pointeur(Element)
Début
Si Non (PileVide(P)) Alors
Q ← P.Sommet
X ← P.Sommet.Val
P.Sommet ← P.Sommet.Suiv
Libérer(P)
Sinon
Ecrire(" la pile est vide ")
Finsi
Fin
66
Chapitre II: Les Files et Les Piles
Les Piles
Exercice 1 :
Soit P une pile d’entier. Que serait il le contenu de la pile à
la fin d’exécution de ces primitives? CréerPile(P)
Empiler(P,5)
Empiler(P,-1)
Empiler(P,4)
Dépiler(P,E1)
Dépiler(P,E2)
Empiler(P,10)
67
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
CréerPile(P)
Empiler(P,5)
Empiler(P,-1)
Empiler(P,4)
Dépiler(P,E1)
Dépiler(P,E2)
Empiler(P,10)
68
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
CréerPile(P)
Empiler(P,5)
Empiler(P,-1)
Empiler(P,4)
Dépiler(P,E1)
Dépiler(P,E2)
Empiler(P,10)
69
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
CréerPile(P)
Empiler(P,5)
Empiler(P,-1)
Empiler(P,4)
Dépiler(P,E1)
Dépiler(P,E2)
Empiler(P,10)
70
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
CréerPile(P)
Empiler(P,5)
Empiler(P,-1)
Empiler(P,4)
Dépiler(P,E1)
Dépiler(P,E2)
Empiler(P,10)
71
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
CréerPile(P)
Empiler(P,5)
Empiler(P,-1)
Empiler(P,4)
Dépiler(P,E1)
E1 = 4
Dépiler(P,E2)
Empiler(P,10)
72
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
CréerPile(P)
Empiler(P,5)
Empiler(P,-1)
Empiler(P,4)
Dépiler(P,E1) E1 = 4
Dépiler(P,E2)
E2 = -1
Empiler(P,10)
73
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
CréerPile(P)
Empiler(P,5)
Empiler(P,-1)
Empiler(P,4)
Dépiler(P,E1) E1 = 4
Dépiler(P,E2) E2 = -1
Empiler(P,10)
74
Chapitre II: Les Files et Les Piles
Les Piles
Exercice 2 :
Soit P une Pile de réels, écrivez une procédure permettant
d’inverser la pile P.
75
Chapitre II: Les Files et Les Piles
Les Piles
Exercice 2 :
Pour inverser la pile P on peu se servir d’une file où l’on enfile ce qui a été
dépilé puis on empile à partir de la file, les éléments seront installés dans
l’ordre inverse.
Procedure inver (Var P : Pile)
Var X: Reel Tantque Non (PileVide (F)) Faire
F: File
Debut Defiler(F, X) ;
CréerFile(F) Empiler(P, X)
Tantque Non(PileVide (P)) Faire
Depiler(P, X) FinTantque
Enfiler(F, X)
FinTantque
76
Chapitre II: Les Files et Les Piles
Les Piles
Exercice 3:
Ecrire un algorithme qui permet de :
— Créer une Pile P d’entiers au moyen d’une LLC,
— Afficher les éléments de la file P,
77
Chapitre II: Les Files et Les Piles
Les Piles
Solution : Algorithme Pile_Entier
Type
Element = Structure
Val : Entier
Suiv : Pointeur(Element)
Fin Structure
File = Structure
Sommet : Pointeur(Element)
Fin Structure
Var P : Pile
78
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
Procedure Remplir(Var P: Pile)
Var V, Rep: Entier
Debut
CréerPile(P) {Création de la pile d’entiers}
Repeter
Ecrire( "Introduire un entier ")
Lire(V)
Empiler(P, V)
Ecrire( " Voulez vous saisir d’autres éléments ? Tapez 1 si oui " )
Lire(Rep)
Jusqu’à (Rep ≠ 1)
Fin
79
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
Procedure Afficher(P: Pile)
Var P1: Pile
Début
CréerPile(P1)
{Affichage des éléments de la pile}
TantQue Non (PileVide(P)) Faire
Dépiler(P, V)
Ecrire( V, " - " )
Empiler(P1,V)
FinTantQue
….
80
Chapitre II: Les Files et Les Piles
Les Piles
Solution :
…
TantQue Non (PileVide(P1)) Faire
Dépiler(P1, V)
Empiler(P,V)
FinTantQue
Fin
Début {Programme principal}
Remplir(P)
Afficher(P)
Fin
81
