Une Queue (File d'attente) est une structure de données qui suit le principe FIFO (First In First Out - premier entré, premier sorti). Inversement aux Stacks (Piles), on contraint ici une structure de données dans laquelle l'élément inséré en premier doit être le premier élément à sortir.

Cela signifie également que le dernier élément mis dans la queue finira toujours par être le dernier élément sorti.

Nous pouvons facilement la visualiser en imaginant une file d'attente dans un magasin. Tout comme les piles (stacks), les queues sont utilisées absolument partout dans le monde de la programmation. En voici quelques exemples:

Elle peut simuler parfaitement une file d'attente.

Ici un algorithme de parcours en largeur (ou BFS, pour Breadth-First Search) permerttant de parcourir un arbre (tree) tel que ci-dessus.
Note : A, B, H, C, D, G, I, J, E, F, K, Z.

Ici un algorithme de parcours en largeur (ou BFS, pour Breadth-First Search) générant un Spanning Tree.

Un spanning tree est un sous-graphe acyclique d'un graphe connecté et non dirigé, qui relie tous les sommets.

Une file d’attente agit comme une mémoire tampon (buffer) entre une tâche et le service qu’elle appelle. Afin d’atténuer les surcharges intermittentes pouvant entraîner l’échec du service une queue réduit l’impact des pics de demandes (tel un condensateur en électronique).

Faire fonctionner une queue.
Créer nos propres structures de queue.
Mettre en pratique les structures de tableaux et de listes chaînées.
Comprendre les avantages / inconvénients de chaque implémentation.

Et ensuite ?

Si nous n’avons pas encore vu les piles (stacks), c’est l’occasion : elles sont implémentées selon le principe LIFO (Last-In-First-Out) inversement aux queues vues ici. Nous pouvons aussi continuer avec des structures de données plus avancées telles que : les arbres binaires (binary trees) ou les tables de hachage (hash tables).

Nous avons opté pour le C++ pour l'illustration du code, mais pas d'inquiétude, les autres langues utilisent la même logique et le plus souvent une syntaxe similaire.

Une queue est utilisée pour les deux opérations principales suivantes :

  void enqueue(const T& data);  // Ajoute un nouvel élément à la fin de la queue (dernier)
  void dequeue();               // Enlève l'élément au début (premier) de la queue

Pour utiliser correctement une queue, les fonctionnalités suivantes sont ajoutées :

  bool empty() const;        // Teste si la queue est vide.
  const T& seek() const;     // Montre l’élément au devant (premier) de la queue.
 

Exemple

  queue< string > clients; // Initialise la queue
  clients.enqueue("john"); // ["john"]
  clients.enqueue("do");   // ["john", "do"]
  clients.seek();          // --> "john"
  clients.dequeue();       // ["do"]
  clients.push("jack");    // ["do", "jack"]
  clients.push("dany");    // ["do", "jack", "dany"]

  // Get clients from the first to be handled
  while (!clients.empty()) {
    auto currentClient = clients.seek();
    clients.dequeue();
  }
 

Comment construire notre propre structure de queue? C’est assez simple, nous verrons plusieurs implémentations afin d’en comprendre les fonctionnements et pouvoir choisir la plus optimale.

Remarque: La queue est une structure de données abstraite (tout comme la pile). La définition de leur structure est basée sur leur comportement et non sur leur implémentation. Cela contraste avec les structures de données plus fondamentales, telles que les tableaux et les listes chaînées, qui ont des exigences strictes pour le stockage de leurs données.

En Liste chaînée (Linked List)

Nous utiliserons une liste chaînée avec un pointeur supplémentaire sur l'arrière de la queue. Reprenons le squelette de notre structure vue dans le cours 'liste chaînée'.

  template < typename T >
  class Queue
  {
  public:
    Queue() : head(nullptr), tail(nullptr) {}  // Construct as an empty queue
    ~Queue() { ... }                           // Destructor (same as linked list)

  private:
    // Node structure declaration
    struct Node
    {
        // Constructor
        Node(const T& data) : data(data), next(nullptr) {}
        T data;     // Value
        Node* next; // Pointer to the next node
    };

    Node* head; // Pointer on the first element (also the beginning of the queue)
    Node* tail; // Pointer on the last element (also the end of the queue)
  }

Lorsque nous souhaitons ajouter quelque chose à la queue (Enqueue), il nous suffit de l'ajouter en fin de liste.

Nous mémorisons le dernier élément de la liste afin de faire des insertions efficace.

  void Enqueue(const T& data)
  {
    Node* newNode = new Node(data); // Allocate memory

    if (!head)      // First element is the head as well as the tail
    {
      head = newNode;   // Set head to the new node
      tail = head;      // Tail is also the head in this case
    }
    else            // Otherwise element is added at the end
    {
      tail->next = newNode;
      tail = tail->next;  // Update the new tail
    }
  }
  

Pour la fonction Dequeue, rien de plus simple : supprimons le premier élément de la liste (comme avec les stacks).

  void Dequeue()
  {
    if (!head)  // Empty queue error
      return;

    auto tmp = head;      // Get the current top
    head = head->next;    // Set the head to point to the next node
    delete tmp;           // Delete the node
  }
  

Les fonctions Empty et Seek sont elles aussi triviales.

  bool Empty() const { return (head) ? false : true; }

  const T& Top() const
  {
    if (!head); // Throw Exception
    return *head;
  }

  

L'implémentation ci-dessus nous donne les idées impliquées, et toute optimisation dont nous pourrions avoir besoin peut être accomplie en modifiant directement une structure de liste chaînée.

En Tableau (array)

Utiliser une implémentation de tableau pour une queue n'est pas l'approche la plus simple, mais reste intéressant. Cela implique l'utilisation d'un tableau circulaire souvent nommé buffer circulaire (circular buffer en anglais). Cela est aussi souvent utilisé pour créer des caches mémoire.

  template < typename T >
  class Queue
  {
  public:
    // Allocate/Deallocate stack memory
    Queue(const int size) : back(0), front(0), count(0), max_size(size)
    {  stack = new T[max_size]; }
    ~Queue() { delete[] stack; }

  private:
    int back;           // back index of the queue
    int front;          // front index of the queue
    int count;          // Keep the count to check if full
    const int max_size; // max size
    T* Queue;           // pointer on the array

    Queue(); // Forbid default constructor
  }

Lorsque nous souhaitons ajouter un élément à la pile (Equeue) il nous suffit de le mettre à l'arrière de la queue et incrémenter les comptes.

  void Enqueue(const T new_data) {
    if (count == max_size) // Stack overflow exception

    queue[back++] = new_data; // Set data and then update back index
    if (back == max_size)     // Circular iteration if end reached
      back = 0;
    ++count;                  // Update count
  }
  

Pour la fonction Dequeue :

  void Dequeue()
  {
    if (count == 0) // Empty queue error
      return;

    if (++front == max_size)     // Circular iteration if end reached
      front = 0;
    --count;  // Change the count
  }
  

Les fonctions Empty et Seek sont triviales.

  bool Empty() const { return count == 0; }
  const T& Seek() const { return queue[front]; }
  

En bref

Liste chaînée (Linked List)
Opérations d'insertion et de suppression en O(1).
Peut grandir de manière dynamique.
Allocation/Deallocation mémoire nécessaire pour les opérations d'insertion et de suppression.
Utilise très légèrement plus de mémoire en raison du stockage supplémentaire de pointeurs.

Tableau Circulaire (Circular Array)
Opérations d'insertion et de suppression en O(1).
Ne peut grandir de manière dynamique : il nécessite une taille maximale à l'initialisation.
Un tableau surdimensionné entraîne quantité de mémoire gaspillée.
Utilise la notion de tableau circulaire (e.g. buffers, caches, ...).

• The Algorithm Design Manual Book par Steven S Skiena
• Wikipedia