Structures de données, interface et implémentation

Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

L'essentiel

Une structure de données est une façon d'organiser des données et un ensemble d'opérations pour les manipuler. Le cœur du programme de Terminale consiste à séparer deux niveaux.

Le type abstrait de données (ou interface) décrit ce qu'on peut faire : les opérations, leurs paramètres, ce qu'elles renvoient, et leurs propriétés (par exemple « depiler renvoie le dernier élément empilé »). On ne dit jamais comment c'est codé.

L'implémentation est la réalisation concrète : on choisit une représentation interne (un tableau, une liste chaînée, un dictionnaire) et on écrit le code des opérations. Une même interface admet plusieurs implémentations.

Cette séparation s'appuie sur l'encapsulation : le code qui utilise la structure ne dépend que de l'interface. On peut donc optimiser ou changer complètement l'implémentation sans toucher au code client.

Formules et schémas clés

Interface de la pile (LIFO, dernier entré premier sorti) : \text{empiler}(p, x), \quad \text{depiler}(p), \quad \text{est\_vide}(p)

Interface de la file (FIFO, premier entré premier sorti) : \text{enfiler}(f, x), \quad \text{defiler}(f), \quad \text{est\_vide}(f)

Complexités typiques selon l'implémentation :

| Opération | Tableau (liste Python) | Liste chaînée | |---|---|---| | accès indice i | O(1) | O(n) | | insertion en tête | O(n) | O(1) | | ajout en fin | O(1) amorti | O(1) avec pointeur de queue |

Méthode type bac

1. Lire l'énoncé pour repérer l'interface demandée (quelles opérations ?). 2. Choisir une implémentation adaptée aux opérations les plus fréquentes. 3. Coder en respectant strictement les noms et le comportement attendus. 4. Vérifier les cas limites : structure vide, un seul élément. 5. Justifier la complexité de chaque opération.

Pièges

  • Ne pas confondre interface (le quoi) et implémentation (le comment) : c'est l'erreur classique.
  • Une pile et une file ont la même interface en apparence mais des comportements opposés (LIFO contre FIFO).
  • En Python, list.pop() retire en fin (sommet de pile) ; list.pop(0) retire en tête mais coûte O(n) : à éviter pour une file efficace.
  • Toujours traiter le cas de la structure vide (lever une erreur ou renvoyer une valeur convenue).

Pour l'épreuve

Le correcteur attend que vous nommiez clairement les opérations de l'interface, que vous choisissiez une implémentation cohérente et que vous justifiiez chaque complexité. À l'épreuve pratique, on demande souvent de compléter une classe : respectez les signatures fournies et gérez le cas vide. Citer l'encapsulation comme justification de la séparation interface/implémentation est valorisé.