Vide ou pleine : le témoin qui ment

Mesuré, avec une capacité de $8$ :

file neuve          : debut=0 fin=0   est_vide dit VIDE       correct
apres 8 enfilages   : debut=0 fin=0   est_vide dit VIDE       FAUX
   or le tableau contient [100 101 102 103 104 105 106 107]

Le défaut nommé. L'indice fin avance modulo $8$ ; après huit enfilages il a fait un tour complet et revient sur $0$. Les deux états « aucun élément » et « huit éléments » ont donc le même témoin, et aucune fonction ne peut les distinguer. Ce n'est pas un défaut de codage : c'est un défaut de représentation — deux états du monde, une seule image.

Les deux parades.

• Retenir $n$, le nombre d'éléments, comme le fait le cours : est_vide teste $n=0$ et est_pleine teste $n=C$. Les deux états deviennent discernables, la capacité utile reste $C$, et fin n'est plus nécessaire puisqu'il vaut $(\text{debut}+n)\mathrm{mod}C$. Coût : un champ.
• Laisser toujours une case libre : on refuse d'enfiler quand $(\text{fin}+1)\mathrm{mod}C=\text{debut}$. Les deux états sont alors distincts, mais la capacité utile tombe à $C-1$ — mesuré : $7$ éléments pour un tableau de $8$. Coût : une case.

Comment trancher. Si les éléments sont gros et la capacité petite, une case perdue coûte plus qu'un entier : on retient $n$. Si la structure est manipulée par plusieurs fils d'exécution, la seconde parade a un avantage réel — elle n'a que deux champs à mettre à jour au lieu de trois, ce qui limite les états intermédiaires incohérents (chapitre chap:concurrence).

Ce que l'exercice enseigne au-delà des files. Avant d'écrire une structure, comptez les états qu'elle doit distinguer et les valeurs que sa représentation peut prendre. Si les seconds sont moins nombreux que les premiers, la représentation est fausse, et aucun soin apporté au code ne la sauvera. Ici : $C+1$ tailles possibles ($0$ à $C$) contre $C$ valeurs possibles pour la différence des deux indices.