Introduction

Pour résoudre certains problèmes il est utile de manipuler des structures de données. Par exemple, lorsque l’on aura à parcourir un graphe, on sera à utiliser ces structures de données pour manipuler l’information lors de notre parcours.

Ces structures sont dites linéaires car les données sont stockées l’une après l’autre sans hiérarchie complexe, par opposition à d’autres structures de données, notamment les structures arborescentes que nous étudierons également.

On parle de type abstrait de données parce qu’on s’intéresse aux opérations que l’on peut effectuer de manière abstraite, dans notre esprit en quelque sorte. Dans un second temps uniquement on pourra être amené à implémenter ces structures en mémoire, en Python ou dans un autre langage de programmation. A ce moment là on parlera de structures de données.

Piles

Pour une pile vous pouvez prendre l'image d'une pile d'assiettes que vous devez laver. Vous commencez par prendre l'assiette du dessus et vous la lavez. Une fois lavée vous la ranger et vous prenez l'assiette suivante, ainsi de suite.

La dernière assiette sur la pile est la première assiette retirée. On dit que la pile fonctionne en mode LIFO : Last In, First Out (dernier arrivé, premier sorti).

Quelques opérations d'une Pile :

• Créer une pile vide PileVide() → Pile.
• Ajouter un élément Empiler(e : Element) (push)
• Renvoie l'élément se situant au sommet de la pile et le retire Dépiler(P: Pile) -> Element (pop)
• Tester si une liste est vide : EstVide(P: Pile) → Booléen renvoie Vrai si la pile est vide et Faux sinon.
• Renvoyer le nombre d'éléments présents dans la pile : Taille(P : Pile) -> entier
• Renvoyer l'élément se situant au sommet de la pile sans le retirer Sommet(P : Pile) -> Element

Implémentations en Python

Maintenant que l'on a définit notre type Pile, on peut se demander comment on va implémenter une Pile en Python. Pour cela on a plusieurs choix possibles.

Si on choisit de le faire sans créer de classes alors cela pourrait être fait directement à l'aide de la structure de données list Python :

    pile = []
    pile.append(1)
    pile.append(2)
    pile.append(3)

    print(pile.pop())
    print(pile.pop())

Question

Quelles valeurs sont affichées et quelles valeurs sont présentes dans la Pile après la dernière instruction ?

On pourrait également choisir de créer une classe Pile qui utilise une structure de données que l'on appelle une liste chainée:

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None

class Pile:
    def __init__(self):
        self.tete = Noeud("tête")
        self.taille = 0

    # Récupérer la taille de la pile
    def get_taille(self):
        return self.taille
    # Vérifier si la pile est vide
    def est_vide(self):
        return self.taille == 0

    # Ajouter d'autres méthodes
    ...

Files

S'imaginer une file d'attente.

Contrairement à la Pile qui fonctionnait sur le principe LIFO : Last In, First Out, la file fonctionne elle sur le principe premier arrivé, premier sorti ou FIFO : First In First Out.

Quelques opérations d'une File :

• Créer une file vide FileVide() → File.
• Consulter le premier élément de la file: la tête Tete(F : File) -> Element.
• Tester si la file est vide EstVide(F: File) → Booléen renvoie Vrai si la file est vide et Faux sinon..
• Enfiler un nouvel élément Enfiler(e : Element)
• Défiler un élément, supprime et renvoie le premier élément Defiler(e : Element) -> Element

Implémentations en Python

On peut choisir d'implémenter une File en utilisant à nouveau la structure de données list de Python.

    file = []

    # Enfiler
    file.append(1)
    file.append(2)
    file.append(3)

    # Dépiler
    print(file.pop(0))

Cela n'est pas un bon choix en terme de performance car lors de l'appel à la méthode pop() nous devrons supprimer le premier élément de la liste, et cette opération est de complexité ...

A vous de jouer

Déterminer la complexité de cette opération dans le pire des cas en étudiant la documentation officielle :
https://wiki.python.org/moin/TimeComplexity

Cela illustre l'importance de la structure de données choisie lors de l'implémentation.

Nous verrons en TP d'autres implémentations de Files.

Listes

Attention

Il ne faut pas confondre la structure de données list de Python avec le type abstrait liste ci-dessous. En effet, on est ici en train de définir de manière quasi mathématiques un type et des opérations. Un peu comme on pourrait définir par exemple ce qu'est un entier en mathématiques et les opérations arithmétiques que l'on pourrait effectuer sur ces entiers (Les ajouter, les multiplier etc).

Une liste notée L est un conteneur d'éléments et est composée de sa tête qui correspond aux dernier élément ajouté et de la queue qui correspond aux restes des éléments de la liste privée de son premier élément. On peut définir les opérations suivantes sur une liste :

• Créer une liste vide : ListeVide() → Liste.
• Tester si une liste est vide : EstVide(L: Liste) → Booléen renvoie Vrai si la liste est vide et Faux sinon.
• Ajouter un élément e en tête de liste : Ajout(L : Liste, e: Element)
• Supprimer la tête e et renvoyer cet élément : SupprEnTete(L : Liste) -> Element
• Renvoyer le nombre d'éléments présents dans la liste : Longueur(L : Liste) -> entier
• Renvoyer l'élément en tête de la liste Tete(L : Liste) -> Element
• Renvoyer la liste privée de son premier élément Queue(L : Liste) -> Liste
• Renvoyer le \(i\) ème élément de la liste GetElement(L : Liste, i : entier) -> Element

Exercice

A la fin quels éléments sont présents dans le type abstrait Liste et dans quel ordre ?

L = ListeVide()
Ajout(2,L)
SupprEnTete(L)
Ajout(3,L)
Ajout(1,L)

Dans quels cas utiliser une Liste, une Pile ou une File ?

Nous verrons plus en détail l'utilisation de ces types abstraits pour résoudre des problèmes algorithmiques lorsque nous étudierons les arbres et les graphes.

Mais généralement, nous pouvons donner quelques indications sur l'utilisation de l'une ou l'autre de ces types :

• Lorsque l'on souhaite récupérer les données dans le même ordre où on les a entrées, alors on utilisera une File.
• Lorsque l'on souhaite récupérer les données dans l'ordre inverse où on les a entrées, alors on utilisera une Pile.
• Quand on se préoccupe pas de l'ordre dans lequel on a entré les données et qu'on souhaite récupérer des données selon un index spécifique, alors on pourra utiliser une liste.

Ce ne sont que des indications, il faudra bien étudier le problème à résoudre avant de choisir telle ou telle type.

Importance de l'implémentation

Jusque là on est resté relativement dans l'abstraction, mais l'implémentation dans un langage de programmation est tout aussi importante. En effet, les performances notamment ne seront pas identiques en fonction de la manière dont on implémentera telle ou telle type abstrait.

Bonus

Vidéo du MIT (en anglais) :