Structure de file
Étape 1 : Concevoir le cahier des charges (TAD)
Une file est un type abstrait de données contenant un ensemble d'éléments, dont l'élément ajouté en premier est accessible.
Nous nommons notre structure de file avec le nom File[T] dont tous ces éléments sont de type T.
Les Primitives
Nous avons donc nos quatre premières primitives qui vont nous permettre de créer et manipuler notre file :
creer_file(): File[T] : crée une file vide et renvoie cette nouvelle file.estVide(): File[T] -> Booléen : renvoie un booléen indiquant si la file passée en paramètre est vide ou non.enfiler(): File[T], T -> File[T] : ajoute un élément de type T en queue de file.defiler(): File[T] -> File[T], T : retire et renvoie l'élément au sommet de la file.
Jeu de cartes
Prenons en exemple le jeu de cartes appelé Bataille. Dans ce jeu, chaque joueur a un paquet de cartes et joue la carte du dessus de son paquet à chaque tour. Le gagnant du tour récupère les cartes jouées et les place au bas de son paquet.
En plus des cartes jouées au centre de la table, nous devons garder en mémoire le paquet de cartes de chaque joueur. Comme les cartes sont ajoutées à une extrémité du paquet et retirées à l’autre, la méthode premier entré, premier sorti des files est exactement ce dont nous avons besoin pour ces ensembles.
Supposons que les joueurs s’appellent Alice et Bob. Nous pouvons donc créer deux paquets de cartes de cette manière :
paquet_alice = creer_file()
paquet_bob = creer_file()
Une opération de distribution des cartes peut ensuite être effectuée pour placer les cartes de départ dans ces deux paquets.
Passons maintenant à quelques aspects de la réalisation d’un tour de jeu. Au début d’un tour, un joueur perd s’il n’a plus de cartes dans son paquet.
def tour():
if est_vide(paquet_alice):
print("Alice perd")
Si la partie n’est pas terminée, le jeu demande alors à chaque joueur de tirer sa première carte. Cela signifie
retirer la première carte du paquet de chaque joueur, avec l’opération defiler().
carte_alice = defiler(paquet_alice)
carte_bob = defiler(paquet_bob)
Si l’un des joueurs gagne ce tour, on peut alors remettre ces deux cartes au fond de son paquet, c’est-à-dire
à l’arrière de sa file de cartes, avec l’opération enfiler().
if valeur(carte_alice) > valeur(carte_bob):
enfiler(paquet_alice, carte_alice)
enfiler(paquet_alice, carte_bob)
Nous supposons ici que nous disposons d’une fonction valeur() permettant de comparer les cartes.
La réalisation complète de ce jeu nécessite plus de travail, car il faut gérer la distribution des cartes et les cas d’égalité.
Étape 2 : Proposer une implémentation
À vous de le découvrir !