Implémentations (Bac 🎯)⚓︎

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.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
la ressource Eduscol sur les types de données
le cours de mon collègue Pierre Duclosson
le cours de Gilles Lassus
le cours de Franck Chambon

🔖 Synthèse de ce qu'il faut retenir pour le bac

Implémentation par une liste chaînée⚓︎

Exercice 3

On peut implémenter le type abstrait File par une liste chaînée mutable en reprenant l'implémentation objet du type Pile mais au lieu d'un unique attribut contenu pointant sur la première cellule de la liste assimilée au sommet de la pile, il faut deux attributs :

pour l'opération defiler: un attribut debut pointant sur la première cellule de la liste
pour l'opération enfiler : un attribut finpointant sur la dernière cellule de la liste

⏱️ Ces deux attributs vont permettre de réaliser les opérations enfiler et defiler en temps constant en \(0(1)\), par l'ajout ou la suppression de liens entre cellules, mais attention 👎

subtilité de la gestion de deux attributs

Une file est vide si et seulement si les deux attributs debut et fin ne pointent pas vers une cellule et sont positionnés à None. Il faut donc être vigilant à bien modifier ces deux attributs lorsqu'on passe d'une file vide à une file non vide et vice versa

si l'opération defiler donne une file vide, l'attribut debut va prendre la valeur None et il faut penser à passer aussi fin à None sinon il va pointer encore sur la cellule qui a été défilée.
si l'opération enfiler s'applique à une file vide, l'attribut debut va pointer vers une nouvelle cellule, il faut penser à faire pointer fin vers cette même cellule sinon il pointe encore vers None.

alt

Question 1

💻 Saisir ses réponses sur Capytale

énoncésolution

Complétez l'interface de la classe File qui implémente le type abstrait File avec une liste chaînée.

Évaluations restantes : ∞/∞

🐍 Script Python

class Cellule:

    def __init__(self, elt, suivant):
        self.element = elt
        self.suivant = suivant
        
class File:
    
    def __init__(self):
        self.debut = None
        self.fin = None
        
    def file_vide(self):
        return (self.debut is None) and (self.fin is None)

    def defiler(self):
        assert not self.file_vide(), "File Vide"
        elt = self.debut.element
        self.debut = self.debut.suivant
        if self.debut is None:
            self.fin = None
        return elt
    
    def enfiler(self, elt):
        if self.file_vide():
            self.fin = Cellule(elt, None)
            self.debut = self.fin
        else:
            self.fin.suivant = Cellule(elt, None)
            self.fin = self.fin.suivant
    
    # interface étendue 
    
    def queue(self):
        assert not self.file_vide()           
        file_queue = File()
        file_queue.debut = self.debut.suivant
        if self.debut.suivant is not None:
            file_queue.fin = self.fin
        else:
            file_queue.fin = file_queue.debut
        return file_queue
    
    def affichage_aux(self):
        if self.file_vide():
            return 'None'
        return f"{str(self.debut.element)} -> {self.queue().affichage_aux()}"
    
    def __str__(self):
        return "début : " + self.affichage_aux() + " : fin"


def test_file():
    f = File()
    for k in range(1, 6):
        f.enfiler(k)
    for k in range(1, 6):
        assert f.defiler() == k
    assert f.file_vide()
    print("Tests réussis")

Implémentation par un tableau circulaire⚓︎

Exercice 4

Si on veut limiter la taille de la file, on peut implémenter le type abstrait File par un tableau statique de taille taille_max comme pour une Pile.

Comme on a besoin de deux accès en debut (pour défiler) et fin (pour enfiler) de file, une solution est de garder en mémoire deux index debutet fin et de les incrémenter si on défile ou enfile un élément. Lorsque l'index atteint la fin du tableau on revient au début comme si le tableau était circulaire. Les décalages d'index se font donc modulo taille_max.

⏱️ Les opérations enfiler et defiler sont de simples décalages d'index avec affectation de coût constant en \(O(1)\).

Exemple 2

Dans l'exemple ci-dessous, un tableau statique de 8 cases permet de contenir une file d'au plus 8 éléments.

Initialement debutet fin pointaient vers la case d'index taille_max - 1 du tableau, la file était vide.
Puis on a enfilé e1 et debut et fin ont incrémenté de 1 et pointé vers la case d'index 0.
Puis on a enfilé e2, e3, e4, e5, e6 : à chaque itération fin a incrémenté de 1 mais debut n'a pas bougé.
Il reste une place dans la file.
Si on défile e1, alors debut incrémentera de 1 et fin ne bougera pas.

Par commodité pour déterminer si la file est vide, on va maintenir un attribut taille initialisé à 0 : on l'incrémentera si on enfile et on le décrémentera si on défile.

alt

Question 1

💻 Saisir ses réponses sur Capytale

énoncésolution

Complétez l'interface de la classe File2 qui implémente le type abstrait File avec un tableau circulaire.

Évaluations restantes : ∞/∞

🐍 Script Python

class File2:
    
    def __init__(self, taille_max):
        self.taille_max = taille_max
        self.tab = [None for _ in range(self.taille_max)]
        self.taille = 0
        self.debut = self.taille_max - 1
        self.fin = self.taille_max - 1
        
    def file_vide(self):
        return self.taille == 0

    def defiler(self):
        assert not self.file_vide(), "File Vide"
        elt = self.tab[self.debut]
        self.debut = (self.debut  + 1) % self.taille_max
        self.taille = self.taille - 1
        return elt
    
    def enfiler(self, elt):
        assert self.taille < self.taille_max, "Dépassement de capacité"
        self.fin = (self.fin + 1) % self.taille_max
        if self.file_vide():
            self.debut = self.fin
        self.taille = self.taille + 1
        self.tab[self.fin] = elt
    
    # interface étendue 

    def __str__(self):
        sortie = "debut : " 
        k = self.debut
        while k != self.fin:
            sortie = sortie + str(self.tab[k]) + ' - '
            k = (k + 1) % self.taille_max
        sortie = sortie + str(self.tab[k]) +  ' - : fin'
        return sortie
        
def test_file2():
    f = File2(10)
    for k in range(1, 6):
        f.enfiler(k)
    for k in range(1, 6):
        assert f.defiler() == k
    assert f.file_vide()
    print("Tests réussis")

Implémentation par deux piles⚓︎

Exercice 5

Une autre implémentation du type abstrait File consiste à utiliser deux piles, entree et sortie. On ajoute les éléments sur la pile entree et on les retire de la pile sortie. Si la pile sortie est vide on y transfère les éléments de la pile entree.

Entre son entrée et sa sortie, un élément subit deux opérations de dépilement, chacune inverse l'ordre et donc au final l'ordre est conservé (penser que la composée de deux fonctions décroissantes est une fonction croissante ! ).

Dans l'exemple ci-dessous :

on enfile successivement 'Alice', 'Bob', 'Charles' qui sont empilés dans la pile entree
quand on veut défiler pour la première fois (étape 4), comme la pile sortie est vide on transfère d'abord la pile entree sur la pile sortie par des dépilements successifs (logique LIFO) puis on dépile (logique LIFO) le sommet de sortie qui est 'Alice'. C'est bien le premier élément inséré dans la structure : la composition de deux fonctions LIFO équivaut à une fonction FIFO.

alt

Question 1

💻 Saisir ses réponses sur Capytale

énoncésolution

Complétez l'interface de la classe File3 qui implémente le type abstrait File avec deux piles.

Évaluations restantes : ∞/∞

🐍 Script Python

class Cellule2:
    
    def __init__(self, elt, suivant):
        self.element = elt
        self.suivant = suivant
        
class Pile:
    
    def __init__(self):
        self.contenu = None

    def pile_vide(self):
        return self.contenu is None

    def depiler(self):
        assert not self.pile_vide(), "Pile Vide"
        sommet = self.contenu.element
        self.contenu = self.contenu.suivant
        return sommet

    def empiler(self, elt):
        if self.pile_vide():
            self.contenu = Cellule2(elt, None)
        else:
            self.contenu = Cellule2(elt, self.contenu)
            
    def queue(self):
        assert not self.pile_vide()           
        pile_queue = Pile()
        pile_queue.contenu = self.contenu.suivant
        return pile_queue
    
    def __str__(self):
        if self.pile_vide():
            return 'None'
        return f"({str(self.contenu.element)},{str(self.queue())})"

class File3:
    
    def __init__(self):
        self.entree = Pile()
        self.sortie = Pile()
        
    def file_vide(self):
        return self.entree.pile_vide() and self.sortie.pile_vide()

    def defiler(self):
        assert not self.file_vide(), "File Vide"
        if self.sortie.pile_vide():
            # si sortie vide  retourne la pile entree sur la pile sortie
            while not self.entree.pile_vide():
                self.sortie.empiler(self.entree.depiler())
        return self.sortie.depiler()            
    
    def enfiler(self, elt):
        self.entree.empiler(elt)
    
    # interface étendue
    def __str__(self):
        sortie = "debut : " 
        tmp = File3()
        while not self.file_vide():
            elt = self.defiler()
            sortie = sortie + str(elt) + ' - '
            tmp.enfiler(elt)
        while not tmp.file_vide():
            self.enfiler(tmp.defiler())        
        sortie = sortie.rstrip(' - ') + ': fin'
        return sortie

def test_file3():
    f = File3()
    for k in range(1, 6):
        f.enfiler(k)
    for k in range(1, 6):
        assert f.defiler() == k
    assert f.file_vide()
    print("Tests réussis")

Implémentation avec une `deque`⚓︎

Exercice 6

Le module collections de la bibliothèque standard de Python propose une implémentation d'une file à deux bouts deque qui permet de retirer ou d'ajouter un élément aux deux bouts en temps constant. Une deque vide est construite à partir d'un tableau dynamique Python vide :

🐍 Script Python

from collections import deque
dq = deque([])  # une deque vide

Un tableau dynamique Python permet l'ajout et le retrait en temps constant à droite (fin du tableau) mais pas à gauche (début du tableau) car il faut alors décaler tous les éléments suivants vers la gauche ou la droite selon qu'on retire ou qu'on ajoute un élément à gauche.

Dans le tableau ci-dessous on compare l'efficacité des opérations d'ajout ou de retrait à gauche ou à droite pour un tableau dynamique Python (type list) ou une deque de taille \(n\).

Opération	Tableau dynamique Python	`deque` du module `collections`	Opération du type File
Ajout à gauche	`tab.insert(0, elt)` de coût \(O(n)\)	`deq.appendleft(elt)` de coût \(O(1)\)	aucune
Retrait à gauche	`tab.pop(0)` de coût \(O(n)\)	`deq.popleft()` de coût \(O(1)\)	`defiler`
Ajout à droite	`tab.append(elt)` de coût \(O(1)\)	`deq.append(elt)` de coût \(O(1)\)	`enfiler`
Retrait à droite	`tab.pop()` de coût \(O(1)\)	`deq.pop()` de coût \(O(1)\)	aucune

Avec une deque on peut implémenter de façon efficace les opérations enfiler et defiler du type abstrait File et le code est simplifié par rapport aux trois implémentations précédentes. L'utilisation d'un tableau dynamique Python dégraderait les performances pour l'opération defiler.

alt

Question 1

💻 Saisir ses réponses sur Capytale

énoncésolution

Complétez l'interface de la classe File4 qui implémente le type abstrait File avec une deque.

Évaluations restantes : ∞/∞

🐍 Script Python

from collections import deque

class File4:
    
    def __init__(self):
        self.contenu = deque([])
        
    def file_vide(self):
        return len(self.contenu) == 0

    def defiler(self):
        assert not self.file_vide(), "File Vide"
        return self.contenu.popleft()
    
    def enfiler(self, elt):
        self.contenu.append(elt)
    
    # interface étendue
    def __str__(self):
        sortie = "debut : " 
        tmp = File4()
        while not self.file_vide():
            elt = self.defiler()
            sortie = sortie + str(elt) + ' - '
            tmp.enfiler(elt)
        while not tmp.file_vide():
            self.enfiler(tmp.defiler())        
        sortie = sortie.rstrip(' - ') + ': fin'
        return sortie

def test_file4():
    f = File4()
    for k in range(1, 6):
        f.enfiler(k)
    print(f)
    for k in range(1, 6):
        assert f.defiler() == k
    assert f.file_vide()
    print("Tests réussis")

Implémentations (Bac 🎯)⚓︎

Implémentation par une liste chaînée⚓︎

Implémentation par un tableau circulaire⚓︎

Implémentation par deux piles⚓︎

Implémentation avec une deque⚓︎

Implémentation avec une `deque`⚓︎