Structure de File
Méthode : Notation des types
Tout comme les piles, nous noterons File[T] une structure de données nommée File et dont tous les éléments sont de type T.
Définition : Primitives
Nous avons donc nos quatre premières primitives simples 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.est_vide(File[T]) -> bool: renvoie un booléen indiquant si la file passée en paramètre est vide ou non.enfiler(File[T], T) -> None: ajoute un élément de type T à l'arrière de la file.defiler(File[T]) -> T: retire et renvoie l'élément à l'avant de la file.
Remarque : English version
In English, we refer to this as a queue, to which elements can be enqueue() or dequeue().
Quelques exemples d'utilisation des files
Exemple : Bataille
Prenons en compte 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 Eliott et Rémi. Nous pouvons donc créer deux paquets de cartes de cette manière :
paquet_eliott = creer_file()
paquet_remi = 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_eliott):
print("Eliott 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_eliott = defiler(paquet_eliott)
carte_remi = defiler(paquet_remi)
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_eliott) > valeur(carte_remi):
enfiler(paquet_eliott, carte_eliott)
enfiler(paquet_eliott, carte_remi)
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é.
Exemple : Système d'exploitation multitâches
Un système d’exploitation multitâche, comme Linux, permet à un utilisateur d’exécuter plusieurs tâches informatiques simultanément.
Prenons un exemple simple avec Linux. Supposons que nous sommes en train d’écrire un document dans un éditeur de texte, tout en écoutant de la musique via un lecteur de musique, et en téléchargeant un fichier à partir d’Internet. Toutes ces tâches semblent s’exécuter simultanément.
Voici comment cela fonctionne :
1ère étape : nous commençons à écrire dans l’éditeur de texte. Le système d’exploitation donne du temps CPU à ce processus
2ème étape : nous décidons d’écouter de la musique. Nous ouvrons notre lecteur de musique et commençons à jouer une chanson. Le système d’exploitation interrompt temporairement l’éditeur de texte et donne du temps CPU au lecteur de musique.
3ème étape : nous revenons à notre document et continuons à taper. Le système d’exploitation interrompt temporairement le lecteur de musique et redonne du temps CPU à l’éditeur de texte.
4ème étape : nous décidons de télécharger un fichier. Nous ouvrons notre navigateur web et commençons le téléchargement. Le système d’exploitation interrompt temporairement l’éditeur de texte et donne du temps CPU au navigateur web.
Le système d’exploitation continue à alterner entre ces trois processus, donnant à chacun un peu de temps CPU. Cela se fait si rapidement qu'on a l’impression que toutes ces tâches sont exécutées simultanément.