Utiliser une implémentation : interface, mise en œuvre et coût des opérations
Utiliser une structure de données (liste, pile, file, dictionnaire) uniquement à travers son interface, en choisissant parmi plusieurs implémentations celle dont la complexité convient aux opérations les plus fréquentes.

Les points essentiels
- Une interface (ou type abstrait) définit les opérations autorisées sur une structure et leur comportement attendu, sans dire comment les données sont stockées : pour une pile, créer, empiler, dépiler, consulter le sommet, tester si elle est vide.
- Une implémentation est la réalisation concrète de l'interface : choix de la représentation (tableau dynamique, liste chaînée, dictionnaire, programmation objet) et code de chaque opération.
Les mots à connaître
- Interface
- Ensemble des opérations d'une structure de données avec leurs entrées, leurs sorties et leur effet attendu, indépendamment de la manière dont les données sont stockées.
- Implémentation
- Réalisation concrète d'une interface dans un langage : représentation choisie en mémoire et code de chacune des opérations.
Un exemple pour comprendre
On implémente une pile avec une liste Python p = []. Écrire les opérations empiler(p, x), depiler(p), est_vide(p) puis donner l'état de p après : empiler 3, empiler 8, empiler 5, depiler, et le sommet restant. Quelle est la complexité de chaque opération ?
Opérations : empiler(p, x) fait p.append(x) ; depiler(p) fait return p.pop() ; est_vide(p) fait return len(p) == 0. États : après empiler 3, p = [3] ; après empiler 8, p = [3, 8] ; après empiler 5, p = [3, 8, 5] ; depiler renvoie 5 et p = [3, 8]. Le sommet restant est 8, dernier élément de la liste. Complexité : append et pop() en fin de liste sont en O(1) (amorti pour append), len en O(1). L'implémentation par liste convient donc bien à l'interface de pile.

