Corrigé du TD Pile et File

---

1. Application de cours

1. 1. Pile

État initial de la pile :

5  ← sommet
4
3
2
1  ← fond

Question 1 : État après Depile(), Depile(), Empile(7), Empile(8), Depile()

Exécution pas à pas :

Opération	État de la pile	Élément retourné
Initial	[1, 2, 3, 4, 5]	-
Depile()	[1, 2, 3, 4]	5
Depile()	[1, 2, 3]	4
Empile(7)	[1, 2, 3, 7]	-
Empile(8)	[1, 2, 3, 7, 8]	-
Depile()	[1, 2, 3, 7]	8

État final :

7  ← sommet
3
2
1  ← fond

top() renvoie : 7

---

Question 2 : Pour que Est_vide() soit vrai, il faut dépiler tous les éléments.

Depile()  → renvoie 5
Depile()  → renvoie 4
Depile()  → renvoie 3
Depile()  → renvoie 2
Depile()  → renvoie 1
Est_vide() → True

Réponse : 5 appels à Depile()

---

Question 3 : Créer une pile contenant 19982018 (1 en bas de pile)

La pile doit ressembler à :

8  ← sommet
1
0
2
8
9
9
1  ← fond

Séquence de méthodes :

Empile(1)
Empile(9)
Empile(9)
Empile(8)
Empile(2)
Empile(0)
Empile(1)
Empile(8)

---

1. 2. File

État initial de la file :

Entrée → 5 | 4 | 3 | 2 | 1 → Sortie
         ↑                   ↑
       queue               tête

Question 1 : État après Defile(), Defile(), Enfile(7), Enfile(8), Defile()

Exécution pas à pas :

Opération	État de la file	Élément retourné
Initial	[5, 4, 3, 2, 1]	-
Defile()	[5, 4, 3, 2]	1
Defile()	[5, 4, 3]	2
Enfile(7)	[7, 5, 4, 3]	-
Enfile(8)	[8, 7, 5, 4, 3]	-
Defile()	[8, 7, 5, 4]	3

État final :

Entrée → 8 | 7 | 5 | 4 → Sortie

top() renvoie : 4 (élément en tête, prêt à sortir)

---

Question 2 : Pour que Est_vide() soit vrai, il faut défiler tous les éléments.

Defile()  → renvoie 1
Defile()  → renvoie 2
Defile()  → renvoie 3
Defile()  → renvoie 4
Defile()  → renvoie 5
Est_vide() → True

Réponse : 5 appels à Defile()

---

Question 3 : Créer une file contenant 19982018 (1 en tête de file)

La file doit ressembler à :

Entrée → 8 | 1 | 0 | 2 | 8 | 9 | 9 | 1 → Sortie
                                       ↑
                                     tête

Pour que 1 soit en tête (premier à sortir), il faut l'enfiler en premier :

Séquence de méthodes :

Enfile(1)
Enfile(9)
Enfile(9)
Enfile(8)
Enfile(2)
Enfile(0)
Enfile(1)
Enfile(8)

---

Tableau récapitulatif

Structure	Principe	Ajout	Retrait	Accès
Pile	LIFO (Last In First Out)	Empile (sommet)	Depile (sommet)	Top (sommet)
File	FIFO (First In First Out)	Enfile (queue)	Defile (tête)	Top (tête)

---

Analogies pour mémoriser

Structure	Analogie	Explication
Pile	Pile d'assiettes	On pose et on prend toujours par le dessus
File	File d'attente	Le premier arrivé est le premier servi
Pile	Historique du navigateur	Le bouton "retour" revient à la page précédente (la dernière visitée)
File	Imprimante	Les documents sont imprimés dans l'ordre d'envoi

---

Auteurs : Florian Mathieu, Enzo Frémeaux, Thimothée Decooster

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.