Un cap pour ce chapitre
Ce que vous saurez faire
- Spécifier les opérations d’une structure.
- Distinguer interface et implémentation.
- Comparer deux réalisations d’un même comportement.
Décrire ce que la structure permet
Une interface décrit les opérations accessibles et leur contrat. Pour une file, on peut proposer créer une file vide, tester si elle est vide, enfiler un élément et défiler l’élément le plus ancien. L’interface précise les paramètres, les résultats, les effets et les conditions d’utilisation. Défiler peut par exemple exiger une file non vide.
Cette description n’impose pas l’organisation en mémoire. Elle indique ce qu’un programme peut demander et ce qu’il peut attendre en retour. Pour l’utiliser correctement, il doit respecter les préconditions ; pour la réaliser correctement, l’implémentation doit garantir les postconditions.
Le contrat doit aussi préciser ce qui ne change pas. Après un retrait, les autres visiteurs restent dans le même ordre. Après une consultation de tête, la taille reste identique. Ces garanties rendent possible un raisonnement sur le programme client sans connaître les cases ni les liens utilisés. Une opération correctement nommée mais insuffisamment spécifiée laisse encore plusieurs comportements incompatibles.
Réaliser le contrat avec un tableau
Une première file peut utiliser une liste Python dont le premier élément est le plus ancien. Enfiler ajoute à droite et défiler retire à gauche. Une autre réalisation peut conserver les éléments dans l’ordre inverse : enfiler à gauche et défiler à droite. Les listes internes diffèrent, mais l’ordre de sortie reste celui des arrivées.
Ces réalisations ne présentent pas nécessairement les mêmes coûts. Déplacer les éléments pour retirer ou ajouter au début d’une liste peut demander un travail proportionnel à sa longueur. La bonne abstraction ne nie pas cette différence ; elle permet de l’étudier séparément du comportement observable.
Changer le mécanisme sans changer le client
Supposons un programme d’accueil qui enfile les visiteurs puis les appelle avec défiler. S’il n’accède qu’aux opérations de l’interface, on peut remplacer le tableau par une réalisation à deux piles sans modifier sa logique. S’il lit directement la case interne 0, il dépend au contraire d’un détail qui peut changer.
Cette discipline facilite les tests. On applique la même suite d’opérations à plusieurs réalisations et on compare les sorties. Une différence révèle un défaut de contrat ou d’implémentation. Des tests réussis ne prouvent pas tous les cas, mais constituent une vérification concrète de l’interchangeabilité annoncée.
Un test commun doit observer les résultats publics et les effets prévus, pas comparer les listes internes. Sinon il déclarerait à tort différente une réalisation qui range les données autrement. Pour tester une file, on peut enregistrer les valeurs renvoyées par les retraits, consulter sa taille si cette opération est exposée et vérifier les refus prévus aux limites.
Choisir des limites explicites
Une file de capacité limitée doit définir ce qui arrive lorsqu’elle est pleine. Une file vide doit également avoir un comportement prévu si une opération de retrait est demandée. On peut imposer une précondition ou produire une erreur documentée ; renvoyer arbitrairement une valeur qui pourrait aussi être une donnée valide créerait une ambiguïté.
L’atelier compare deux listes internes opposées. Il affiche les opérations interdites comme des refus sans modifier la structure. Ce choix pédagogique n’oblige pas toutes les files à gérer les erreurs de cette manière. Le but est d’observer un contrat commun malgré des représentations différentes.
Exemple suivi : rédiger une petite interface
Une file de commandes propose creer(), est_vide(f), enfiler(f,x) et defiler(f). Créer fournit une file vide. Tester la vacuité renvoie un booléen sans modification. Enfiler ajoute x après les éléments présents. Défiler exige une file non vide, renvoie le plus ancien élément puis le retire, sans changer l’ordre des autres.
À partir du vide, enfilez A, enfilez B, défilez, enfilez C, puis défilez deux fois. Les sorties doivent être A,B,C, quelle que soit la représentation. Les états abstraits sont [], [A], [A,B], [B], [B,C], [C], []. Cette trace définit ce qui est observable. Une représentation stockant les éléments à l’envers doit adapter ses opérations pour reproduire exactement cette suite.
Adapter une implémentation et diagnostiquer ses limites
Supposons une capacité de deux éléments. Après l’arrivée de A et B, enfiler C doit suivre une règle documentée : refus avec état conservé, erreur ou autre politique explicitement choisie. Remplacer silencieusement A par C changerait la notion de file si l’interface ne l’autorise pas. Une capacité est une contrainte observable, elle ne peut pas être cachée comme un simple détail interne.
Pour choisir une réalisation, séparez conformité et coût. Une liste peut retirer au début en déplaçant plusieurs cases ; une autre organisation peut éviter ces déplacements mais utiliser davantage de références. Les résultats peuvent rester identiques. Le choix dépend des opérations fréquentes, des tailles et de la simplicité souhaitée. L’abstraction sert à garder stable le besoin exprimé par le client, tout en permettant d’étudier ces compromis et de remplacer le mécanisme lorsque ses garanties restent compatibles.
À vous de faire varier les choses
Une file, deux rangements internes
Choisissez une suite d’arrivées et de départs. Avancez les opérations et vérifiez que les sorties sont identiques malgré les listes inversées.
Lire le résultat de l’expérience initiale
Sorties : A
I range le plus ancien à gauche ; II le range à droite. Les opérations du contrat doivent produire les mêmes sorties.
| Opération | Interne I | Interne II | Résultat I / II |
|---|---|---|---|
| Enfiler A | A | A | Arrivée acceptée |
| Enfiler B | A, B | B, A | Arrivée acceptée |
| Défiler | B | B | A / A |
Le contrat reste stable quand les opérations internes s’adaptent au rangement choisi.
De la compréhension à l’autonomie
À vous de résoudre
Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.
Lire le contrat
Une opération défiler exige une file non vide et renvoie son élément le plus ancien en le retirant. Identifiez précondition, résultat et effet.
Indice 1
Une précondition doit être vraie avant l’appel.
Indice 2
Renvoyer et retirer sont deux propriétés différentes.
Comprendre la correction
La précondition est que la file soit non vide. Le résultat est l’élément entré depuis le plus longtemps parmi ceux encore présents. L’effet est son retrait de la file. Une fonction qui le renverrait sans le retirer respecterait seulement une partie du contrat.
Deux représentations, une sortie
Une file a reçu A, B puis C. L’implémentation I stocke [A, B, C], la II [C, B, A]. Quel élément doit sortir et de quel côté chaque réalisation le retire-t-elle ?
Indice 1
Le premier arrivé reste le même dans les deux cas.
Indice 2
Le côté du retrait dépend de la représentation.
Comprendre la correction
A doit sortir dans les deux cas. La réalisation I retire à gauche, tandis que la II retire à droite. Les contenus internes sont inversés, mais la signification de l’opération reste identique. Retirer à droite dans les deux versions ne respecterait pas le même contrat.
Un client trop curieux
Un programme utilise file.contenu[0] pour obtenir le prochain visiteur. Pourquoi cette instruction fragilise-t-elle le remplacement de la file ?
Indice 1
La première case n’a pas forcément le même sens dans toutes les réalisations.
Indice 2
Cherchez une opération publique exprimant le besoin.
Comprendre la correction
Le programme dépend de l’existence d’un attribut contenu et du choix de ranger le plus ancien élément à l’indice 0. Une autre réalisation peut utiliser deux piles ou un ordre inverse. Il faut demander une opération d’interface, comme consulter la tête, dont le contrat garantit le prochain élément sans exposer son rangement.
L’équivalence ne garantit pas le même coût
Deux files renvoient les mêmes éléments pour toute suite d’opérations valide. Peut-on en déduire qu’elles consomment autant de temps et de mémoire ?
Indice 1
Le comportement observable et la réalisation sont séparés.
Indice 2
Les déplacements internes peuvent différer.
Comprendre la correction
Non. L’équivalence du comportement garantit les mêmes résultats et effets définis par l’interface, pas les mêmes coûts. Une réalisation peut déplacer de nombreux éléments, une autre utiliser des liens ou différer des transferts. Il faut analyser les opérations internes et la mémoire nécessaire selon l’usage attendu.
Une suite qui sépare pile et file
Depuis une structure vide, ajoutez 4, ajoutez 7, retirez, ajoutez 2, retirez, retirez. Donnez les sorties attendues pour une file puis pour une pile. Expliquez pourquoi ce test distingue les deux contrats malgré les mêmes noms de méthodes.
Indice 1
La file retire le plus ancien ; la pile retire le plus récent.
Indice 2
Conservez le contenu restant après chaque retrait.
Comprendre la correction
Pour la file, les sorties sont 4,7,2. Pour la pile, elles sont 7,2,4. Les structures utilisent les mêmes valeurs et peuvent exposer des noms proches, mais elles n’offrent pas le même ordre. Ce scénario est donc plus informatif que l’ajout puis le retrait d’un unique élément.
Le refus doit préserver la file
Une file de capacité deux refuse un ajout lorsque sa taille atteint deux. On ajoute A,B,C, puis on retire deux fois. Donnez les sorties et l’état après le refus. Un programme qui remplace A par C respecte-t-il cette interface ?
Indice 1
Le refus annoncé ne retire aucun élément ancien.
Indice 2
Les effets interdits font aussi partie du contrat.
Comprendre la correction
Après le refus de C, la file reste A,B. Les sorties sont A puis B. Remplacer A par C détruit une commande acceptée auparavant et viole le contrat de refus sans modification. La limitation de capacité n’autorise pas implicitement une politique d’écrasement.
Un client indépendant
Un client veut afficher le prochain visiteur sans le retirer. Il lit actuellement f.contenu[0]. Proposez une opération publique avec précondition, résultat et effet. Expliquez comment une représentation inversée peut la réaliser.
Indice 1
Le besoin est une consultation et non un retrait.
Indice 2
La position interne du plus ancien dépend du rangement.
Comprendre la correction
On peut définir tete(f) avec précondition file non vide, résultat égal au plus ancien élément et aucun effet sur la file. Une représentation normale consulte sa première case ; une représentation inversée consulte la dernière. Le client appelle la même opération et conserve sa logique, sans connaître le rangement.
Les erreurs qui méritent un détour
- Définir une interface comme un écran graphique.
- Ici, le mot désigne le contrat des opérations offertes à un programme. Le contexte détermine son sens.
- Supposer qu’une représentation correcte est optimale.
- Un même contrat peut admettre plusieurs compromis de temps, mémoire et simplicité.
La fiche à garder
L’essentiel à retenir
- L’interface décrit les opérations et leurs contrats.
- L’implémentation réalise ces opérations avec une organisation concrète.
- Un client fondé sur l’interface dépend moins des détails internes.
Le prochain pas
- Listes comme structures abstraites et listes chaînées
- Les piles : comprendre le fonctionnement LIFO
- Les files : comprendre le fonctionnement FIFO
- Modules, bibliothèques, API et documentation
Retrouver le catalogue de Terminale
Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.