Module : Structures de données et programmation
C++
Élément 1: Structures de données
Filières : GI, IDS Semestre 2
Année Universitaire 2023-2024
Pr. Rachid AIT DAOUD
Chapitre 3: Les piles et les files
2
Plan
Introduction
Les piles
Définitions
Opérations sur les piles
Les files
Définitions
Opérations sur les files
3
Introduction
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.
Elles sont très souvent utiles et servent, entre autres, à mémoriser des évènements
en attente de traitement.
Elles utilisent une structure de liste chainée pour rassembler les éléments.
Les piles et les files sont deux variantes un peu particulières des listes chaînées.
Elles permettent de contrôler la manière dont sont ajoutés les nouveaux éléments
(Ajout au début ou à la fin).
Les piles et les files sont donc très utiles pour des programmes qui doivent traiter
des données qui arrivent au fur et à mesure.
4
1. Les piles
Quand on vous dit pile penser directement à une pile d’assiettes ou pile de pièces
qu’il faut manipuler avec attention pour éviter les dégâts.
Sommet
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.
5
1. Les piles
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).
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.
6
1. Les piles
Définition:
Une pile (stack en anglais) est une structure dynamique dans laquelle dépilement
l'insertion ou la suppression d'un élément s‘effectue toujours à partir de la empilement
même extrémité de cette structure. Cette extrémité est appelée le sommet
de la pile.
En d’autres termes: sommet
Une pile est un contenant pour des éléments insérés et retirés
selon le principe dernier entré, premier sorti (LIFO: Last-In, First
Out).
Les éléments peuvent être insérés à tout moment, mais
seulement le dernier (le plus récemment inséré) peut être retiré.
Insérer un élément correspond à empiler l’élément (pushing).
Dépiler la pile (popping) correspond au retrait d’un élément. Pile
7
1. Les piles
Les principales fonctions:
En termes de programmation, une pile est un enregistrement avec : empilement dépilement
1. Une structure de données pour enregistrées les valeurs
(elle peut être statique ou dynamique).
2. Une variable sommet qui indique le sommet de la pile.
La manipulation d’une pile revient à l’appel de fonctions et procédures dites sommet
de bases définies une seule fois et utilisées autant de fois qu’il est nécessaire.
Les principales fonctions/Procédures associées aux piles sont:
Empiler(): Permet d’ajouter un nouvel élément à la pile (au dessus du sommet et
dans le cas d’une pile non pleine) ;
Depiler(): Permet de retirer une valeur (se trouvant au sommet de la pile). Cette
opération n’est possible que si la file n’est pas vide.
GetVal(): Retourner le sommet de la pile.
Pile
Pile_vide(): pour vérifier si une pile est vide ou non et savoir alors s’il reste des
valeurs à traiter ou non.
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) ; 8
1. Les piles
Exemple de pile
Une pile contenant Après l’empilement de Après l’empilement de Après un dépilement
3 éléments 13 21
sommet 21
sommet 13 13 sommet 13
sommet 17 17 17 17
10 10 10 10
7 7 7 7
Pile Pile Pile Pile
9
1. Les piles
Utilisation
De nombreuse applications s’appuient sur l’utilisation d’une pile, on peut citer:
Dans un navigateur web, une pile sert à mémoriser les pages Web visitées.
L'adresse de chaque nouvelle page visitée est empilée et l'utilisateur dépile
l'adresse de la page précédente en cliquant le bouton précédent.
La fonction « Annuler la frappe » (en anglais « Undo ») d'un traitement de
texte mémorise les modifications apportées au texte dans une pile. Vous pouvez
donc parcourir la pile des opérations pour vous retrouver à tel moment précis
de votre édition.
Appel des fonctions d’un programme lors de l’utilisations des fonctions
imbriquées.
Pour « retenir » l'ordre dans lequel les fonctions ont été appelées, l’ordinateur
crée une pile de ces fonctions au fur et à mesure.
10
1. Les piles
Représentation d’une pile
indice 0 1 2 3 4 5
Représentation contiguë (par tableau) :
o Les éléments de la pile sont rangés dans un tableau (les éléments sont
adjacents)
o Un entier représente la position du sommet de la pile
Représentation chaînée (par pointeurs) :
o Les éléments de la pile sont chaînés entre eux par un pointeur.
o Un pointeur sur le premier élément désigne la pile et représente le
sommet de cette pile.
o Une pile vide est représentée par le pointeur NULL.
Liste simplement chainée 17 @1 14 @2 107 @3 9 NULL
11
1. Les piles
Représentation par une liste chainée
Implémentation en C
valeur
next
sommet
7 702 Last in
Chaque élément de la pile aura une structure identique à celle 703
d’une liste chainée:
5 701
cellule/élément 3 700
1 First in
700
Pile
12
1. Les piles
Représentation par une liste chainée
Implémentation en C
LA PILE
Empiler() Depiler() PileVide () GetVal() PilePleine ()
Utilisée dans le cas où la pile a une taille fixe
13
1. Les piles
Représentation par une liste chainée
empilement
Implémentation en C
Empiler: Ajout un nouveau élément au sommet de la pile. sommet
Pile
14
1. Les piles
Représentation par une liste chainée
Implémentation en C dépilement
Dépiler: Retirer le sommet
temp 104
104
sommet 104 sommet
104
103
temp
104 103 103
102 102
101 101
100 100
Pile NULL Pile NULL
15
1. Les piles
Représentation par une liste chainée
Implémentation en C
valeur
next
sommet
GetVal: Retourner le contenu du sommet de la pile:
703 7 702 Last in
5 701
// la valeur 7 cellule/élément 3 700
1
700
Pile
16
1. Les piles
Implémentation en C
Fonction principale main()
17
Les files
Définitions
Opérations sur les files
18
2. Les files
Quand on vous dit file penser directement à une file d’attente où chacun à son tour
qu’il doit respecter.
Une file est un ensemble de valeurs qui a un début (Debut) et une fin (Queue).
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) ;
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.
19
2. Les files
Définition:
Une File (queue en anglais ) est une structure de données dans laquelle l'insertion se fait à la fin et la
suppression d'un élément s'effectue à partir de début de cette structure.
Le fonctionnement ressemble à une file d'attente: les premières personnes arrivées, se sont les premières
personnes à servir.
20
2. Les files
Principe de fonctionnement:
Un élément ne peut être ajouté qu’à la queue de la file.
Un élément ne peut être retiré qu’à la tête de la file.
Il s’agit donc, d’une structure de type FIFO (FIFO: First In, First Out). "Le premier qui
arrive est le premier à sortir".
Les données sont retirées dans l’ordre où elles ont été ajoutées.
Insérer un élément correspond à enfiler l’élément. Défiler la file correspond au retrait de
l’élément situé au début de la file.
En C, une file est une liste chaînée où chaque élément pointe vers le suivant, tout comme
les piles. Le dernier élément de la file pointe vers NULL
21
2. Les files
Exemple de file:
queue tete
Une file contenant 3 éléments CC BB AA
queue tete
Après l’enfilement de DD DD CC BB AA
enfiler
queue tete
Après l’enfilement de EE EE DD CC BB AA
enfiler
queue tete
Après un défilement EE DD CC BB défiler
queue tete
Après un 2ème défilement EE DD CC
défiler
22
2. Les files
Utilisation:
En général, on utilise des files pour mémoriser temporairement des
transactions qui doivent attendre pour être traitées.
Les serveurs d'impression, qui doivent traiter les requêtes dans l'ordre
dans lequel elles arrivent, et les insèrent dans une file d'attente ( ou une
queue).
Ordonnanceur de tâches du système d’exploitation (file d’exécution des
tâches, sans en privilégier aucune).
Construire des systèmes de réservation.
Le routage de paquets réseau.
23
2. Les files
Représentation d’une file
indice 0 1 2 3 4 5
Représentation contiguë (par tableau) :
o Les éléments de la file sont rangés dans un tableau. tete queue
o Deux entiers représentent respectivement les positions de la tête et de la queue de la file
Représentation chaînée (par pointeurs) :
o Les éléments de la file sont chaînés entre eux par pointeurs.
o Un pointeur sur le premier élément désigne la file et représente la tête de cette file.
o Un pointeur sur le dernier élément représente la queue de file.
o Une file vide est représentée par le pointeur NULL.
Liste simplement chainée first last
tete 17 @1 14 @2 107 @3 9 NULL queue
24
2. Les files
Représentation par une liste chainée
Implémentation en C
Afin de présenter une file par une liste chainée, nous allons besoin de définir deux structures:
Une structure cellule_file qui représente un élément de la file.
Une structure file qui représente la file.
Une file vide --> tete = queue = NULL
Une file a un seul élément --> tete = queue ≠ NULL
Une file a plus d’un élément --> tete ≠ queue
tete queue
17 @1 14 @2 9 NULL
enfiler
défiler 25
2. Les files
Représentation par une liste chainée
Implémentation en C
Déclaration d’une file:
----------------------Statique------------------------
F
struct file F; tete queue
F.tete = NULL; NULL NULL
F.queue = NULL;
Une file vide --> tete = queue = NULL
26
2. Les files
Représentation par une liste chainée
Implémentation en C
Déclaration d’une file:
----------------------Dynamique-----------------------
F
struct file *F = NULL; La file n’est pas encore
NULL
créée (n’existe plus dans la
@700 mémoire), on a juste un
pointeur qui va recevoir
l’adresse d’une file.
27
2. Les files
Représentation par une liste chainée
Implémentation en C
Déclaration d’une file:
----------------------Dynamique-----------------------
F
struct file *F = NULL; 740
F = malloc(sizeof(struct file);
*F @700
Allocation de mémoire par malloc, tete queue
et affectation de l’adresse de la file
vers le pointeur F.
F->tete = NULL; @740
F->queue = NULL;
28
2. Les files
Représentation par une liste chainée
Implémentation en C
Déclaration d’une file:
Déclaration statique: Déclaration dynamique:
F F (*F)
tete queue tete queue
@600
@700 @702 @700 @702
@550 @600
7 701 99 702 -4 NULL 7 701 99 702 -4 NULL
@700 @701 @702 @700 @701 @702
29
2. Les files
Représentation par une liste chainée
Implémentation en C
LA FILE
Enfiler() Defiler() FileVide () GetVal() FilePleine ()
Liste des fonctions/procédures autorisées pour la manipulation d’une file.
Utilisée dans le cas où la file a une taille fixe
30
2. Les files
Représentation par une liste chainée
Implémentation en C
Enfiler: Ajout un nouveau élément au queue de la file.
Deux cas de figure:
1. File vide F->tete == NULL
2. File non vide F->tete != NULL
//Ancienne dernière cellule
D
31
2. Les files
Représentation par une liste chainée
Implémentation en C
Défiler: Retirer un élément
Trois cas de figure se présentent:
1. File vide F->tete == NULL
2. File contient seul élement F->tete == F->queue
3. File contient plusieur élements F->tete != F->queue
32
