Voir la source de File (structure de données)

{{Voir homonymes|File}}
{{Voir homophones|Fil|Phil}}
En [[informatique]], une '''file''' dite aussi '''file d'attente''' (en anglais '''''{{langue|en|queue}}'''''{{note|groupe=alpha|''{{langue|en|queue}}'' est le terme anglais emprunté au français, tandis que {{langue|en|file}} désigne dans cette langue un [[Fichier informatique|fichier]].}}) est un [[type abstrait]] basé sur le principe « [[Premier entré, premier sorti (gestion)|premier entré, premier sorti]] » ou PEPS, désigné en anglais par l'acronyme FIFO ({{citation étrangère|langue=en|first in, first out}}) : les premiers éléments ajoutés à la file seront les premiers à en être retirés.

== Description ==
[[Fichier:FIFO PEPS.png|vignette|''{{Langue|en|First In First Out}}'' - Premier Entré Premier Sorti.]]
Le type décrit le fonctionnement d'une [[file d'attente]] : les premiers arrivés seront les premiers à sortir<ref name="Aho">Cf.  {{Ouvrage
|langue=fr |trad=J.-M. Moreau|prénom1=Alfred|nom1=Aho|prénom2=John|nom2=Hopcroft|lien auteur2=John Hopcroft|prénom3=Jeffrey|nom3=Ullman|lien auteur3=Jeffrey Ullman|titre=Structures de données et algorithmes|lieu=Paris|éditeur=InterÉditions|année=1995|pages totales=450|isbn=978-2-7296-0194-2|chap=Types de données abstraites élémentaires|passage=58-62}}</ref> ([[Premier entré, premier sorti (gestion)|PEPS]], FIFO en anglais pour ''{{lang|en|First in, first out}}''). 

Quand le dernier entré est le premier à sortir (DEPS, LIFO pour ''{{langue|en|[[Last in, first out]]}}'' en anglais), c'est une ''[[Pile (informatique)|pile]]'' (''{{langue|en|stack}}'').

Par exemple, les [[Algorithme|algorithmes]] basés sur le principe des files,  et utilisés pour suivre les stocks, se doivent d'être cohérents avec la méthode utilisée en [[Stock|gestion des stocks]].

Une [[liste chaînée]] dont on n'utilise que les opérations ''ajouterQueue'' et ''retirerTête'' constitue une queue. Si la queue se base sur un [[Tableau (structure de données)|tableau]], la structure enregistre deux indices, l'un correspondant au dernier arrivé, l'autre au prochain à sortir<ref>{{harvsp|Bachelet|2011}}.</ref>.

Les queues servent à organiser le traitement séquentiel des blocs de données d'origines diverses.

La [[théorie des files d'attente]], élaborée pour le dimensionnement des réseaux téléphoniques, relie le nombre d'usagers, le nombre de canaux disponibles, le temps d'occupation moyen du canal, et les temps d'attente à prévoir<ref>{{Ouvrage|prénom1=Michel |nom1=Fleutry |titre=Dictionnaire encyclopédique d'électronique |sous-titre=anglais-français |éditeur=La maison du dictionnaire |lieu=Paris |année=1991 |pages totales=1054 |passage=699 |isbn=2-85608-043-X}} ; {{Ouvrage |langue=en |prénom1=R.L. |nom1=Brewster |titre=Telecommunications technology |éditeur=Ellis Horwood |lieu=Chichester, UK |année=1986 |passage=45 |isbn=}}.</ref>.

== Limites de la méthode ==
Dans un [[logiciel]] [[informatique]], l'avantage de cet [[Théorie de l'ordonnancement|ordonnancement]] réside dans sa relative simplicité ; cependant elle pénalise les [[processus (informatique)|processus]] à temps bref d'exécution : en effet, si on lance, à la suite d'un processus qui demande beaucoup de temps de calcul, une petite tâche (par exemple, dans un serveur qui ne gère qu'une imprimante, imprimer une page), la petite tâche devra attendre la fin de la tache qui demande beaucoup plus de temps (imprimer cent pages) avant de s'exécuter. 

À l'époque des machines à un seul [[processeur]], c’était la technique la plus fiable pour être sûr d'effectuer les opérations dans un ordre logique<ref>Cf. {{Lien web|titre=Files d'attente|site=Université P. et M. Curie Paris -- Systèmes d'exploitation des ordinateurs|url=https://www-int.impmc.upmc.fr/public/Enseignement/ye/informatique/systemes/chap5/521.html}}</ref>.

Cet algorithme est également utilisé comme [[Algorithme de mise en cache|politique de remplacement des lignes de cache]] en raison de sa simplicité d'[[Mise en œuvre|implémentation]] et de son faible coût. Néanmoins, il présente dans cet usage une anomalie connue sous le nom d'[[anomalie de Belady]] : augmenter le nombre d'étages de la file peut avoir un effet négatif sur la performance.

== Applications ==
Ce type est utilisé par exemple :
* en général, pour mémoriser temporairement des transactions qui doivent attendre pour être traitées ;
* les [[Serveur d'impression|serveurs d'impression]], qui traitent ainsi les requêtes dans l'ordre dans lequel elles arrivent, et les insèrent dans une file d'attente (dite aussi queue ou ''[[Spooling|spool]]'') ;
* certains moteurs [[multitâche]]s, dans un [[système d'exploitation]], qui doivent accorder du [[Temps CPU|temps-machine]] à chaque tâche, sans en privilégier aucune ;
* un [[algorithme de parcours en largeur]] utilise une file pour mémoriser les nœuds visités ;
* pour créer toutes sortes de [[Mémoire tampon|mémoires tampons]] (en anglais {{citation étrangère|langue=en|buffers}}) ;
* En [[Stock|gestion des stocks]] les algorithmes doivent respecter la gestion physique des stocks pour assurer la cohérence physique/valorisation.

== Primitives ==
[[Fichier:PrimitivesFile.png|vignette|Les deux primitives de base]]
Voici les [[Fonction primitive|primitives]] communément utilisées pour manipuler des files. Il n'existe pas de normalisation pour les primitives de manipulation de file. Leurs noms sont donc indiqués de manière informelle<ref name="Aho"/>.

* « Enfiler » : ajoute un élément dans la file. Le terme anglais correspondant est ''{{langue|en|enqueue}}''.
* « Défiler » : renvoie le prochain élément de la file, et le retire de la file. Le terme anglais correspondant est ''{{langue|en|dequeue}}''.
* « La file est-elle vide ? » : renvoie « vrai » si la file est vide, « faux » sinon.
* « Nombre d'éléments dans la file » : renvoie le nombre d'éléments dans la file.

=== Exemple en C# ===
{{Boîte déroulante/début|titre=Exemple en C#}}
<syntaxhighlight lang="csharp">
using System;

namespace ExempleFile
{
    public class File
    {
        private object[] _File;
        private int _PointeurDeTete;
        private int _PointeurDeQueue;
        private int _Taille;
        private int _NbreElements;

        #region Constructeur
        public File(int Taille)
        {
            this._Taille = Taille;
            this._File = new object[Taille];
            this._PointeurDeTete = 0;
            this._PointeurDeQueue = 0;
            this._NbreElements = 0;
        }
        #endregion

        #region Fonctions
        public virtual void Enfiler(object item)
        {
            lock (this)
            {
                if (this.EstPleine())
                {
                    throw new Exception("La file est pleine !");
                }
                else
                {
                    this._File[this._PointeurDeQueue] = item;
                    this._NbreElements++;
                    // Pointer sur le prochain elément libre,
                    // revenir à zéro si on est au bout de la file
                    this._PointeurDeQueue = this._PointeurDeQueue + 1;
                    if (this._PointeurDeQueue >= this._File.Length)
                    {
                        this._PointeurDeQueue = 0;
                    }
                }
            }
        }

        public virtual object Defiler()
        {
            lock (this)
            {
                object item = null;

                if (this.EstVide())
                {
                    throw new Exception("La file est vide !");
                }
                else
                {
                    item = this._File[this._PointeurDeTete];
                    this._NbreElements--;

                    // Faire pointer le pointeur de queue sur le prochain élément valide,
                    // revenir à zéro si on est au bout de la file
                    this._PointeurDeTete = this._PointeurDeTete + 1;
                    if (this._PointeurDeTete >= this._File.Length)
                    {
                        this._PointeurDeTete = 0;
                    }
                }

                return item;
            }
        }

        public virtual bool EstVide()
        {
            return (this._NbreElements == 0);
        }

        public virtual bool EstPleine()
        {
            return (this._NbreElements == this._Taille);
        }

        public int NbreElements
        {
            get { return this._NbreElements; }
        }
        #endregion
    }
}
</syntaxhighlight>
{{Boîte déroulante/fin}}

== Notes et références ==
{{References|groupe=alpha}}
{{Références}}

== Voir aussi ==
=== Bibliographie ===
* {{Ouvrage |langue=en |prénom1=Donald E. |nom1=Knuth |lien auteur1=Donald E. Knuth |titre=[[The Art of Computer Programming]] |volume=I, Fundamental Algorithms |éditeur=3 |année=1997 |pages totales=704 |isbn=}}

=== Articles connexes ===
{{Colonnes|taille=21|
* [[Anomalie de Belady]]
* [[File d'attente de message]]
* [[File d'attente à double extrémité]]
* [[File de priorité]]
* [[File d'attente]] (''queue'')
* [[Théorie des files d'attente]]
* [[Pile (informatique)]] : [[FIFO]], [[LIFO]]
* [[Spooling]]
* [[Type abstrait]]
* [[Terminologie informatique]]
* [[Liste chaînée]]
}}

=== Liens externes ===
* {{chapitre|prénom=Bruno|nom=Bachelet|lire en ligne=http://www.nawouak.net/?doc=course.data_structures+ch=queues+lang=fr|titre=File d'attente|site=nawouak.net|titre ouvrage=Structures de données|année=2011}}

{{Palette|Structure de données|Programmation informatique}}

{{Portail|programmation informatique}}

[[Catégorie:Structure de données]]