PILE & FILE – Pile
Chapitre V
1. Trouver des exemples dans la vie courante et/ou en informatique d’utilisation d’une structure de type PILE.
Le schéma d’utilisation de la structure peut aider.
PILE & FILE – Pile
Chapitre V
2. Implémenter ces interfaces en POO Python.
On pourra fortement s’inspirer de la liste simplement chaînée non circulaire, tout comme également ajouter une fonction d’affichage.
PILE & FILE – Pile
Chapitre V
3. Modifier l’attribut taille de la classe Pile : cet attribut sera privé et accessible seulement par la méthode __len__.
Ecrire une fonction inverse(pile) de paramètre une instance de la classe Pile, qui renvoie une nouvelle instance de Pile dont les valeurs sont les mêmes que pile, mais dans l’ordre contraire.
4. Quelle est la complexité des méthodes de la classe Pile ?
Quelle est la complexité de la fonction inverse ?
5. Un problème fréquent pour les compilateurs est de vérifier la validité d’une expression en ne considérant que () et []. Ainsi :
- "4 bleu ( 5 + [rouge] )" ou "[]" seront considérées valables.
- "4 bleu ( [5 + rouge) ]" ou "[(" ne seront pas considérées valables.
Ecrire une fonction valide(chaine) qui renvoie True si la chaine est valable, False sinon. Vous utiliserez une Pile comme structure.
PILE & FILE – File
Chapitre V
6. Trouver des exemples dans la vie courante et/ou en informatique d’utilisation d’une structure de type FILE.
Le schéma d’utilisation de la structure peut aider.
PILE & FILE – File
Chapitre V
7. Implémenter ces interfaces en POO Python.
On pourra fortement s’inspirer de la liste simplement chaînée non circulaire, tout comme également ajouter une fonction d’affichage.
Contrairement à la Pile, une File n’est pas une structure de donnée récursive :
En effet, on a besoin d’accéder à la fois au premier et au dernier élément.
PILE & FILE – File
Chapitre V
8. Modifier la classe File avec un attribut taille au constructeur. Reprendre ensuite les exercices 3 et 4 avec les deux classes File.
9. Il est possible d’implémenter la structure File avec deux Piles ; enfiler un élément consiste à l’empiler sur la pile d’entrée et défiler un élément consiste à dépiler la pile de sortie. Si la pile de sortie est vide, dépiler chaque élément de la pile d’entrée pour l’empiler sur la pile de sortie et dépiler. Implémenter cette classe File_2piles.
10. A l’hôpital, aux urgences, difficile de ne considérer que l’ordre d’arrivée des patients. On va donc affecter à chacun une priorité (1, 2, 3, 4, 5) 5 étant vital, 1 mineur. Ainsi : si on voit arriver ("Linux", 4), ("MacOS", 2) puis ("Windows", 4), la file retenue sera :
("Linux", 4), ("Windows", 4) puis ("MacOS", 2)
Implémenter une classe File_prio qui tient compte de cette règle.