Les Piles et les Files
Introduction Les Piles Les Files
Introduction
1/11
Les Piles et les Files
Introduction Les Piles Les Files
Introduction
Les piles et les files font partie de la grande famille des structures de
données. Rappel : une structure de données est une structure logique
destinée à contenir des données, afin de leur donner une organisation
permettant de simplifier leur traitement.
Toutes les structures de données vu au cours ont leur propre logique,
leur propre manière de fonctionner et leurs propres avantages et
inconvénients. Les piles et les files ont un fonctionnement assez
proche des listes, au point qu’en Python, on les codera . . . à l’aide des
listes.
2/11
Les Piles et les Files
Introduction Les Piles Les Files
Les Piles
3/11
Les Piles et les Files
Introduction Les Piles Les Files
Définition
Définition :
Une pile est une structure de données qui suit le principe LIFO (Last
In First Out : le dernier rentré sera le premier à sortir).
On retrouve dans les piles une partie des propriétés des listes. Dans
les piles, il est uniquement possible de manipuler le dernier élément
introduit dans la pile.
On prend souvent l’analogie avec une pile d’assiettes : dans une pile
d’assiettes la seule assiette directement accessible et la dernière
assiette qui a été déposée sur la pile.
4/11
Les Piles et les Files
Introduction Les Piles Les Files
Opérations sur les piles
Le dernier élément de la pile est appelé le sommet de la pile.
On utilise les listes pour manipuler les piles, et les opérations que l’on
peut faire avec une pile sont les suivantes :
creer_pile() : pour créer une pile vide.
on peut savoir si une pile est vide (est_vide(p)).
on peut empiler un nouvel élément et qui devient le sommet de
la pile (empiler(p,e)).
on peut dépiler un élément de la pile : Cela signifie supprimer et
renvoyer l’élément au sommet de la pile (depiler(p)).
on peut accéder à l’élément situé au sommet de la pile sans le
supprimer de la pile (sommet(p)).
on peut connaitre le nombre d’éléments présents dans la pile
(taille(p)).
5/11
Les Piles et les Files
Introduction Les Piles Les Files
Exemples :
Soit une pile P composée des éléments suivants : 2, 3, 10, 19 et 22 (le
sommet de la pile est 22) Pour chaque exemple ci-dessous on repart
de la pile d’origine ( c’est-à-dire on le réinitialise dans chaque
exemple) :
depiler(P) renvoie 22 et la pile P devient : 2, 3, 10 et 19 (le
sommet de la pile devient 19).
empiler(P,42) la pile P est maintenant composée des éléments
suivants : 2, 3, 10, 19, 22 et 42.
sommet(P) renvoie 22, la pile P n’est pas modifiée.
Si on applique depiler(P) 5 fois de suite, est_vide(P) renvoie
True.
Après avoir appliqué depiler(P) une seule fois, taille(P) renvoie 4.
6/11
Les Piles et les Files
Introduction Les Piles Les Files
Les Files
7/11
Les Piles et les Files
Introduction Les Piles Les Files
Définition
Les files sont des structures de données fondées sur le principe du «
premier arrivé, premier sorti » : elles sont dites de type FIFO (First
In, First Out). C’est similaire au principe de la file d’attente devant un
guichet ou une caisse.
8/11
Les Piles et les Files
Introduction Les Piles Les Files
Définition
Les files sont des structures de données fondées sur le principe du «
premier arrivé, premier sorti » : elles sont dites de type FIFO (First
In, First Out). C’est similaire au principe de la file d’attente devant un
guichet ou une caisse.
On insère les nouveaux éléments à la fin (i.e la queue de la file) et
l’opération est dite enfiler.
et on enlève les éléments au début (tête de file) et on dit qu’on
défile.
9/11
Les Piles et les Files
Introduction Les Piles Les Files
Opérations sur les files
Comme dans les piles, il y a des opérations fondamentales
caractérisant les files :
creer_file() : pour créer une file vide.
on peut savoir si une file est vide (file_vide(F)).
on peut enfiler un nouvel élément à la queue (enfiler(F,e)).
on peut défiler un élément de la tête de la file (defiler(F)).
on peut accéder à la tête et la queue de la file sans la modifier.
on peut connaitre le nombre d’éléments présents dans la file
(taille(F)).
Exercice : Implémenter en Python les opérations de bases
utilisées pour manipuler les files(utiliser des fonctions).
10/11
Les Piles et les Files
Introduction Les Piles Les Files
Exemples :
En Python, les files peuvent toutes être simulées avec des listes. Pour
ajouter un élément à la fin de la file, on utilise append(). Pour
récupérer un élément de la tête de la file, on utilise pop(0) avec 0 pour
indice.
11/11
Les Piles et les Files
