structure de données abstraites linéaires III

Implémentation

Objectifs :

À la fin de cette séquence vous serez capable de :

• Distinguer des structures par le jeu des méthodes qui les caractérisent.
• Choisir une structure de données adaptée à la situation à modéliser.
• Spécifier une structure de données par son interface.
• Distinguer interface et implémentation.
• Écrire plusieurs implémentations d’une même structure de données.

1. Implémenter à l'aide du sous-module deque

1.1. La classe deque du module collections

Cette classe deque renvoie un nouvel objet deque initialisé de gauche à droite avec les données d'un iterable (str, list, tuple...). Si l'iterable n'est pas spécifié, le nouveau deque est vide.
deque est optimisé pour la création de pile et file.

from collections import deque
lst_deque_vide = deque()

len(lst_deque_vide)

lst_deque = deque([1, 2, 3])

lst_deque

lst_deque.append("a")

lst_deque

lst_deque.appendleft(100)

lst_deque

lst_deque.pop()

lst_deque

lst_deque.popleft()

lst_deque

# deque avec une taille max
lst_deque_avec_taille_max = deque([], 5)

lst_deque_avec_taille_max 

lst_deque_avec_taille_max.append("a")
lst_deque_avec_taille_max .append("e")
lst_deque_avec_taille_max .append("i")
lst_deque_avec_taille_max .append("o")
lst_deque_avec_taille_max .append("u")

lst_deque_avec_taille_max

# supprimer le dernier élément et insérer le nouvel élément à gauche
lst_deque_avec_taille_max.appendleft(1)

lst_deque_avec_taille_max

# supprimer le premier élément et insérer le nouvel élément à droite
lst_deque_avec_taille_max.append(100)

lst_deque_avec_taille_max

# afficher la taille max
lst_deque_avec_taille_max.maxlen

lst_deque_avec_taille_max[0]

len(lst_deque_avec_taille_max)

list(lst_deque_avec_taille_max)[1:]

1.2. Type liste

from collections import deque

class ListeDeque:
    def __init__(self):
        """Crée et initialise la liste."""
        self.donnees = deque()
        
    def est_vide(self):
        """Renvoie True si la liste est vide, False sinon."""
        return len(self.donnees) == 0
    
    def head(self):
        """
            Renvoie la valeur de l'élément en tête de liste sans le supprimer.
            Lève une exception si la liste est vide.
        """
        if self.est_vide():
            raise IndexError("La liste est vide !")
        else:
            return self.donnees[0]
        
    def pop(self):
        """
        Supprime et renvoie l'élément en tête de liste.
        Lève une exception si la liste est vide.
        """
        if self.est_vide():
            raise IndexError("La liste est vide !")
        return self.donnees.popleft()
        
    def push(self, donnee):
        """Insère donnee à la tête de la liste."""
        self.donnees.appendleft(donnee)
        
    def queue_de_deque(self):
        """Renvoie la liste privée de son premier élément.
           Lève une exception si la liste est vide.
        """
        if self.est_vide():
            raise IndexError("La liste est vide !")
        else:
            return list(self.donnees)[1:]

    def __repr__(self):
        """Représentation pour les programmeurs."""
        return f"ListeDeque({repr(self.donnees)})"
    
    def __str__(self):
        return f"{list(self.donnees)}"

elts_chimiques = {
    "alcalins": {1: "H", 3: "Li", 11: "Na", 19: "K"},
    "alcalino-terreux": {4: "Be", 12: "Mg", 20: "K", 38: "Sr"},
    "gaz rares": {2: "He", 10: "Ne", 18: "Ar", 36: "Kr"}
}

1. À l'aide d'une boucle for, insérer dans l'instance de ListeDeque, lst_deque, les symboles chimiques du dictionnaire elts_chimiques.
2. À l'aide de lst_deque, tester les différentes méthodes de la classe ListeDeque.

1.3. Pile

from collections import deque

class PileDeque:
    """Implémentation de la pile avec deque"""
    def __init__(self):
        """Initialise une pile vide."""
        self.donnees = deque()
    
    def empile(self, donnee):
        """Insère donnee au sommet de la pile."""
        self.donnees.append(donnee)
        
    def depile(self):
        """Supprime et renvoie l'élément au sommet de la pile."""
        if not self.est_vide():
            return self.donnees.pop()
        else:
            raise IndexError("La pile est vide !")
    
    def sommet(self):
        """Renvoie sans le supprimer l'élément au sommet de la pile."""
        if not self.est_vide():
            return self.donnees[-1]
        else:
            raise IndexError("La pile est vide !")
    
    def est_vide(self):
        """Renvoie True si la pile est vide, False sinon."""
        return len(self.donnees) == 0
    
    def taille(self):
        """Renvoie le nombre d'éléments dans la pile."""
        return len(self.donnees)
    
    # Afficher les éléments sous la forme d'une liste python
    def __str__(self):
        return f"{list(self.donnees)}"
    
    def __repr__(self):
        return f"PileDeque({self.donnees})"

1.4. File

Implémenter une classe File à l'aide de la classe deque.

2. Conclusion : types de données et strutures de données

Un type abstrait ou structure de données abstraite (SDA) est la description d'un ensemble organisé d'objets et des opérations de manipulation sur cet ensemble. Ces opérations comprennent les moyens d'accéder aux éléments de l'ensemble, et aussi, lorsque l'objet est dynamique, les possibilités de le modifier.
Par exemple, on n'a pas besoin de savoir comment une chaîne de caractères (str) ou une liste est stockée en mémoire, tant que l'on sait l’utiliser. Une SDA décrit quoi faire, mais pas comment le faire. C'est un concept.
Une structure de données (SDD) est la réalisation concrète, l'implémentation explicite en machine d'une SDA.

• Décrire un type de données, le spécifier comme on dit, c'est décrire les opérations possibles et licites, et leur effet.
• Décrire une structure de données, c'est expliciter comment les objets sont représentés et comment les opérations sont implémentées.

Chaque SDD a

• une interface.
  Elle liste les opérations disponibles, les types de paramètres qu’elles acceptent et leurs résultats.
• Une implémentation.
  Elle définit comment les données sont organisées et comment les opérations fonctionnent en interne.

Le choix d'une structure de données a un impact direct sur la complexité d'un algorithme, c'est-à-dire sur la quantité de ressources (temps et mémoire) qu'il consomme pour s'exécuter. Cela signifie qu'une SDD mal choisie peut rendre un algorithme inefficace, tandis qu'une structure bien adaptée peut grandement améliorer ses performances.
Donc le choix d'une structure de données dépend des opérations fréquentes dans l'algorithme.