Files

Une file est une sorte de liste mais pour laquelle on s'intéresse surtout à la façon de faire entrer et sortir les données.

On pourra adopter la même notation que pour les listes. Par exemple, 3:85:17:9 est une pile dans laquelle on a ajouté, dans l'ordre, 3, 85, 17 et 9.

FIFO

Il faut penser à une file d'attente.

Un nouveau venu se met à la fin de la file.
Le premier à sortir de la file est celui qui est devant et qui attend depuis le plus longtemps.

Donc, quand on retire un élément, c'est toujours le plus ancien à avoir été ajouté.

On parle de FIFO = First In First Out, c'est à dire Premier entré, premier sorti.

C'est le principe de la file d'attente ou encore des denrées périssables sur les rayonnages des magasins.

Interface

Méthode	Description
CREER_FILE_VIDE()	Renvoie une file de contenu vide
EST_VIDE(F)	Renvoie vrai si la file est vide
ENFILER(F, e)	Ajoute l'élément e en queue de file
DEFILER(F)	Enlève l'élément en tête de file le renvoie précondition : file non vide

Taille maximale ?

Pour une file c'est surtout le mode d'enfilement et de défilement qui importe. Il n'est pas indispensable que la taille de la file puisse augmenter indéfiniment comme dans une Liste. Il est donc courant de créer une file en prévoyant un espace mémoire maximal, si bien qu'il peut arriver que la file soit pleine.

Dans ce cas, on a dans l'interface :

Méthode	Description
CREER_FILE_VIDE(taille)	Renvoie une file de contenu vide avec une taille max spécifiée
EST_PLEINE(F)	Renvoie vrai si la pile est pleine
ENFILER(F)	Ajoute l'élément e en queue de file précondition : file non pleine

Exercices

Exercice 1

Donner la file F obtenue après exécution des lignes suivantes (dans les deux cas) :

F = CREER_FILE_VIDE()
ENFILER(F, 'X')
ENFILER(F, 'B')
ENFILER(F, 'E')
DEFILER(F)
ENFILER(F, 'Y')

G = CREER_FILE_VIDE()
ENFILER(G, 51)
ENFILER(G, 3)
F = CREER_FILE_VIDE()
ENFILER(F, DEFILER(G))
ENFILER(F, 17)
ENFILER(F, DEFILER(G))

Exercice 2 - Pile ou File ?

Entre listes, piles et files, choisissez la structure de donnée qui vous parait le plus adaptée pour les cas suivants :

Gestion d'un répertoire téléphonique.
Mémorisation des actions dans une applications de dessin afin de permettre le retour en arrière - Undo.
Envoyer des fichiers à un serveur d'impression.
Buffer clavier

Buffer clavier

Le clavier utilise une mémoire tampon (buffer) pour mémoriser les touches appuyées car le PC n'est peut-être pas disponible à ce moment précis. Le clavier envoie une requête au PC et quand celui-ci est disponible, il vient lire le contenu du buffer. Il peut arriver que le PC soit bloqué dans un travail et qu'alors le buffer se remplit sans se vider. Quand il est plein, le clavier envoie une alarme.