Les Piles et Files
CPGE Moulay Youssef
Rabat
MPSI
2024 / 2025
0 / 15
Introduction Les Piles Les Files
Plan
1 Introduction
2 Les Piles
3 Les Files
1 / 15
Les Piles et Files
Introduction Les Piles Les Files
Introduction
Nous avons vu quelques structures de données essentielles dans la programmation
en Python, qui seront utiles pour bien gérer, organiser et manipuler les données d’un
problème.
Parfois nous aurons besoin d’utiliser quelques types particuliers structures de
données, qui doivent respecter quelques restrictions dans l’ajout et la suppression.
Par exemple pour résoudre un problème lié aux files de priorité, on doit savoir
comment gérer l’ordre de traitement de chaque donnée.
Les Piles et Files seront très utiles dans certains problèmes de programmation.
Parmi les domaines d’application : Gestion de l’historique, piles d’exécution,
Algorithmes de parcours, Gestion des ressources, files d’attente, etc.
2 / 15
Les Piles et Files
Introduction Les Piles Les Files
Les Piles
Définition
Une PILE (en anglais : stack) est une liste linéaire dont une seule extrémité (le
sommet) est accessible (visible).
Les PILEs peuvent être considérées comme des listes avec des conditions d’utilisation
restreintes.
Les PILEs suivent une démarche LIFO (Last In First Out) ce qui signifie que les derniers
éléments ajoutés à la pile seront les premiers à être récupérés.
3 / 15
Les Piles et Files
Introduction Les Piles Les Files
Opérations sur les Piles
La pile est un objet dynamique. Son état ( surtout sa taille) est variable. L’extraction ou
l’ajout se font toujours au sommet de la pile.
On peut définir les Piles sous forme de classes, listes chainées, ou tout simplement avec les
listes que vous connaissez en respectant le principe.
Opérations fondamentales sur les Piles :
Empiler (push) : Ajouter un élément au sommet.
Dépiler (pop) : Retirer l’élément au sommet.
Sommet : Consulter l’élément au sommet sans le retirer.
Tester si vide (isEmpty) : Vérifier si la pile est vide.
4 / 15
Les Piles et Files
Introduction Les Piles Les Files
Opérations sur les Piles
Exemples :
Une pile d’assiette. Lorsqu’on ajoute une assiette en haut de la pile, on retire toujours
celle qui se trouve en haut de la pile : c’est à dire celle qui a été ajoutée en dernier,
sinon tout le reste s’écroule.
Les piles peuvent être utilisées dans des algorithmes d’évaluation des expressions
mathématiques.
En général, Chaque problème qui utilise cette démarche peut être simulé (dans sa
résolution) par les piles.
5 / 15
Les Piles et Files
Introduction Les Piles Les Files
Opérations sur les Piles
Exercice :
En utilisant une pile sous forme de liste, créez des fonctions qui implémentent les
opérations élémentaires sur les Piles.
empiler(pile, element) , depiler(pile) , taille(pile) , sommet(pile) , est_vide(pile)
6 / 15
Les Piles et Files
Introduction Les Piles Les Files
1 # Pile implementee avec une liste
2 pile = []
1 # Verifier si la pile est vide
2 def est_vide ( pile ) :
3 return len ( pile ) == 0
1 # Ajouter un element ( push )
2 def empiler ( pile , element ) :
3 pile . append ( element )
1 # Retirer un element ( pop )
2 def depiler ( pile ) :
3 if not est_vide ( pile ) :
4 return pile . pop ()
5 return " Pile vide "
7 / 15
Les Piles et Files
Introduction Les Piles Les Files
1 # La taille de la pile
2 def taille ( pile ) :
3 return len ( pile )
2 # Consulter le sommet
3 def sommet ( pile ) :
4 if not est_vide ( pile ) :
5 return pile [ -1]
6 return " Pile vide "
8 / 15
Les Piles et Files
Introduction Les Piles Les Files
Les Files
Définition
Une FILE est une liste linéaire où toutes les insertions se font par une extrémité
(queue,arrière), les extractions se font par l ’autre extrémité (avant, tête).
Les PILEs suivent une démarche FIFO (First In First Out), le premier arrivé est le premier
servi.
9 / 15
Les Piles et Files
Introduction Les Piles Les Files
Opérations sur les Files
En général on implémente une file sous forme d’une liste, où une liste à deux extrémités
(deque).
Ajouter ou retirer des éléments des deux extrémités peut être en FIFO, ou parfois selon
une priorité plutôt que l’ordre d’arrivée.
Opérations fondamentales sur les Files :
Enfiler (enqueue) : Ajouter un élément à la fin.
Défiler (dequeue) : Retirer l’élément au début.
Premier (front) : Consulter l’élément au début sans le retirer.
Tester si vide (isEmpty) : Vérifier si la file est vide.
10 / 15
Les Piles et Files
Introduction Les Piles Les Files
Exemples :
On peut gérer une file d’attente où les clients arrivent et partent selon l’ordre
d’arrivée.
Serveur de traitement. Les tâches sont envoyées à un serveur, qui les traite dans
l’ordre où elles arrivent.
Un ascenseur. Les étages à visiter sont traités dans l’ordre où ils ont été demandés.
11 / 15
Les Piles et Files
Introduction Les Piles Les Files
Exercice :
En utilisant une file sous forme de liste, créez des fonctions qui implémentent les
opérations élémentaires sur les files.
enfiler(file, element) , défiler(file) , taille(file) , premier(file) , est_vide(file)
12 / 15
Les Piles et Files
Introduction Les Piles Les Files
1 # Initialiser une file vide
2 file = []
1 # Verifier si la file est vide
2 def est_vide ( file ) :
3 return len ( file ) == 0
1 # Enfiler un element
2 def enfiler ( file , element ) :
3 file . append ( element )
1 # Defiler un element
2 def defiler ( file ) :
3 if est_vide ( file ) :
4 return " La file est vide "
5 return file . pop (0) # Retire le premier element
13 / 15
Les Piles et Files
Introduction Les Piles Les Files
1 # Obtenir le premier element
2 def premier ( file ) :
3 if est_vide ( file ) :
4 return " La file est vide "
5 return file [0]
1 # Exemple d ' utilisation
2 enfiler ( file , 1)
3 enfiler ( file , 2)
4 enfiler ( file , 3)
5 print ( premier ( file ) ) # Affiche 1
6 print ( defiler ( file ) ) # Retire et affiche 1
7 print ( file ) # Affiche [2 , 3]
14 / 15
Les Piles et Files
Introduction Les Piles Les Files
Le module [Link] de Pyhton
Même si on peut utiliser facilement les listes pour implémenter les piles et files. Parfois on
peut se servir du module collections offert par Python.
Ce module possède une classe des listes particulières, offrant des méthodes pour
ajouter/supprimer aux début et à la fin de la liste.
La classe deque (double-ended queue) du module collections rend les opérations d’ajout
et de suppression aux extrémités plus rapides.
1 from collections import deque
1 d = deque ([1 , 2 , 3]) # Creer un deque
1 d . append (4) # Ajoute a la fin
2 d . appendleft (8) # Ajoute au debut
1 d . pop () ) # Supprimer de la fin
2 d . popleft () # Supprimer du debut
15 / 15
Les Piles et Files