Interface d'une structure de données : séparer ce qu'on peut faire de la façon dont c'est codé
Définir l'interface d'une structure de données (liste, pile, file, dictionnaire) comme un ensemble d'opérations, la distinguer de son implémentation et comparer la complexité des opérations selon l'implémentation choisie.

Les points essentiels
- L'interface d'une structure de données est la liste de ses opérations (nom, paramètres, rôle, effet), indépendamment du code qui les réalise : c'est le contrat que doit respecter toute implémentation.
- L'implémentation est la façon concrète de réaliser ce contrat : choix des variables, du type de support (tableau, liste chaînée, table de hachage) et du code de chaque opération.
Les mots à connaître
- Interface
- Ensemble des opérations qu'une structure de données propose à l'utilisateur, avec leur signature et leur comportement attendu, sans préciser comment elles sont codées.
- Implémentation
- Réalisation concrète d'une interface dans un langage : choix de la représentation des données et code de chaque opération.
Un exemple pour comprendre
On implémente une pile avec une liste Python : la tête de pile est le dernier élément de la liste. Écrire les opérations empiler, depiler et est_vide, puis donner leur complexité. Que contient la pile après : p = []; empiler(p, 3); empiler(p, 7); x = depiler(p) ?
def est_vide(p): return len(p) == 0 def empiler(p, x): p.append(x) def depiler(p): return p.pop() # suppose p non vide append et pop() en fin de liste sont en O(1) (amorti pour append), len est en O(1) : les trois opérations sont donc en temps constant. Déroulé : après empiler 3, p = [3] ; après empiler 7, p = [3, 7] ; depiler renvoie 7 (dernier empilé, comportement LIFO) et p = [3], donc x = 7. L'utilisateur n'a utilisé que l'interface.

