Skip to content

TD11. Files et piles

Le sujet de ce TD est disponible au format pdf ici.

Les objectifs de ce TD sont les suivants :

  • continuer à manipuler des références ;
  • maîtriser les piles ;
  • maîtriser les files.

Exercice 1 : les derniers seront les premiers

Vous êtes contactés par l'association NiEmacsNiVim pour réaliser un petit projet logiciel pour eux. Cette association développe un éditeur de texte révolutionnaire dans lequel il suffit de taper contrôle + s pour sauvegarder un fichier et de taper contrôle + z pour annuler la dernière action. Afin justement de pouvoir annuler un grand nombre d'actions, NiEmacsNiVim nous demande de leur fournir un module Python permettant de :

  • créer un historique d'actions initialement vide ;
  • ajouter une action à un historique ;
  • récupérer la dernière action ajoutée en levant une exception si il n'y a plus d'action dans l'historique ;
  • connaître la taille de l'historique.

Question 1

 

Ce cahier des charges correspond il à une structure de données (SDD) ou à un type abstrait (TA) ?

Question 2

 

Avez vous déjà rencontré quelque chose de similaire, et si oui sous quelle dénomination ?

Question 3

 

Proposez un squelette de votre module pour qu'il puisse être validé par NiEmacsNiVim avant que vous ne commenciez le développement. Vous fournirez une nouvelle classe permettant de représenter une pile. Pour rappel, dans le cadre de BPI nous utilisons les classes uniquement comme un agrégat de données. Les opérations que vous fournirez seront donc des fonctions et non pas des méthodes.

Question 4

 

Implémentez votre module sans utiliser de list Python.

Question 5

 

Dessinez la mémoire d'une pile contenant du haut vers le bas "partez", 3.0, (1, 2). C'est à dire une pile dans laquelle nous avons empilé (1, 2) puis 3.0 puis "partez".

Question 6

 

Justifiez vos choix auprès de NiEmacsNiVim.

Question 7

 

Sans écrire de code, comment feriez-vous pour implémenter votre module avec une list Python ? Quels seraient les avantages et les inconvénients par rapport à votre implémentation précédente ?

Exercice 2 : première arrivée, première servie

Question 1

 

Analysez le module Python ci-dessous et notez toutes les remarques (positives et négatives) et questions que vous pouvez avoir.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#!/usr/bin/env python3

"""Implémentation de l'ADT file en python."""

import datetime
import time

def arrive(l, b):
    l.append(b)

def premier(l):
    assert l, "file vide!"
    preums = l[0]
    l.pop(0)
    return preums

# Quelques tests
file_devant_la_poste = []
if datetime.date.today().weekday() == 5: # Samedi, c'est blindé !
    for i in range(1, 43):
        arrive(file_devant_la_poste, "client" + str(i))
else:
    arrive(file_devant_la_poste, "Micheline")
    arrive(file_devant_la_poste, "Karim")
    arrive(file_devant_la_poste, "Bao")
print(file_devant_la_poste)
try:
    while True:
        print(premier(file_devant_la_poste) + " au guichet SVP")
        time.sleep(5)
except:
    pass
print(file_devant_la_poste)

Exercice 3 : il y a des piles et des files partout (pour aller plus loin)

Question 1

 

Listez toutes les utilisations de le TA pile au sein d'un ordinateur que vous avez déjà rencontrées.

Question 2

 

Même question pour le TA file.

Question 3

 

Faites un dessin/schéma pour illustrer le plus simplement et clairement possible selon vous les notions de pile et de file. L'objectif est d'expliquer ces concepts à vos collègues absents aujourd'hui.