École Nationale d'Ingénieurs de Tunis
Université Tunis El Manar
COURS ALGORITHME.STRUCTURE DE
DONNÉES ET PROGRAMMATION
Chapitre 5
Piles et Files
Maroua Ben Slimane
[email protected] December 20, 2018
Plan
1
Introduction
Les Piles
Les Piles, pourquoi ?
Les Piles : Définition
Pile statique
Pile Dynamique
Les Files
Les files, pourquoi??
Les Files : Définition
File statique
File Dynamique
Exercices
Énoncé
Solution
Maroua Ben Slimane | Piles et Files
Introduction
2
I Les piles et les files ne sont pas de nouveaux types de données
mais plutôt une manière de gérer un ensemble de données.
I Elles sont très souvent utiles et servent, entre autres, à
mémoriser des évènements en attente de traitement.
I Il n’y a pas de structures spécifiques prévues dans les langages
de programmation pour les piles ou files.
I Il faut donc les créer de toute pièce sachant que la
représentation en mémoire de ces structures de données peut
être, selon le besoin:
I statique (utilisation des tableaux)
I dynamique (utilisation des listes).
Maroua Ben Slimane | Piles et Files
Les Piles, pourquoi ?
3
I Une pile sert essentiellement à stocker des données qui ne
peuvent pas être traitées immédiatement, car le programme a
une tâche plus urgente ou préalable à accomplir auparavant.
I En particulier les appels et retours de fonctions sont gérés
grâce à une pile appelée pile d’exécution.
I Les piles servent à revenir à l’état précédent et sont utilisées
pour:
I Recherche de chemins (labyrinthe)
I Gestion d’un historique de modifications (fonctions undo/redo)
I Gestion de la récursivité dans un langage (pile d’appels)
I etc.
Maroua Ben Slimane | Piles et Files
Les Piles : Définition
4
I Quand on vous dit pile penser directement à une pile d’assiettes
qu’il faut manipuler avec attention pour éviter les dégâts.
I Une pile est un ensemble de valeurs ne permettant des
insertions ou des suppressions qu’a une seule extrémité,
appelée sommet de la pile.
Maroua Ben Slimane | Piles et Files
Les Piles : Définition
5
I Empiler un objet sur une pile P consiste à insérer cet objet au
sommet de P (dans la pile d’assiettes une nouvelle assiette ne
peut être ajoutée qu’au dessus de celle qui se trouve au sommet)
I Dépiler un objet de P consiste à supprimer de P l’objet placé au
sommet (dans la pile d’assiettes seule peut être retirée celle qui
se trouve au sommet). L’objet dépilé est retourné comme résultat
du traitement.
I Une propriété remarquable des piles est qu’un objet ne peut être
dépilé qu’après avoir dépilé tous les objets qui sont placés "au
dessus" de lui, ce qui fait que les objets quittent la pile dans
l’ordre inverse de leur ordre d’arrivée.
Maroua Ben Slimane | Piles et Files
Les Piles : Définition
6
I Une pile est aussi appelée structure LIFO (Last In, First Out) ou
(dernier arrivé, premier sorti)
I le premier élément accessible est le dernier ajouté.
I On ne peut accéder qu’à l’élément placé au sommet de la pile.
Maroua Ben Slimane | Piles et Files
Les Piles : Définition
6
I Une pile est aussi appelée structure LIFO (Last In, First Out) ou
(dernier arrivé, premier sorti)
I le premier élément accessible est le dernier ajouté.
I On ne peut accéder qu’à l’élément placé au sommet de la pile.
Maroua Ben Slimane | Piles et Files
Les Piles : Définition
6
I Une pile est aussi appelée structure LIFO (Last In, First Out) ou
(dernier arrivé, premier sorti)
I le premier élément accessible est le dernier ajouté.
I On ne peut accéder qu’à l’élément placé au sommet de la pile.
Maroua Ben Slimane | Piles et Files
Les Piles : Définition
6
I Une pile est aussi appelée structure LIFO (Last In, First Out) ou
(dernier arrivé, premier sorti)
I le premier élément accessible est le dernier ajouté.
I On ne peut accéder qu’à l’élément placé au sommet de la pile.
Maroua Ben Slimane | Piles et Files
Les Piles : Définition
6
I Une pile est aussi appelée structure LIFO (Last In, First Out) ou
(dernier arrivé, premier sorti)
I le premier élément accessible est le dernier ajouté.
I On ne peut accéder qu’à l’élément placé au sommet de la pile.
Maroua Ben Slimane | Piles et Files
Les Piles : Définition
7
I En termes de programmation, une pile est un enregistrement
avec :
I Une structure de données pour enregistrées les valeurs (elle peut
être statique ou dynamique)
I Une variable sommet qui indique le sommet de la pile.
I On peut implémenter une pile dans un tableau (pile statique) ou
dans une liste chaînée (pile dynamique).
I Les opérations autorisées avec une pile sont :
I empiler, toujours au sommet, et jusqu’à la limite de la mémoire,
I dépiler, toujours au sommet, si la pile n’est pas vide,
I vérifier si la pile est vide ou non.
Maroua Ben Slimane | Piles et Files
Les Piles : Manipulation
8
La manipulation d’une pile revient à l’appel de fonctions et
procédures dites de bases définies une seule fois et utilisées autant
de fois qu’il est nécessaire.
Ces sous-algorithmes sont :
I Init_Pile : permet d’initialiser une pile à vide lors de sa création
I Pile_vide : pour vérifier si une pile est vide ou non et savoir alors
s’il reste des valeurs à traiter ou non
I Pile_pleine : pour vérifier s’il est possible de rajouter ou non un
nouveau élément (utilisée dans le seul cas des piles statiques)
I Empiler : permet d’ajouter une nouvelle valeur (envoyé en
paramètre par l’appelant) à la pile (au dessus du sommet et dans
le cas d’une pile non pleine)
I Depiler : permet de supprimer une valeur (se trouvant au
sommet de la pile) et de la renvoyer en paramètre. Cette
opération n’est possible que si la file n’est pas vide
Maroua Ben Slimane | Piles et Files
Pile statique : Définition
9
Une pile statique est un enregistrement à 2 cases :
I un tableau à hauteur maximale prévisible
I un indice entier qui pointe la dernière valeur ajoutée à la pile
(sommet).
Maroua Ben Slimane | Piles et Files
Pile statique : Déclaration
10
Constante
(N : entier) = . . . . ; /* taille du tableau*/
Type
Tab = Tableau de N Type_C { Type_C est le type des données
enregistrées dans la pile}
Pile = Enregistrement
T : Tab
Sommet : Entier
Fin Enregistrement
Note : Les données enregistrées dans la pile peuvent être des
entiers, des réels, des caractères, des chaînes de caractères, des
booléens, des tableaux, des pointeurs de listes ou encore des piles
ou files.
Maroua Ben Slimane | Piles et Files
Manipulation d’une pile Statique
11
Initialisation d’une pile
Procédure Init_Pile (Var P : Pile)
Début
P.Sommet ← 0
Fin
Vérification de pile vide
Fonction Pile_vide (P : Pile) : Booleen
Début
Si P.Sommet = 0 Alors
Pile_vide ← vrai
Sinon
Pile_vide ← faux
FinSi
Fin
Maroua Ben Slimane | Piles et Files
Manipulation d’une pile Statique
12
Vérification de pile pleine
Une autre façon plus compacte d’écrire cette fonction est la suivante :
Fonction Pile_pleine (P : Pile) : Booleen
Début
Pile_pleine ← P.Sommet = N
Fin
Ajout d’une nouvelle valeur à une pile
Procédure Empiler (Var P : Pile ; X : Type_C)
Début
Si Pile_pleine(P) Alors
Écrire("Impossible la pile est pleine")
Sinon
P.Sommet ← P.Sommet + 1
P.T [P.Sommet] ← X
FinSi
Fin
Maroua Ben Slimane | Piles et Files
Manipulation d’une pile Statique
13
Suppression d’une valeur de la pile
Procédure Depiler (Var P : Pile ; X : Type_C)
Début
Si Pile_vide(P) Alors
Écrire("Impossible la pile est vide")
Sinon
X ← P.T [P.Sommet]
P.Sommet ← P.Sommet − 1
FinSi
Fin
Maroua Ben Slimane | Piles et Files
Pile Dynamique : Définition
14
I Une pile dynamique est une liste à la quel on attache un
pointeur sommet.
I C’est un enregistrement à une seule case : pointeur qui pointe
la dernière valeur traitée dans la liste (sommet).
De même que pour les piles statiques nous présentons la déclaration
et les sous algorithmes de bases détaillés pour le type statique. Et
dans un souci d’uniformisation nous utilisons les mêmes noms mais
en ajoutant un D (pour rappeler Dynamique) à la fin de chaque nom
pour faire la différence.
Note : Il n’y a pas de pile pleine pour les piles dynamique. La seule
possibilité de ne pas pouvoir ajouter un élément c’est d’avoir une
mémoire pleine, cas que l’on ne prend pas en considération ici.
Maroua Ben Slimane | Piles et Files
Déclaration d’une pile dynamique
15
Type
Liste = ∗ Element
Elem = Enregistrement
Info : Type_C
Suivant : ∗ Element
Fin Enregistrement
PileD = Enregistrement
Sommet : Liste
Fin Enregistrement
Note : Les données enregistrées dans la pile peuvent être des
entiers, des réels, des caractères, des chaînes de caractères, des
booléens, des tableaux, des pointeurs de listes ou encore des piles
ou files.
Maroua Ben Slimane | Piles et Files
Exemple d’une pile dynamique
16
Maroua Ben Slimane | Piles et Files
Manipulation d’une pile dynamique
17
Initialisation d’une pile dynamique
Procédure Init_PileD (Var P : PileD)
Début
P.Sommet ← Nil
Fin
Vérification de pile vide dynamique
Fonction PileD_vide (P : PileD) : Booleen
Début
Si P.Sommet = Nil Alors
Pile_vide ← vrai
Sinon
Pile_vide ← faux
FinSi
Fin
Maroua Ben Slimane | Piles et Files
Manipulation d’une pile dynamique
18
Vérification de pile vide dynamique
Une autre façon plus compacte d’écrire cette fonction est la suivante :
Fonction Pile_videD (P : PileD) : Booleen
Début
Pile_videD ← P.Sommet = Nil
Fin
Note: Le nom de la fonction recevra le résultat de la comparaison
(vrai ou faux) entre le sommet et le Nil.
Maroua Ben Slimane | Piles et Files
Manipulation d’une pile dynamique
19
Ajout d’une nouvelle valeur à une pile dynamique
Procedure EmpilerD (Var P : PileD ; X : Type_C)
Var
Pt : Liste
Début
Allouer(Pt)
Pt ∗ .InfoX
Pt ∗ .Suivant ← P.Sommet
P.Sommet ← Pt
Fin
Note : L’ajout d’une valeur à une pile dynamique revient à une
insertion en début de liste si l’on considère que le sommet est la
tête de la liste.
Maroua Ben Slimane | Piles et Files
Manipulation d’une pile dynamique
20
Suppression d’une valeur de la pile dynamique
La suppression d’une valeur dans une pile dynamique revient à
effectuer une suppression physique d’un nœud (le premier de
liste) et à récupérer dans un paramètre, passé par variable, la
donnée enregistrée.
Procédure DepilerD (Var P : PileD, X : Type_C)
Var
Pt : Liste
Début
Si Pile_videD(P) Alors
Écrire("Impossible la pile est vide")
Sinon
Pt ← P.Sommet
X ← P.Sommet ∗ .Info
P.Sommet ← P.Sommet ∗ .Suiv
Liberer(Pt)
FinSi
Maroua Fin
Ben Slimane | Piles et Files
Les files, pourquoi??
21
Quelques exemples d’utilisation :
I File d’attente dans un magasin
I Gestion de stocks de denrées périssables
I Ordonnancement de processus
Maroua Ben Slimane | Piles et Files
Les Files, pourquoi ??
22
I Quand on vous dit file penser directement à une file d’attente
où chacun à son tour qu’il doit respecter.
I Une file est un ensemble de valeurs qui a un début (Debut) et
une fin (Queue).
Maroua Ben Slimane | Piles et Files
Les Files, pourquoi ??
23
I Enfiler un objet sur une file F consiste à insérer cet objet à la fin
de la file F (dans la file d’attente un nouvel arrivant se met à la
queue c.-à-d., après la personne arrivée juste avant lui)
I Défiler un objet de F consiste à supprimer de F l’objet placé en
début de file (dans la file d’attente seule peut être servie la
personne qui se trouve en début de file). L’objet défilé est
retourné comme résultat du traitement.
I Une file sert essentiellement à stocker des données qui doivent
être traitées selon leur ordre d’arrivée.
I L’exemple le plus connu est celui de l’impression de
documents reçus par une imprimante qui imprime le premier
document arrivé et termine par le dernier. Ce qui fait que les
objets quittent la file dans l’ordre de leur ordre d’arrivée. Pour
cette raison, une file est aussi appelée structure FIFO (First In,
First Out ou (premier arrivé, premier sorti)
Maroua Ben Slimane | Piles et Files
Les Files : Définition
24
I Une file est un conteneur d’éléments qui respecte le principe du
First In First Out (FIFO) : le premier élément accessible est le
premier ajouté.
Maroua Ben Slimane | Piles et Files
Les Files : Définition
24
I Une file est un conteneur d’éléments qui respecte le principe du
First In First Out (FIFO) : le premier élément accessible est le
premier ajouté.
Maroua Ben Slimane | Piles et Files
Les Files : Définition
24
I Une file est un conteneur d’éléments qui respecte le principe du
First In First Out (FIFO) : le premier élément accessible est le
premier ajouté.
Maroua Ben Slimane | Piles et Files
Les Files : Définition
24
I Une file est un conteneur d’éléments qui respecte le principe du
First In First Out (FIFO) : le premier élément accessible est le
premier ajouté.
Maroua Ben Slimane | Piles et Files
Les Files : Définition
24
I Une file est un conteneur d’éléments qui respecte le principe du
First In First Out (FIFO) : le premier élément accessible est le
premier ajouté.
Maroua Ben Slimane | Piles et Files
Les Files : Définition
25
En termes de programmation, une file est un enregistrement avec :
I Une structure de données pour enregistrées les valeurs (elle
peut être statique ou dynamique)
I Une variable Debut(ou tête) qui indique le premier élément de la
file.
I Une variable Queue qui indique le dernier élément de la file.
I Comme pour les piles, la manipulation d’une file revient à l’appel
de fonctions et procédures dites de bases définies une seule fois
et utilisées autant de fois qu’il est nécessaire.
Maroua Ben Slimane | Piles et Files
Les Files : Manipulation
26
Ces sous-algorithmes sont :
I Init_File : permet d’initialiser une file à vide lors de sa création
I File_vide : pour vérifier si une file est vide ou non et savoir alors
s’il reste des valeurs à traiter ou non
I File_pleine : pour vérifier s’il est possible de rajouter ou non un
nouveau élément (utilisée dans le seul cas des files statiques)
I Enfiler : permet d’ajouter une nouvelle valeur (envoyé en
paramètre par l’appelant) à la file (après le dernier élément de la
file qui se trouve au niveau de sa queue et dans le cas d’une file
non pleine)
I Defiler : permet de supprimer une valeur (se trouvant au début
de la file) et de la renvoyer en paramètre. Cette opération n’est
possible que si la file n’est pas vide.
Maroua Ben Slimane | Piles et Files
File statique
27
Définition
Une file statique est un enregistrement à 3 cases :
I un tableau à hauteur maximale prévisible
I un indice entier qui pointe le premier élément insérer dans la file
(Debut)
I un deuxième indice entier qui pointe la dernière valeur ajoutée
(Queue).
Exemples : Sachant que le tableau est indicé de 1 à N et pour une
gestion simpliste des files :
1. Une file a un seul élément → Debut = 1 et Queue = 1
2. Une file a 3 éléments → Debut = 1 et Queue = 3
3. Une file qui vient d’être déclarée (et non encore utilisée) →
Debut = 1 et Queue = 0
4. Une file complètement vidée → Debut = Queue +1
Maroua Ben Slimane | Piles et Files
File Statique : Déclaration
28
Constante
(N : entier)= . . . . { taille du tableau}
Type
Tab = Tableau de N Type_C { Type_C est le type des
données enregistrées dans la file}
File =Enregistrement
T : Tab
Debut, Queue : Entier
Fin Enregistrement
Maroua Ben Slimane | Piles et Files
File Statique : Déclaration
29
Note :
I Les données enregistrées dans la file peuvent être des entiers,
des réels, des caractères, des chaînes de caractères, des
booléens, des tableaux, des pointeurs de listes ou encore des
piles ou files.
I Dans certain langages de programmation le nom "File" désigne
un type de données appelé fichier. Dans ce cas ne pas utiliser
ce terme comme identifiant de la file.
Maroua Ben Slimane | Piles et Files
File Statique : Manipulation
30
Initialisation d’une file
Procédure Init_File (Var F : File)
Début
F .Debut ← 1
F .Queue ← 0
Fin
Vérification de File vide
Fonction File_vide (F : File) : Booleen
Début
Si F .Debut > F .Queue Alors
File_vide ← vrai
Sinon
File_vide ← faux
FinSi
Fin
Maroua Ben Slimane | Piles et Files
File Statique : Manipulation
31
Vérification de File vide
Une autre façon plus compacte d’écrire cette fonction est la suivante :
Fonction File_vide (F : File) : Booleen
Début
File_vide ← F .Debut > F .Queue
Fin
Le nom de la fonction recevra le résultat de la comparaison (vrai ou
faux) entre les indices début et Queue.
Maroua Ben Slimane | Piles et Files
File Statique : Manipulation
32
Vérification de File pleine
Fonction File_pleine (F : File) : Booleen
Début
Si (F .Queue = N) et (F .Debut < F .Queue) Alors
File_pleine ← vrai
Sinon
File_pleine ← faux
FinSi
Fin
Une autre façon plus compacte d’écrire cette fonction est la suivante :
Fonction File_pleine (F : File) : Booleen
Début
File_pleine ← (F .Queue = N) et (F .Debut < F .Queue)
Fin
Maroua Ben Slimane | Piles et Files
File Statique : Manipulation
33
Ajout d’une nouvelle valeur à une File
Procédure Enfiler (Var F : File ; X : Type_C)
Début
Si File_pleine(F) Alors
Écrire("Impossible la file est pleine")
Sinon
F .Queue ← F .Queue + 1
F .T (F .Queue) ← X
FinSi
Fin
Maroua Ben Slimane | Piles et Files
File Statique : Manipulation
34
Suppression d’une valeur de la File
Procédure DeFiler (Var F : File, X : Type_C)
Début
Si File_vide(F) Alors
Écrire("Impossible la File est vide")
Sinon
X ← F .T (F .Debut)
F .Debut ← F .Debut + 1
FinSi
Fin
Maroua Ben Slimane | Piles et Files
File Dynamique : Définition
35
Une File dynamique est une liste à la quel on attache deux (2)
pointeurs Debut et Queue.
C’est un enregistrement à deux cases :
I pointeur qui pointe le premier élément de la liste (Debut)
I pointeur qui pointe la dernière valeur ajoutée dans la liste
(Queue).
Exemples:
I Une file vide → Debut = Queue = Nil
I Une file a un seul élément → Debut = Queue 6= Nil
I Une file a plus d’un élément → Debut 6= Queue
Maroua Ben Slimane | Piles et Files
File Dynamique : Définition
36
I De même que pour les files statiques nous présentons la
déclaration et les sous algorithmes de bases détaillés pour le
type statique. Et dans un souci d’uniformisation nous utilisons
les mêmes noms mais en ajoutant un D (pour rappeler
Dynamique) à la fin de chaque nom pour faire la différence.
Note : Il n’y a pas de file pleine pour les files dynamique. La seule
possibilité de ne pas pouvoir ajouter un élément c’est d’avoir une
mémoire pleine, cas que l’on ne prend pas en considération ici.
Maroua Ben Slimane | Piles et Files
Déclaration d’une file dynamique
37
Type
Liste = ∗ Element
Element = Enregistrement
Info : Type_C
Suivant : *Element
Fin Enregistrement
FileD = Enregistrement
Debut, Queue : Liste
Fin
Maroua Ben Slimane | Piles et Files
Manipulation des Files Dynamiques
38
Initialisation d’une file dynamique
Procédure Init_FileD (F : FileD)
Début
F .Debut ← Nil
F .Queue ← Nil
Fin
Vérification de File vide dynamique
Fonction File_videD (F : FileD) : Booleen
Début
Si F. Queue = Nil Alors
File_videD ← vrai
Sinon
File_videD ← faux
FinSi
Fin
Maroua Ben Slimane | Piles et Files
Manipulation des Files Dynamiques
39
Vérification de File vide dynamique
Une autre façon plus compacte d’écrire cette fonction est la suivante :
Fonction File_videD (F : FileD) : Booleen
Début
File_videD ← F .Queue = Nil
Fin
Le nom de la fonction recevra le résultat de la comparaison (vrai ou
faux) entre la queue et le Nil.
Ajout d’une nouvelle valeur à une file dynamique
I L’ajout d’une valeur à une File dynamique revient à une insertion
à la fin de liste avec l’adresse du dernier élément dans Queue.
I Le cas d’un enfiler sur file vide nécessite l’initialisation du Debut
à l’adresse du nouveau nœud.
Maroua Ben Slimane | Piles et Files
Manipulation des Files Dynamiques
40
Ajout d’une nouvelle valeur à une file dynamique
Procédure EnfilerD (Var F : FileD ; X : Type_C)
Var
Pt : Liste
Début
Allouer(Pt)
Pt ∗ .Info ← X
Pt ∗ .Suiv ← Nil
Si File_videD(F) Alors
F .Debut ← Pt
Sinon
F .Queue∗ .Suiv ← Pt
FinSi
F .Queue ← Pt
Fin
Maroua Ben Slimane | Piles et Files
Manipulation des Files Dynamiques
41
Suppression d’une valeur de la file dynamique
I La suppression d’une valeur dans une file dynamique revient à
effectuer une suppression physique d’un nœud (le premier de
liste) et à récupérer dans un paramètre, passé par variable, la
donnée enregistrée.
Maroua Ben Slimane | Piles et Files
Manipulation des Files Dynamiques
42
Suppression d’une valeur de la file dynamique
Procédure DefilerD (Var F: FileD, X : Type_C)
Var
Pt : Liste
Début
Si File_videD(F) Alors
Écrire("Impossible la file est vide")
Sinon
Pt ← F .Debut
X ← F .Debut ∗ .Info
F .Debut ← F .Debut ∗ .Suiv
Si F. Debut = Nil Alors
F .Queue ← Nil
FinSi { si debut devient Nil cela veut dire que la file
a été vidée et Queue doit devenir Nil}
Liberer(Pt)
FinSi
Maroua Fin
Ben Slimane | Piles et Files
Exercices
43
Dans les exercices avec piles et files il est suffit de faire appel aux
sous algorithmes de base définis dans les sections précédentes.
Exercice 1 : Énoncé
Écrire une procédure afficherF1) qui affiche tous les éléments d’une
file de mots et une autre défilerJusquaF1, elt) qui défile la file
jusqu’à l’élément elt. L’élément elt n’est pas défilé. Si l’élément
n’appartient pas à la file, alors la fonction défile toute la file.
Exercice 2 : Énoncé
Écrire une procédure qui inverse une pile P1de réels. Doit-on utiliser
une pile ou une file ?
Pour inverser une pile on aurait besoin d’utiliser une file où l’on enfile
ce qui a été dépilé puis empilant à partir de la file les éléments seront
installés dans l’ordre inverse.
Maroua Ben Slimane | Piles et Files
Exercices
44
Exercice 3 : Énoncé
On se donne une pile P1 contenant des entiers positifs.
Écrire un algorithme pour déplacer les entiers de P1 dans une pile P2
de façon à avoir dans P2 tous les nombres pairs en dessus des
nombres impairs en gardant l’ordre d’apparition des nombre pairs et
en inversant l’ordre d’apparition des nombres impairs. Au retour à
l’algorithme appelant on doit retrouver P1 initiale.
Exercice Supplémentaire
1. Montrer comment implémenter une file en utilisant deux piles,
écrire les opérations enfiler, défiler de ce cas de figure.
2. Montrer comment implémenter une pile en utilisant deux files,
écrire les opérations empiler, dépiler de ce cas de figure.
Maroua Ben Slimane | Piles et Files
Exercice 1
45
Maroua Ben Slimane | Piles et Files
Si l’on considère que la file est dynamique il suffit de faire appelle aux
46
sous-algorithmes de base des files dynamiques comme suit :
Maroua Ben Slimane | Piles et Files
Exercice 1
47
Maroua Ben Slimane | Piles et Files
Exercice 2
48
Maroua Ben Slimane | Piles et Files
Exercice 3
49
Maroua Ben Slimane | Piles et Files