Files

Une file, en anglais Queue, est une structure de données FIFO, pour First In, First Out, au sens où les éléments en seront retirés dans le même ordre que celui de leur insertion. En cela, elle peut représenter une file d'attente ou un canal de communication simple. Il existe plusieurs variantes, comme par exemple les files prioritaires, où les éléments insérés dans la file sont extraits dans un ordre influencé par une politique particulière (p. ex. : en ordre de priorité), ou encore les files circulaires, qui opèrent sur un espace maximal fixe.

Opérations clés

Les opérations clés d'une file suivent. Une implémentation peut bien sûr offrir d'autres services, ou utiliser d'autres noms que ceux utilisés ici.

Nom (français)	Nom (anglais)	Sémantique	Complexité typique	Risques d'échec / d'exception	Remarques
`enfiler`	enqueue push_back	Ajouter un élément dans la file	$O(1)$	La file est pleine; s'applique si la pile a une capacité maximale fixée a priori Manque de ressources; s'applique si les noeuds sont alloués dynamiquement
`defiler`	`dequeue` `pop`	Retirer un élément de la file. Retournera l'élément dans certaines implémentations, et sera void dans d'autres implémentations	$O(1)$	La file est vide	Une implémentation générique devra implémenter ce service de telle sorte qu'il soit void, du moins en l'absence d'un moteur de collecte d'ordures, sinon elle ne pourra être Exception-Safe
est_vide	empty	Prédicat qui s'avère seulement si la pile est vide	$O(1)$		Si le langage le supporte, sera typiquement const Si le langage le supporte, sera typiquement noexcept
examiner	back peek	Consulter le prochain élément disponible pour extraction, sans l'extraire	$O(1)$	La file est vide	Si le langage le supporte, sera typiquement const Si le langage le supporte, sera typiquement noexcept Nécessaire pour réaliser une implémentation générique qui soit Exception-Safe, du moins en l'absence d'un moteur de collecte d'ordures. Peut être omise sinon

Technique

Implémentation naïve à base de noeuds (capacité dynamique).

File d'entiers avec C++ File générique avec C++

File d'entiers avec C++	File générique avec C++
#include <iostream> class Empty {}; class file { struct noeud { int valeur; noeud pred; noeud succ; noeud(int valeur) noexcept : valeur{ valeur }, pred{}, succ{} { } }; noeud tete, queue; public: bool empty() const noexcept { return !tete; } file() noexcept : tete{}, queue{} { } // // incopiable mais déplaçable // file(const file&) = delete; file& operator=(const file&) = delete; file(file &&autre) : tete{ autre.tete }, queue{ autre.queue } { autre.tete = {}; autre.queue = {}; } file& operator=(file &&autre) { tete = autre.tete; queue = autre.queue; autre.tete = {}; autre.queue = {}; return *this; } void enqueue(int valeur) { auto p = new noeud{ valeur }; if (queue) queue->succ = p; else tete = p; p->pred = queue; queue = p; } void dequeue() { if (empty()) throw Empty{}; auto p = tete; if (tete == queue) tete = queue = {}; else { tete = tete->succ; tete->pred = {}; } delete p; } int peek() const { if (empty()) throw Empty{}; return tete->valeur; } ~file() { while (!empty()) dequeue(); } }; int main() { using namespace std; enum { N = 10 }; file ze_file; for (int i = 0; i < N; ++i) ze_file.enqueue(i + 1); while (!ze_file.empty()) { cout << ze_file.peek() << endl; ze_file.dequeue(); } }	#include <iostream> #include <string> class Empty {}; template <class T> class file { public: using value_type = T; using reference = T&; using const_reference = const T&; private: struct noeud { value_type valeur; noeud pred; noeud succ; noeud(const_reference valeur) noexcept : valeur{ valeur }, pred{}, succ{} { } }; noeud tete, queue; public: bool empty() const noexcept { return !tete; } file() noexcept : tete{}, queue{} { } // // incopiable mais déplaçable // file(const file&) = delete; file& operator=(const file&) = delete; file(file &&autre) : tete{ autre.tete }, queue{ autre.queue } { autre.tete = {}; autre.queue = {}; } file& operator=(file &&autre) { tete = autre.tete; queue = autre.queue; autre.tete = {}; autre.queue = {}; return *this; } void enqueue(const_reference valeur) { auto p = new noeud{ valeur }; if (queue) queue->succ = p; else tete = p; p->pred = queue; queue = p; } void dequeue() { if (empty()) throw Empty{}; auto p = tete; if (tete == queue) tete = queue = {}; else { tete = tete->succ; tete->pred = {}; } delete p; } reference peek() { if (empty()) throw Empty{}; return tete->valeur; } const_reference peek() const { if (empty()) throw Empty{}; return tete->valeur; } ~file() { while (!empty()) dequeue(); } }; int main() { using namespace std; enum { N = 10 }; file<string> ze_file; for (int i = 0; i < N; ++i) ze_file.enqueue(to_string(i + 1) + "!"); while (!ze_file.empty()) { cout << ze_file.peek() << endl; ze_file.dequeue(); } }
Exécution	Exécution
`1 2 3 4 5 6 7 8 9 10`	`1! 2! 3! 4! 5! 6! 7! 8! 9! 10!`

#include <iostream>
class Empty {};
class file
{
   struct noeud
   {
      int valeur;
      noeud *pred;
      noeud *succ;
      noeud(int valeur) noexcept
         : valeur{ valeur }, pred{}, succ{}
      {
      }
   };
   noeud *tete, *queue;
public:
   bool empty() const noexcept
      { return !tete; }
   file() noexcept
      : tete{}, queue{}
   {
   }
   //
   // incopiable mais déplaçable
   //
   file(const file&) = delete;
   file& operator=(const file&) = delete;
   file(file &&autre)
      : tete{ autre.tete }, queue{ autre.queue }
   {
      autre.tete = {};
      autre.queue = {};
   }
   file& operator=(file &&autre)
   {
      tete = autre.tete;
      queue = autre.queue;
      autre.tete = {};
      autre.queue = {};
      return *this;
   }
   void enqueue(int valeur)
   {
      auto p = new noeud{ valeur };
      if (queue)
         queue->succ = p;
      else
         tete = p;
      p->pred = queue;
      queue = p;
   }
   void dequeue()
   {
      if (empty()) throw Empty{};
      auto p = tete;
      if (tete == queue)
         tete = queue = {};
      else
      {
         tete = tete->succ;
         tete->pred = {};
      }
      delete p;
   }
   int peek() const
   {
      if (empty()) throw Empty{};
      return tete->valeur;
   }
   ~file()
   {
      while (!empty())
         dequeue();
   }
};
int main()
{
   using namespace std;
   enum { N = 10 };
   file ze_file;
   for (int i = 0; i < N; ++i)
      ze_file.enqueue(i + 1);
   while (!ze_file.empty())
   {
      cout << ze_file.peek() << endl;
      ze_file.dequeue();
   }
}

#include <iostream>
#include <string>
class Empty {};
template <class T>
   class file
   {
   public:
      using value_type = T;
      using reference = T&;
      using const_reference = const T&;
   private:
      struct noeud
      {
         value_type valeur;
         noeud *pred;
         noeud *succ;
         noeud(const_reference valeur) noexcept
            : valeur{ valeur }, pred{}, succ{}
         {
         }
      };
      noeud *tete, *queue;
   public:
      bool empty() const noexcept
         { return !tete; }
      file() noexcept
         : tete{}, queue{}
      {
      }
      //
      // incopiable mais déplaçable
      //
      file(const file&) = delete;
      file& operator=(const file&) = delete;
      file(file &&autre)
         : tete{ autre.tete }, queue{ autre.queue }
      {
         autre.tete = {};
         autre.queue = {};
      }
      file& operator=(file &&autre)
      {
         tete = autre.tete;
         queue = autre.queue;
         autre.tete = {};
         autre.queue = {};
         return *this;
      }
      void enqueue(const_reference valeur)
      {
         auto p = new noeud{ valeur };
         if (queue)
            queue->succ = p;
         else
            tete = p;
         p->pred = queue;
         queue = p;
      }
      void dequeue()
      {
         if (empty()) throw Empty{};
         auto p = tete;
         if (tete == queue)
            tete = queue = {};
         else
         {
            tete = tete->succ;
            tete->pred = {};
         }
         delete p;
      }
      reference peek()
      {
         if (empty()) throw Empty{};
         return tete->valeur;
      }
      const_reference peek() const
      {
         if (empty()) throw Empty{};
         return tete->valeur;
      }
      ~file()
      {
         while (!empty())
            dequeue();
      }
   };
int main()
{
   using namespace std;
   enum { N = 10 };
   file<string> ze_file;
   for (int i = 0; i < N; ++i)
      ze_file.enqueue(to_string(i + 1) + "!");
   while (!ze_file.empty())
   {
      cout << ze_file.peek() << endl;
      ze_file.dequeue();
   }
}

Exécution Exécution

1!
2!
3!
4!
5!
6!
7!
8!
9!
10!

Pédagogie :

Concevoir une file sans verrous avec C++

Lectures complémentaires

Le type std::queue<T> de C++ : hhttp://en.cppreference.com/w/cpp/container/queue
La classe java.util.Queue<E> de Java : http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html
La classe System.Collections.Queue de C#, qui n'est pas générique : https://msdn.microsoft.com/en-us/library/system.collections.queue%28v=vs.110%29.aspx
Construire une file à partir de deux piles, un exercice de style en 2011 : http://pozorvlak.livejournal.com/164716.html
Survol du concept : http://www.studytonight.com/data-structures/queue-data-structure
Explication proposée par Lloyd Allison : http://www.allisons.org/ll/AlgDS/Queue/
Texte du Code Project en 2015 par Hatem Mostafa présentant une file circulaire en C++ : http://www.codeproject.com/Articles/224733/Real-time-Feed-Distribution-using-Circular-Shared

Texte de Jeff Preshing en 2012 montrant comment mettre au point une file circulaire de journalisation en mémoire des événements clés d'un programme, pour faciliter le débogage de programmes parallèles et concurrents : http://preshing.com/20120522/lightweight-in-memory-logging/

Versions sans verrous :

Implémentation d'une file synchronisée sans verrous : ../Parallelisme/lock_free_queue.html
Une file synchronisée sans verrous, proposée par Max Khiszinsky en 2015 : http://kukuruku.co/hub/cpp/lock-free-data-structures-yet-another-treatise