Liste des cours Se connecter

Informations

Auteur(s) Vincent Branders, Pierre Dupont
Date limite 12/03/2025 14:00:00
Limite de soumission Pas de limite

Se connecter

Se connecter

[TP.04] Le TAD File

Intéressons-nous un peu au TAD file.

Question 1: Le TAD File

Sélectionnez, parmi les propositions suivantes, celle qui définit le TAD File.

Question 2: Implémentation d'une file

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier queue.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter. Pour cet exercice, remplissez le corps de la classe en implémentant les fonctions suivantes :

class Queue:
    ########################################################
    # TODO: écrivez les spécifications complètes de la classe
    # TODO: complétez les méthodes de la classe pour implémenter
    #       une file par un tableau dynamique circulaire
    def __init__(self):
        """
        pre:
        post:
        """
        return None
    def __len__(self):
        """
        pre:
        post:
        """
        return None
    def enqueue(self, item):
        """
        pre:
        post:
        """
        return None
    def dequeue(self):
        """
        pre:
        post:
        """
        return None
    def is_empty(self):
        """
        pre:
        post:
        """
        return None
    ########################################################
    # Si vous le désirez, vous pouvez implémenter la méthode
    # __str__(self) pour obtenir une représentation de votre
    # file sous forme de string
    # Exemple:
    def __str__(self):
        str_queue = "This is a Queue. Ideally, I should report "\
        "my content.\n"
        return str_queue
Question 3: enqueue()

Quelle est la complexité temporelle amortie de la méthode enqueue() ? Choisissez la borne la plus simple et la plus stricte possible.

Question 4: dequeue()

Quelle est la complexité temporelle de la méthode dequeue() ? Choisissez la borne la plus simple et la plus stricte possible.