Développement 1.1 (suite)
Files
Une file, comme une pile, est une structure abstraite de données possédant trois opérations essentielles :
- enqueue
-
ajoute une donnée à la structure.
- dequeue
-
retire et renvoie la donnée la plus ancienne contenue dans la structure.
- empty
-
identifie une file vide (dequeue n'est pas définie sur une
pile vide).
Remarque La situation représentée par une file est alternativement désignée par l'acronyme «FIFO» (First In, First Out) : le premier arrivé est le premier sorti.
-
Chaînée. Reprenez le programme de test du premier exercice du sujet sur les piles et appliquez-le à une file de caractères.
-
Extras. Ajoutez à la file du précédent exercice le support des opérations optionnelles first (qui renvoie l'élément le plus ancien sans le retirer de la file) et clear (qui retire tous les éléments de la file). Notez que contrairement à clear, first n'est pas une simple combinaison des opérations normales, mais bien une nouvelle fonctionnalité.
-
Simon. Le jeu du Simon est un gadget électronique qui teste la mémoire.
Écrivez un programme qui affiche une fenêtre comportant quatre zones séparées. Dans la première phase, le programme met graphiquement en valeur durant une seconde une zone choisie au hasard. Le choix est mémorisé dans une file. Dans la deuxième phase, le joueur choisit dans quelle zone cliquer. Son choix est comparé au choix tiré de la file, et le jeu se termine s'il s'est trompé. Si la deuxième phase est fidèle à la première phase, on refait une première phase avec un choix de plus.
-
Remplaçant. Recodez les fonctions qui représentent les cinq opérations sur une file pour qu'elle utilisent un tableau (dynamique) à la place d'une liste chaînée et faites marcher les exercices précédents avec cette nouvelle version.
On doit pouvoir compiler chaque exercice pour utiliser soit une liste chaînée, soit un tableau rien qu'en changeant la liste des fichiers sources dans le
Makefile. Si ce n'est pas déjà fait, définissez et utilisez un constructeur et un destructeur : des fonctions pour respectivement créer et détruire la file. -
Traînée. Un personnage se déplace dans une grille de 10 colonnes par 10 lignes. On souhaite afficher à la fois la position actuelle du personnage et les 7 dernières cases visitées.
Écrivez un programme dont l'apparence s'inspire de cette maquette et qui permet de déplacer le personnage dans les quatres directions avec les flèches (un déplacement qui franchit un bord ramène le personnage sur le bord opposé). À quoi peut servir une file dans ce problème ?