GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Files ======

{{ .:piles_et_files.fiche.pdf |Fiche à imprimer}}

Une file est une sorte de [[nsi:terminales:structures:liste_abstraite|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 =====

{{ .:files-1.png?nolink&400|}}

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) :

<WRAP group>
<WRAP half column>
<code lang-none linenums>
F = CREER_FILE_VIDE()
ENFILER(F, 'X')
ENFILER(F, 'B')
ENFILER(F, 'E')
DEFILER(F)
ENFILER(F, 'Y')
</code>
</WRAP>
<WRAP half column>
<code lang-none linenums>
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))
</code>
</WRAP>
</WRAP>

==== Exercice 2 - Pile ou File ? ====

Entre [[liste_abstraite|listes]], [[pile_abstraite|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

<WRAP info>
==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.
</WRAP>