C3.3 : Varier les implémentations

Rappel de vocabulaires

Une structure de données est un ensemble cohérent qui permet de stocker et manipuler des informations à l'aide d'algorithmes.

Une structure de données se caractérise par :

- son interface : c'est l'ensemble de ce à quoi l'utilisateur de la structure de données peut accéder ;
- son implémentation : c'est le code utilisé pour programmer la structure de données (l'implémentation n'a pas besoin d'être connue de l'utilisateur de la structure de données).

Implémentations des piles et des files à l'aide de fonctions

A] Implémentation des piles

On considère le code ci-dessous :

def fonction1():
    return []

def fonction2(p):
    return p ==[]

def fonction3(p):
    if p != []:
        return p.pop()
    else:
        return None

def fonction4(p,e):
    p.append(e)

1) Justifier que ces quatre fonctions constituent bien une implémentation pour la manipulation de structures de données de type pile. Donner un nom adapté à chaque fonction.

2) Écrire le code qui permet d'exécuter successivement les actions suivantes :

- création d'un pile p1
- création d'un pile p2
- ajout successif des valeurs 4 et 8 à la pile p1.
- transfert successif de deux valeurs de la pile p1 à la pile p2.
- vérification que la pile p1 et vide et que la pile p2 n'est pas vide.

B] Implémentation des files

Q) Sur le même modèle, écrire une implémentation des structures de données de type file.

Implémentations des files à l'aide d'une classe et de piles

On considère le code suivant qui propose :

- une classe Pile permettant d'implémenter les structures de données de type pile ;
- une classe File, dont le code est incomplet, qui permet d'implémenter les structures de données de type file en utilisant un attribut privé de type Pile.

class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_pile_vide(self):
        return self.__valeurs == []

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_pile_vide()):
            return self.__valeurs.pop()
        else:
            return None

class File:
    def __init__(self):
        """Constructeur"""
        self.__donnees = Pile()

    def est_file_vide(self):
        """Méthode qui permet de tester si la file est vide ou non"""
        pass

    def enfile(self, elt):
        """Méthode qui permet d'ajouter elt à la file"""
        pass

    def defile(self):
        """Méthode qui permet d'enlever et de renvoyer le premier élément de la file"""
        pass

1) Compléter les méthodes de la classe File.

2) Proposer quelques lignes de code qui permettent de tester les différentes méthodes de la classe File.