Chapitre 4

Les piles et les

files
Introduction
 Les piles et files ne sont pas de nouveaux types de données mais plutôt une manière de
gérer un ensemble de données.
 Les piles et les files se définissent par leur comportement (en répondant à la question «
qu’est ce que cela fait ») on dit que ce sont des structures de données abstraites.
 Elles sont très souvent utiles et servent, entre autres, à mémoriser des évènements en attente
de traitement.
 Il n'y a pas de structures spécifiques prévues dans les langages de programmation pour les
piles ou files.
Il faut donc les créer de différents manières sachant que la représentation en mémoire de
ces structures de données peut être, selon le besoin, statique (utilisation des tableaux) ou
dynamique (utilisation des listes).

Imen TOUNSI 2
1. Les piles
1.1 Définition
 En informatique, une pile est un ensemble d’éléments de même type dont un seul est
accessible à un moment donné; celui qui est au sommet de la pile.
 Les piles sont des structures de données abstraites dont l'accès est selon la règle dernier
arrivé premier servi ou encore Last In First Out (LIFO).
 L’ajout d’un élément à la pile se fait sur le sommet de la pile.
 Le dernier élément ajouté à la pile est le premier traité et supprimé.
 Elles sont appelées ainsi, en référence à une pile d’assiettes car un utilisateur ne peut
accéder qu’à l’élément au sommet de la pile.

Imen TOUNSI 2
 La pile est une propriété abstraite, qui n’impose pas une constitution particulière.
 En fait, on réalise aussi bien des piles à partir de tableaux qu’à partir de listes chaînées.
 Utilité :
• Traitement des expressions arithmétiques
• Sauvegarde du contexte par le traitement des fonctions récursives
• Compilateur
• Parcours en profondeur
1.3. Opérations
Les opérations (primitives) sur une pile sont les suivantes :
 Empiler(élément,p) : rajoute un élément sur la pile.
 Sommet(p) : donne l’élément au sommet de p.
 Dépiler(p) : renvoie la valeur de l'élément au sommet de la pile et le supprime.
 Vide(p) : renvoie VRAI si et seulement si la pile est vide
 RAZ(p) : vide le contenu de la pile (Remise A Zéro)

Imen TOUNSI 4
1.4. Représentation d’une pile par un tableau (Pile statique)
1 Une pile statique est un enregistrement à 2 cases : un
2 tableau à hauteur maximale prévisible et un indice entier
3 qui pointe sur la dernière valeur ajoutée à la pile (sommet).
4
Pascal
/*définition du type pile
5
Const n=8 /* taille du tableau*/
6 Java
Types
7 C Pile = enregistrement
8 Python element[1..n] : chaine
sommet : entier
FinEnregistrement
Var P:Pile
Dans l’exemple : Sommet= 5
Si la pile est vide sommet = 9
Si la pile est pleine sommet = 1

Imen TOUNSI 5
Primitives de pile représentée par un vecteur
procédure RAZ(var p : Pile)
Début
p.sommet ← n+1
Fin
Fonction vide(p : Pile) : Booléen //vérifier si la liste est vide
Début
si (p.sommet = n+1) alors
vide ← vrai
sinon
vide ← faux
Fin
Fonction pleine(p : Pile) : Booléen //vérifier si la liste est pleine
Début
si (p.sommet = 1) alors
pleine ← vrai
sinon
pleine ← faux
Fin

Imen TOUNSI 6
Fonction sommetP (p : pile): chaine
Début
Si (vide(p)) alors sommet ← "#" //retourne une chaine particulière si la pile est vide
Sinon sommetP ← p.element[p.sommet]
FinSi
Fin

Procédure empiler(var p : pile, x:chaine)

Début Procédure dépiler(Var p : pile, var s :
Si (pleine(p)) alors Écrire("la pile est pleine") chaine)
Sinon Début
p.sommet ← p.sommet – 1 Si (vide(p)) alors Écrire("la pile est vide")
p.element[p.sommet] ← x Sinon
Finsi s ← p.element[p.sommet]
Fin p.sommet ← p.sommet + 1
Finsi
Fin

Imen TOUNSI 7
1.5. Exemple d'utilisation: calcul en notation polonaise inversée
Une formule mathématique peut être représentée par une liste de lexèmes. Un lexème
pouvant représenter:
 une valeur
 un operateur binaire
 un operateur unaire
 une parenthèse (ouvrante ou fermante)
 Exemple: peut être représentée par la liste : {4, 2, 16, sqrt, *, +, 6, /}

une forme post fixée où chaque opérateur vient après son dernier argument.
 L'intérêt de cette forme est qu'elle ne nécessite pas l'utilisation de parenthèses.

Imen TOUNSI 8
{4, 2, 16, sqrt, *, +, 6, /}
 L'évaluation de la formule post fixée peut être réalisée en utilisant une pile et en suivant les
règles suivantes : On lit les lexèmes dans l'ordre de la liste:
• si l'élément de la liste est une valeur, la placer sur une pile.
• si l'élément de la liste est un operateur unaire, l’appliquer sur le sommet de la pile.
• si l'élément de la liste est un operateur binaire, l’appliquer sur les deux éléments de tête de la pile.
 Algorithme :
élément pile
4 4
2 2 4
16 16 2 4
sqrt 4 2 4
* 8 4
+ 12
6 6 12
2 1 / 2
Imen TOUNSI 9
1.4 Représentation d’une pile par une liste simplement chaînée (Pile dynamique)
 En supposant que les éléments de la pile sont des entiers celles-ci se déclare de la façon
suivante:
Types
CelluleP = Enregistrement
Elem : entier
Suiv:*CelluleP
FinEnregistrement
Pile=*CelluleP

Var P:Pile

Imen TOUNSI 10
Opérations
Définir les opérations (primitives) sur une pile de type liste:
 Procédure Initialiser (Var P : Pile) : permet d'initialiser une pile vide
 Fonction PileVide (P : Pile) : booléen : permet de tester si une pile est vide
 Fonction Sommet (P : Pile) : entier : permet de retourner l’élément au sommet de P. Elle
retourne 0 si la pile est vide
 Procédure Empiler (Var P:Pile, x: Entier) : permet d'ajouter un élément x à la pile
 Procédure Dépiler (Var P:Pile, Var x: entier) : permet de supprimer le sommet de la pile et
d’enregistrer la valeur dans x
Types
CelluleP = Enregistrement
Elem : entier
Suiv:*CelluleP
FinEnregistrement
Pile=*CelluleP
Var P:Pile

Imen TOUNSI 11
Procédure Initialiser (Var P: Procédure Empiler (Var P: Pile,
Pile) x: entier)
Début
Var
P ← Nil
Fin Q : Pile
Fonction PileVide (P : Pile) : Début
booléen Allouer (Q)
Début
PileVide ←(P=Nil) *Q.Elem ←x
Fin *Q.Suiv←P
Fonction Sommet (P : Pile) : entier P←Q
Début Fin
Si (PileVide(p)) alors sommet ← 0
Sinon Sommet ← *P.Elem
FinSi
Fin

Imen TOUNSI 12
Procédure Dépiler (Var P: Pile, Var x: entier)
Var
Q:Pile
Début
Si PileVide(P) alors Ecrire (" la pile est vide")
Sinon
Q←P La suppression d’une valeur dans une pile
P ←*P.Suiv dynamique revient à effectuer une
x←*Q.Elem suppression physique d’un nœud (le premier
Liberer(Q) de liste) et à récupérer dans un paramètre,
passé par variable, la donnée enregistrée.
FinSi
Fin

Imen TOUNSI 13
Exercice 1
Écrire une procédure permettant d'inverser une liste L moyennant une pile.
procédure inverser_liste(Var L : Liste, P: Pile) QL
Var Q : Liste Tant que (Q<>Nil) Faire
Début dépiler(P, *Q.Elem)
RAZ(P) Q*Q.suivant
QL FinTQ
Tant que (Q<>Nil) Faire FIN
empiler (P, *Q.Elem)
Q  *Q.suivant
FinTQ Pile P
L
1 @c2
1
2 NiL

Imen TOUNSI 14
Exercice 2
Écrire une procédure pile_copy recevant une pile P comme argument et renvoyant une copie
CP de P (la pile P doit être conservée)
Procédure pile_copy(P: Pile, var CP : Pile)
Var T: Pile
x:entier 4 1 4
Début 3 2 3
Tantque (non vide(P)) faire 2 3 2
dépiler(P,x) 1 4 1
empiler(T,x) P T CP
FinTantQue
Tantque(non vide(T)) faire
dépiler(T,x)
empiler(P,x)
empiler(CP,x)
Fintantque
Fin
Imen TOUNSI 15
2. Les files
2.1. Définition
 Les files sont des structures de données abstraites qui ressemblent beaucoup aux files
d'attentes. C’est un ensemble de valeurs qui a un début (Tête) et une fin (Queue).
 Les files suivent la loi du premier arrivé premier servi, ou encore First In First Out (FIFO).
 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)
 Défiler un objet de F consiste à supprimer de F l'objet placé en début de file. L'objet défilé
est retourné comme résultat du traitement.

Imen TOUNSI 16
2.2. Utilité
 En informatique une file sert essentiellement à stocker des données qui doivent être traitées
selon leur ordre d’arrivée.
 L’exemple le plus connu est celui de l’impression de documents reçus par une imprimante qui
imprime le premier document arrivé et termine par le dernier. Ce qui fait que les objets
quittent la file dans l'ordre de leur arrivé.
 En termes de programmation, une file est un enregistrement avec :
• Une structure de données pour enregistrées les valeurs (elle peut être statique ou
dynamique)
• Une variable Tête qui indique le premier élément de la file.
• Une variable Queue qui indique le dernier élément de la file.

Imen TOUNSI 17
2.3. Opérations
 Comme pour les piles, la manipulation d’une file revient à l’appel de fonctions et procédures
dites de bases définies une seule fois et utilisées autant de fois qu’il est nécessaire.
 Ces sous-algorithmes sont :
• Init_File : permet d’initialiser une file à vide lors de sa création ;
• File_vide : pour vérifier si une file est vide ou non et savoir alors s’il reste des valeurs à
traiter ou non ;
• File_pleine : pour vérifier s’il est possible de rajouter ou non un nouveau élément (utilisée
dans le seul cas des files statiques) ;
• Enfiler : permet d’ajouter une nouvelle valeur (envoyé en paramètre par l’appelant) à la
file (après le dernier élément de la file qui se trouve au niveau de sa queue et dans le
cas d’une file non pleine) ;
• Défiler : permet de supprimer une valeur (se trouvant au début de la file) et de la
renvoyer en paramètre. Cette opération n’est possible que si la file n’est pas vide.
• RAZ : vider le contenu de la file (Remise A Zéro)

Imen TOUNSI 18
2.2. Déclaration d'une file sous forme d'un tableau (File statique)
8
tête= 1, queue=4
7
6 Si la file est vide tête = queue = 0

5 Si la file est pleine (queue +1) mod n = tête

queue 4 Pascal
/*définition du type file
3 Java Const n=8
2 C Type
Tête 1 Python File = enregistrement
element[1..n] : chaine
tête, queue : entier
FinEnregistrement
Var F:File

Imen TOUNSI 19
Primitives de file représentées par un tableau
procédure RAZ_file(var f : File)
Début
f.tête←0
f.queue ←0
Fin
Fonction file_vide(f : File) : Booléen
Début
si (f.tête= 0) alors
file_vide ← vrai
sinon
file_vide ← faux
Fin
Fonction file_pleine(f : File) : Booléen
Début
si ((f.queue +1) mod n= f.tête) alors
file_pleine ← vrai
sinon
file_pleine ← faux
Fin
Imen TOUNSI 20
Fonction tête_file (f : file): chaine
Début
Si (file_vide(f))
alors tête_file ← "#" // retourne une chaine particulière si la file est vide
sinon tête_file ← f.element[f.tête]
Finsi
Fin
Procédure enfiler(Var f : file, x:chaine)
Début
Si (file_pleine(f)) alors Écrire("la file est pleine")
Sinon
si (file_vide(f)) alors f.tête ← 1
finsi
f.queue ← (f.queue + 1) mod n
f.element[f.queue] ← x

Finsi
Fin
nh

Imen TOUNSI 21
Procédure défiler(Var f : file, Var x: chaine)
Début
Si (file_vide(f)) alors x ← "#"
Sinon
x ← f.element[f.tête]
si (f.tête = f.queue) alors
RAZ_file(f)
sinonSi (f.tête = n-1) alors
f.tête ← n
Sinon f.tête ← (f.tête + 1) mod n
Finsi
Fin

Imen TOUNSI 22
2.4 Déclaration d'une file sous forme d'une liste chainée (File dynamique)
 Une File dynamique est une liste à la quel on attache deux pointeurs : un
pointeur qui pointe sur le premier élément de la liste (Tête) et un autre qui
pointe sur la dernière valeur ajoutée dans la liste (Queue).
 Exemples :
1- Une file vide : Tête = Queue = Nil
2- Une file a un seul élément : Tête = Queue ≠ Nil
3- Une file a plus d’un élément : Tête ≠ Queue

Note : Il n’y a pas de file pleine pour les files dynamique.

Imen TOUNSI
 En supposant que les éléments de la file sont des entiers celles-ci se déclare de la
façon suivante:
Types
CelluleF = Enregistrement
Elem : entier
Suiv : *CelluleF
FinEnregistrement
Tête

FileD = Enregistrement
Tête : *CelluleF
Queue : *CelluleF
FinEnregistrement

Var
F : FileD

Imen TOUNSI
 Initialisation d’une file dynamique
Procédure Init_FileD (Var F : FileD)
Début
F. Tête ← Nil
F. Queue ← Nil • Une autre façon plus compacte d’écrire cette
fonction est la suivante :
Fin
 Vérification de File dynamique vide Fonction File_videD (F : FileD) :
Fonction File_videD (F : FileD) : Booléen Booléen
Début Début
Si (F. Queue = Nil) alors File_videD ← vrai File_videD ← F. Queue = Nil
Sinon File_videD ← faux Fin
FinSi
Fin

Imen TOUNSI 25
 Ajout d’une nouvelle valeur à une file dynamique
Procédure EnfilerD (Var F : FileD , X : Entier)
Var Pt : *CelluleF
Début
Allouer (Pt)
*Pt.Elem ← X
*Pt. Suiv ← Nil
Si File_videD(F) Alors F.Tête ← Pt
Sinon *(F. Queue).Suiv ← Pt
FinSi
F.Queue ← Pt
Fin

Imen TOUNSI 26
Suppression d’une valeur de la file dynamique
Procédure DéfilerD (Var F: FileD, Var X :Entier)
Var Pt : *CelluleF
Début
Si File_videD(F) Alors Ecrire('Impossible la file est vide')
Sinon
Pt ← F. Tête
X ← *(F. Tête).Elem
F.Tête ← *(F. Tête).Suiv
Si F. Tête = Nil Alors F. Queue ← Nil
FinSi /* si Tête devient Nil cela veut dire que la file a été vidée et Queue doit devenir Nil*/
Libérer (Pt)
FinSi
Fin

Imen TOUNSI 27
Exercice
Écrire une procédure permettant d'inverser une file, passée en paramètre, moyennant une pile.
Procédure Inverser_fileD(Var F :FileD, P : Tant que (non Pile_vide(P)) Faire
Pile)
Dépiler(P,x)
Var x : entier
EnfilerD(F,x)
Début
Initialiser(P) FinTQue
Tant que (non File_videD(F)) Faire Fin
DéfilerD(F, x)
Empiler(P,x)
FinTantQue

Imen TOUNSI 28
 Fin
PILES ET FILES

Imen TOUNSI 29