Structures de données et interfaces

Une structure de données organise des valeurs et propose des opérations. Une interface décrit les opérations accessibles, leurs paramètres, leurs résultats et leurs conditions d’utilisation. Elle ne décrit pas nécessairement les instructions qui les réalisent. Une implémentation choisit une représentation et des algorithmes pour respecter ce contrat. L’abstraction consiste à raisonner sur les propriétés utiles sans dépendre de tous les détails internes. Ici, le mot interface ne désigne pas un écran : il désigne la frontière entre le programme utilisateur et la structure qu’il utilise.

Pour notre file, creer() produit une file vide ; ajouter(f, x) place x à la fin ; est_vide(f) renvoie un booléen ; retirer(f) enlève et renvoie la valeur la plus ancienne. La précondition de retirer est que la file ne soit pas vide. La postcondition précise le résultat et le nouvel état : si l’état abstrait est [a, b, c], retirer renvoie a et laisse [b, c]. Ajouter modifie la structure et ne renvoie ici aucune valeur utile. Cette précision évite de confondre une modification avec le résultat d’une fonction.

Une réalisation directe place les valeurs dans une liste Python, de la plus ancienne à la plus récente. L’invariant de représentation est la propriété qui doit rester vraie après chaque opération : l’ordre de la liste correspond à l’ordre d’arrivée des valeurs encore présentes. Ajouter en fin conserve cet ordre. Retirer au début enlève bien la plus ancienne. Le code ci-dessous est volontairement simple. Les retraits dans les blocs Python indiquent l’appartenance aux fonctions et aux boucles ; recopie quatre espaces par niveau.

La correction fonctionnelle ne dit pas tout sur le coût. Retirer au début d’une liste Python oblige à décaler les références des éléments suivants. Pour n valeurs, le coût dépend donc de n. Un ajout en fin est généralement peu coûteux, avec des réallocations occasionnelles. On distingue ici l’ordre de grandeur du coût et une durée mesurée sur une machine. Quelques essais chronométrés ne prouvent pas une loi universelle ; ils peuvent seulement illustrer un modèle que l’on explique. Le choix de l’implémentation dépend du nombre d’opérations et des contraintes du programme.

Une pile autorise l’ajout et le retrait à la même extrémité. Avec deux piles, on peut pourtant obtenir l’ordre d’une file. Les nouvelles valeurs entrent dans une pile entree. Une pile sortie fournit les valeurs à retirer. Quand sortie est vide, on y transfère toutes les valeurs de entree en les retirant une à une. Le transfert inverse leur ordre : la plus ancienne devient alors accessible au sommet de sortie. Tant que sortie contient des valeurs, on n’y transfère rien. Ce dernier point est essentiel pour conserver la priorité des anciennes demandes.

L’état abstrait correspond aux valeurs de sortie lues depuis son sommet, suivies des valeurs de entree lues dans leur ordre d’ajout. Cette relation permet de vérifier la correction au-delà d’un exemple. Ajouter prolonge la seconde partie. Retirer enlève la tête de la première partie ; si elle est vide, le transfert recrée cette partie en conservant l’ordre abstrait. Chaque valeur est ajoutée à entree, transférée au plus une fois, puis retirée de sortie. Une série d’opérations évite ainsi les décalages répétés du tableau, même si un retrait particulier peut déclencher un transfert long.

Pour tester une interface, le programme de test doit passer par ses opérations. S’il lit les clés entree ou sortie, il vérifie des détails de la seconde implémentation plutôt que la compatibilité du service. On peut garder en parallèle une liste de référence, calculer l’ordre attendu et comparer chaque retrait. Pour une file vide, on vérifie est_vide avant retirer : l’absence de résultat sur ce cas vient ici de la précondition. Un sujet peut imposer une exception ou une autre convention ; c’est alors cette convention qu’il faut respecter.

S’entraîner : ouvre l’espace Exercices du site.