Chapitre 8 : Structures de données

abstraites en python
Mme. S. Darragi & M. A. Ammar : Classes Spè 15 mai 2023

Table des matières

1 Introduction 2

2 La notion de pile 2
2.1 Principales fonctions associées . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Applications en informatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 La notion de file 3
3.1 Principales fonctions associées . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Applications en informatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4 Comment procéder avec le langage Python ? 4

5 Piles vs files : synthèse 5

Page 1
1 Introduction

Les listes, les piles (stack en anglais) et les files (queue en anglais) sont des structures
abstraites de données fondamentales en informatique. Elles diffèrent par les conditions d’ajout
et d’accès aux éléments qui les constituent.

2 La notion de pile

Les piles sont fondées sur le principe du "der-

nier arrivé, premier sorti" ; on les dit de type
LIFO (Last In, First Out). C’est le principe même
de la pile d’assiettes : c’est la dernière assiette
posée sur la pile d’assiettes sales qui sera la
première lavée.
Figure 1 – Pile d’assiettes.
La pile ("stack" en anglais) est une structure de données que ne permet que deux opérations :
• Empiler un élément, qui consiste à ajouter un élément en haut de la pile.
• Dépiler un élément, qui consiste à retirer un élément empilé et à lire son contenu.

2.1 Principales fonctions associées

Pile vide Pile non vide

v2 sommet

Pour utiliser une pile, il suffit de savoir : v1

[] [v1, v2]
• Créer une pile (initialement vide).
Empiler v3 v3 = dépiler
• Empiler un élément (en anglais push). v3
• Dépiler un élément (en anglais pop). v2 v2 v2
v1 v1 v1

Figure 2 – Structure d’une pile.

Remarque
en informatique, un dépassement de pile ou débordement de pile (en anglais, stack
overflow) est un bug causé par un processus qui, lors de l’écriture dans une pile, écrit à
l’extérieur de l’espace alloué à la pile, écrasant ainsi des informations nécessaires au pro-
cessus. Stack Overflow est aussi connu comme étant un site web proposant des questions
et réponses sous la forme d’un forum d’entre-aide sur un large choix de thèmes concer-
nant la programmation informatique. Il y a de forte chance que vous trouviez la réponse à
un problème informatique même ardu sur Stack Overflow !

Page 2
2.2 Applications en informatique

De nombreuses applications s’appuient sur l’utilisation d’une pile. En voici quelques-unes :

• 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 sur le bouton "Afficher la page précédente".
• l’évaluation des expressions mathématiques en notation post-fixée (ou polonaise in-
verse) utilise une pile ;
• la fonction "Annuler la frappe" (Undo en anglais) d’un traitement de texte mémorise les
modification apportées au texte dans une pile ;
• la récursivité (une fonction qui fait appel à elle-même) utilise également une pile ;
• etc. . .

3 La notion de file

Les files sont fondées sur le principe du "pre-

mier arrivé, premier sorti" ; on les dit de type
FIFO (First In, First Out). C’est le principe de la
file d’attente devant un guichet.

Figure 3 – File d’attente.

La file ("queue" en anglais) est une structure de données que ne permet que deux opérations :
• Entrer une valeur (Enfiler).
• Sortir une valeur (Défiler).

3.1 Principales fonctions associées

Pour utiliser une file, il suffit de savoir :

• Créer une file (initialement vide).
• Enfiler un élément (en anglais enqueue).
• Défiler un élément (en anglais dequeue).

queue tête
file vide v3 v2 v1 file non vide

[] [v1, v2, v3]

v2 v1 v3 v2 v1 v3 v2
entrer v3 v1 = sortir

Figure 4 – Structure d’une file.

Page 3
3.2 Applications en informatique

En général, on utilise une file pour mémoriser temporairement des transactions qui doivent
attendre pour être traitées.
Voici quelques exemples d’applications :
• les serveurs d’impression, qui doivent traiter des requêtes dans l’ordre dans lequel elles
arrivent, et les insère dans une file d’attente (ou une queue) ;
• les requêtes entre machines sur un réseau ;
• certains moteurs multi-tâches, dans un système d’exploitation, qui doivent accorder du
temps machine à chaque tâche, sans en privilégier une plus qu’une autre ;
• on utilise des files pour créer toutes sortes de mémoires tampons (buffers en anglais) ;
• etc. . .

4 Comment procéder avec le langage Python ?

En natif, le type liste intègre déjà toutes les méthodes pour réaliser ces deux structures de
données, si L est un objet de type liste :
• [Link](x) ajoute un élément xà la fin de la liste ;
• [Link](i, x) insère un élément à la position indiquée. Le premier argument est la po-
sition de l’élément courant avant lequel l’insertion doit s’effectuer, donc [Link](0, x)
insère l’élément en tête de la liste, et [Link](len(L), x) est équivalent à [Link](x) ;
• [Link](x) : ajoute a à la fin de la liste ;
• [Link](x) qui supprime de la liste le premier élément dont la valeur est x. Une excep-
tion est levée s’il existe aucun élément avec cette valeur ;
• [Link](i), enlève de la liste l’élément situé à la position indiquée, et le retourne. Si aucune
position n’est indiqué, [Link]() enlève et retourne le dernier élément de la liste.

Bon à savoir : Il existe le module collections dans python qui offre la classe deque (double
ended queue) permettant de modéliser les files en permettant les accès à droite et à gauche de
la file, cette classe a été conçue pour fournir des opérations d’ajouts et de retraits rapides aux
deux extrémités. Les méthodes prédéfinies pour la classe deque sont principalement :
• file=[Link]([]) création d’une file vide ou [Link]([],3) créa-
tion d’une file avec taille prédéfinie (file bornée) ;
• len(file) retourne la taille de la file
• [Link](x) ajoute un élément text à la fin de la file ;
• [Link](y) insère un élément y au début de la file ;
• [Link]() supprime le dernier élément de la file ;
• [Link]() supprime le premier élément de la file ;
• [Link]() supprime tous les éléments de la file
• [Link](val) donne le nombre d’occurrence d’une valeur dans file ;
• [Link](L1) Étendre le côté droit de la file avec des éléments de L1 ;
• [Link](L2) Étendre le côté gauche de la file avec des éléments de L2.

Page 4
 Exemple d’utilisation de deque

1 >>> import collections as c

2 >>> f=[Link]([]), #création d'une file vide
3 >>> f1=[Link]([],5) # 5 représente l'attribut maxlen de f1
4 >>> [Link]
5 5
6 >>> [Link]('f')
7 >>> f1
8 deque(['f', 45], maxlen=5)
9 >>> [Link]([1,8,9,10])
10 >>> f1
11 deque([45, 1, 8, 9, 10], maxlen=5)
12 >>> [Link](0)
13 >>> f1
14 deque([1, 8, 9, 10, 0], maxlen=5)
15 >>> len(f1)
16 5

5 Piles vs files : synthèse

Pile File

Les objets sont insérés et supprimés à 1 seule Les objets sont insérés et retirés aux 2 extrémi-
extrémité. tés.

Dans les piles, un seul pointeur est utilisé. Il Dans les files, deux pointeurs différents sont uti-
pointe vers le haut de la pile. lisés pour les extrémités ; le tète et la fin.

Dans les piles, le dernier objet inséré est le pre- Dans les files, l’objet inséré en premier est le
mier à sortir. premier qui sera supprimé.

Les piles suivent l’ordre Last In First Out (LIFO). Les files suivent l’ordre First In First Out (FIFO).

Les opérations de pile s’appellent "Empiler" et Les opérations de file sont appelées "Enfiler" et
"Dépiler". "Défiler".

Les piles sont visualisées sous forme de collec- Les files sont visualisées sous forme de collec-
tions verticales. tions horizontales.

Page 5