Groupe des étudiants : JM2 ISEN
Structures de données
en Python
(Piles, Files, Deque)
Simohamed H.
Numéro de bureau : A34
10/12/2021 1 Structures de Données ~ Python [Link]@[Link]
Piles
10/12/2021 2 Structures de Données ~ Python [Link]@[Link]
Piles
Définition
▪ Une pile (stack) est une structure de données dans laquelle les éléments
sont ajoutés et supprimés suivant le principe dernier élément entré,
premier sorti (LIFO : Last In, First Out)
▪ Une pile est manipulée par une seule extrémité : le sommet (top)
10/12/2021 3 Structures de Données ~ Python [Link]@[Link]
Piles
Opérations
▪ Les opérations sur une pile sont :
a. Empiler (push) : ajoute l'élément au sommet de la pile
b. Dépiler (pop) : retire et renvoie le sommet de la pile
10/12/2021 4 Structures de Données ~ Python [Link]@[Link]
Piles
Opérations
▪ Les opérations sur une pile sont :
a. Empiler (push) : ajoute l'élément au sommet de la pile
b. Dépiler (pop) : retire et renvoie le sommet de la pile
▪ Exemple :
10/12/2021 5 Structures de Données ~ Python [Link]@[Link]
Piles
Les piles en Python
▪ Manipulation des piles en se basant sur le principe des listes
10/12/2021 6 Structures de Données ~ Python [Link]@[Link]
Piles
Applications
▪ Forward-backward dans les navigateurs web
• Les navigateurs web stockent les nouveaux sites visités dans une pile
• En ouvrant une page web, son adresse est empilée dans une pile
• En cliquant sur "Afficher la page précédente", l'adresse courante est dépilée
▪ Redo-undo dans les éditeurs de texte ...
▪ Vérification de l'ouverture/fermeture des parenthèses/accolades/crochets
dans un code informatique (tâche réalisée par le compilateur)
10/12/2021 7 Structures de Données ~ Python [Link]@[Link]
Files
10/12/2021 8 Structures de Données ~ Python [Link]@[Link]
Files
Définition
▪ Une file (queue) est une structure de données dans laquelle les élément
sont ajoutés et supprimés suivant le principe premier élément entré,
premier sorti (FIFO : First In, First Out)
▪ Une file est manipulée par ses deux extrémités : l'avant et l'arrière
10/12/2021 9 Structures de Données ~ Python [Link]@[Link]
Files
Opérations
▪ Les opérations sur une file sont :
a. Enfiler (enqueue) : ajoute l'élément à l'arrière de la file
b. Défiler (dequeue) : retire et renvoie l'élément à l'avant de la file
10/12/2021 10 Structures de Données ~ Python [Link]@[Link]
Files
Opérations
▪ Les opérations sur une file sont :
a. Enfiler (enqueue) : ajoute l'élément à l'arrière de la file
b. Défiler (dequeue) : retire et renvoie l'élément à l'avant de la file
▪ Exemple :
10/12/2021 11 Structures de Données ~ Python [Link]@[Link]
Piles
Les files en Python
1. Utilisation des listes
• la suppression en fin de liste est rapide
• l'insertion en début de liste est lente
2. Utilisation de la classe deque du module collections
10/12/2021 12 Structures de Données ~ Python [Link]@[Link]
Piles
Applications
▪ Gestion de l'impression dans une imprimante
▪ Ordre de l'exécution du processeur (CPU)
▪ Vie quotidienne
10/12/2021 13 Structures de Données ~ Python [Link]@[Link]
Deque
10/12/2021 14 Structures de Données ~ Python [Link]@[Link]
Deque
Définition
▪ Une deque* (double-ended queue) est une généralisation des piles et files
• on peut ajouter et retirer les éléments par les deux bouts (avant et arrière)
• = une file à double entrée
* ça se prononce "dèque"
10/12/2021 15 Structures de Données ~ Python [Link]@[Link]
Deque
Opérations
▪ Les opération sur une deque sont :
a. Insertion en avant
b. Insertion en arrière
c. Suppression en avant
d. Suppression en arrière
c. a.
b. d.
10/12/2021 16 Structures de Données ~ Python [Link]@[Link]
Deque
Opérations
▪ Les opération sur une deque sont :
a. Insertion en avant
b. Insertion en arrière
c. Suppression en avant
d. Suppression en arrière
c. a. Pile
b. d.
10/12/2021 17 Structures de Données ~ Python [Link]@[Link]
Deque
Opérations
▪ Les opération sur une deque sont :
a. Insertion en avant
b. Insertion en arrière
c. Suppression en avant
d. Suppression en arrière
c. a.
File
b. d.
10/12/2021 18 Structures de Données ~ Python [Link]@[Link]
Deque
Opérations
▪ Les opération sur une deque sont :
a. Insertion en avant
b. Insertion en arrière
c. Suppression en avant
d. Suppression en arrière
c. a.
b. d. Spécifique au Deque
10/12/2021 19 Structures de Données ~ Python [Link]@[Link]
Deque
Opérations
▪ Les opération sur une deque sont :
a. Insertion en avant (add_first)
b. Insertion en arrière (add_last)
c. Suppression en avant (delete_first)
d. Suppression en arrière (delete_last)
Source : Data Structures &
Algorithms in Python, M.T.
Goodrich, R. Tamassia, M. H.
GOLDWASSER
10/12/2021 20 Structures de Données ~ Python [Link]@[Link]
Deque
Les deques en Python
1. Utilisation des listes
• la suppression en fin de liste est rapide
• l'insertion en début de liste est lente
2. Utilisation de la classe deque du module collections (pareil que les files)
10/12/2021 21 Structures de Données ~ Python [Link]@[Link]
Synthèse :
Pile VS File VS Deque
10/12/2021 22 Structures de Données ~ Python [Link]@[Link]
Synthèse
Pile VS File VS Deque
Pile : File : Deque :
- manipulation (empiler/dépiler) - manipulation depuis l'avant - manipulation depuis l'avant
depuis le sommet (défiler) et l'arrière (enfiler) (ajouter/supprimer) et
- LIFO - FIFO l'arrière (ajouter/supprimer)
10/12/2021 23 Structures de Données ~ Python [Link]@[Link]
