Exercices pile, file

• Correction des exercices

Exercices

Exercice 1 *

L’interface d’une pile peut s’écrire:

• creer_pile() -> Pile: crée une pile vide
• est_vide(p: Pile) -> bool: renvoie True si la pile est vide, False sinon.
• empiler(p: Pile, e: T) -> None: ajoute un élément e au sommet de la pile.
• depiler(p: Pile) -> T: retire et renvoie l’élément du sommet de la pile.

L’implémentation utilisant la programmation objet, choisie dans le cours, n’est pas la seule possible.

Dans cet exercice, le choix est fait d’écrire quatre fonctions pour implémenter la pile. De plus, les données (des entiers) seront stockées dans un tableau. L’interface peut alors se réécrire:

• creer_pile() -> list: crée une pile vide
• est_vide(p: list) -> bool: renvoie True si la pile est vide, False sinon.
• empiler(p: list, e: int) -> None: ajoute un élément e au sommet de la pile.
• depiler(p: list) -> int: retire et renvoie l’élément du sommet de la pile.

1. Écrire les fonctions implémentant l’interface de la pile. Pour la fonction depiler, ajouter une assertion qui vérifiera que la pile n’est pas vide.

2. Écrire un programme qui:

   • construit une pile,
   • empile 5 entiers aléatoires
   • dépile la pile tant qu’elle n’est pas vide.

Exercice 2 *

1. Effectuer le même travail que l’exercice précédent, pour une file d’interface:

• creer_file() -> list: crée une file vide
• est_vide(f: File) -> bool: renvoie True si la file est vide, False sinon.
• enfiler(f: File, e: T) -> None: ajoute un élément e à la fin de la file.
• defiler(f: File) -> T: retire et renvoie l’élément du début de la file.

2. Discuter la complexité des fonctions de cette implémentation.

Exercice 3 **

1. Créer une classe Pile qui implémente l’interface:

   • est_vide() -> bool
   • empiler(e: int) -> None
   • depiler() -> int

2. À l’aide la bibliothèque time, estimer la durée d’exécution pour:

   • empiler 100000 éléments,
   • dépiler 100000 éléments.

Exercice 4 **

1. Créer une classe File qui implémente l’interface:

   • est_vide() -> bool
   • enfiler(e: int) -> None
   • defiler() -> int

2. À l’aide la bibliothèque time, estimer la durée d’exécution pour:

   • empiler 100000 éléments,
   • dépiler 100000 éléments.

3. Proposer une explication qui justifie ces durées.

4. Ouvrir la documentation de la classe deque dans la bibliothèqe collections

5. Écrire une nouvelle classe File_deque en utilisant une deque pour stocker les données. La classe implémentera la même interface que précédemment.

6. Mesurer la durée pour enfiler puis défiler 100000 éléments.