File (structure de données)

Pour les articles homonymes, voir File.

 Pour les articles homophones, voir Fil et Phil.

En informatique, une file (« queue » en anglais ) est une structure de données basée sur le principe du Premier entré, premier sorti, en anglais FIFO (First In, First Out), ce qui veut dire que les premiers éléments ajoutés à la file seront les premiers à être récupérés. Le fonctionnement ressemble à une file d'attente : les premières personnes à arriver sont les premières personnes à sortir de la file.

Applications

Cette structure est utilisée par exemple :

• En général, pour mémoriser temporairement des transactions qui doivent attendre pour être traitées.
• Les serveurs d'impression, qui doivent traiter les requêtes dans l'ordre dans lequel elles arrivent, et les insèrent dans une file d'attente (ou une queue).
• Certains moteurs multitâches, dans un système d'exploitation, qui doivent accorder du 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émoires tampons (en anglais buffers).

Primitives

Voici les 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.

• « Enfiler » : ajoute un élément dans la file. Terme anglais correspondant : « Enqueue ».
• « Défiler » : renvoie le prochain élément de la file, et le retire de la file. Terme anglais correspondant : « 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#

Exemple en C#

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
    }
}

 

Voir aussi

• File à priorités
• Pile
• Structure de données