La structure des données de la file d'attente

Maintenant, nous commençons vraiment à entrer dans le vif du sujet ! Nous en sommes à notre quatrième structure de données qui, dans ce cas, est la file d'attente. Au moment où nous aurons terminé ici, nous aurons une compréhension assez solide de toutes les structures de style de liste (bien sûr, jusqu'à ce que nous atteignions les tables de hachage). Allons-y !

Qu'est-ce qu'une file d'attente ?

Comme son nom l'indique, les files d'attente sont comme les files d'attente dans un supermarché. Chaque client est servi dans l'ordre dans lequel il est aligné. Pour une file d'attente, cela signifie que les données circulent de la fin de la liste vers le début de la liste où elles sont finalement traitées. En informatique, ces extrémités sont appelées la tête et la queue.

Comme les piles, les files d'attente sont une autre structure de liste de cas particulière. Cependant, dans une file d'attente, les deux extrémités de la liste sont utilisées. Dans cette structure de données, les éléments sont toujours insérés en queue et supprimés en tête. Cette restriction applique le comportement premier entré, premier sorti (FIFO).

Les opérations principales pour une file d'attente sont mettre en file d'attente et retirer de la file d'attente. Comme nous pouvons l'imaginer, ces opérations sont directement corrélées à l'insertion et à la suppression. L'opération de mise en file d'attente place un nouvel élément dans un nœud à la fin de la liste. Cet objet fera lentement son chemin vers l'avant jusqu'à ce qu'il soit retiré de la file d'attente en tête de liste. Ensemble, ces deux fonctionnalités suffisent pour créer une file d'attente.

Propriétés des files d'attente

Tout comme les piles, les files d'attente ne sont que des listes liées à des cas particuliers, bien qu'elles puissent être implémentées à l'aide de tableaux. Nous gardons exactement la même structure qu'une liste chaînée mais nous n'exposons que les nœuds les plus externes :la tête et la queue. Cela nous permet de conserver une propriété très importante :FIFO. Si jamais nous avons besoin de préserver l'ordre des données telles qu'elles arrivent, nous utiliserons une file d'attente.

Cependant, toutes les files d'attente ne sont pas égales. Comme nous le verrons ci-dessous, certaines files d'attente imposent un ordre de tri qui n'est pas lié à l'ordre d'insertion. Dans ces cas, nous aurons ce qu'on appelle une file d'attente prioritaire.

Applications des files d'attente

Les files d'attente sont généralement utilisées lors du traitement des demandes d'une seule ressource partagée comme un processeur ou un périphérique comme une imprimante. Dans ces scénarios, nous veillons à ce que les demandes soient traitées dans l'ordre dans lequel elles sont reçues. Dans le cas du CPU, les instructions doivent parcourir le pipeline dans le même ordre que le code source. Pour les imprimantes, les travaux d'impression doivent être exécutés selon le principe du premier arrivé, premier servi.

Les files d'attente peuvent également être utilisées pour gérer le transfert de données asynchrone. En d'autres termes, les files d'attente constituent d'excellentes structures de données dans les situations de threading. Si un thread doit contacter un autre, nous pouvons définir une file d'attente entre eux qui stocke les messages. Le premier thread peut simplement stocker les messages dans cette file d'attente et espérer que le second thread surveille correctement l'autre extrémité.

Cela dit, il existe des structures de file d'attente plus complexes qui permettent la manipulation du contenu. Par exemple, les files d'attente peuvent être modifiées pour prendre en charge la priorité des objets. Cette priorité détermine où exactement le nouvel objet ira lorsqu'il sera placé dans la file d'attente. Les objets de même priorité sont triés par ordre d'insertion comme une file d'attente normale. Généralement, les files d'attente prioritaires sont utilisées pour des applications telles que la gestion de la bande passante. Cependant, les files d'attente prioritaires sont également utilisées comme noyau de nombreux algorithmes importants tels que Huffman Coding et l'algorithme de Dijkstra.

Syntaxe de la file d'attente Java

Bien que Java prenne en charge les files d'attente dans sa bibliothèque de collections, nous allons continuer et en implémenter une à la main. Nous continuerons à utiliser l'implémentation entière de node jusqu'à ce que nous ayons une meilleure compréhension du typage générique.

Définition de classe

La classe de file d'attente de base prend en charge deux fonctions principales :mise en file d'attente et retrait de la file d'attente. Comme vous pouvez l'imaginer, ces fonctions sont l'équivalent d'insérer et de supprimer. Par conséquent, le code nécessaire pour créer une file d'attente ressemble plus à ceci :

public class Queue {
  private Node head;
  private Node tail;

  public Queue() {
    head = null;
    tail = null;
  }
}

Nous définissons simplement les deux extrémités de la file d'attente comme des nœuds dans une liste chaînée (bien que nous aurions tout aussi bien pu utiliser un tableau).

Insertion

En utilisant la structure de file d'attente ci-dessus, l'insertion nous oblige simplement à implémenter la méthode de mise en file d'attente.

public void enqueue(int element) {
  Node toAdd = new Node(element, null);
  if (tail != null) {
    this.tail = this.tail.setNext(toAdd);
  } else {
    this.tail = toAdd;
    this.head = toAdd;
  }
}

Ici, nous vérifions simplement si la file d'attente est vide. Si c'est le cas, nous définissons à la fois la tête et la queue du nouveau nœud. Sinon, nous définissons le nouveau nœud comme la fin de la liste.

Suppression

La suppression nécessite simplement que nous implémentions la fonctionnalité de retrait de la file d'attente. Ici, nous devons nous assurer que la fonction renvoie notre entier.

public int dequeue() {
  Node toRemove = this.head;
  if (this.head == null) {
    throw new NoSuchElementException();
  } else if (this.head.getNext() == null) {
    this.head = null;
    this.tail = null;
  } else {
    this.head = this.head.getNext();
  }
  return toRemove.getPayload();
}

Pour la suppression, nous nous retrouvons avec trois cas :une liste vide, une liste à un seul élément et une liste à plusieurs éléments.

Résumé

Dans l'ensemble, les files d'attente sont comme les piles et les listes liées, donc naturellement leurs performances sont en grande partie les mêmes.

Algorithme	Durée d'exécution
Accès	O(N)
Insérer	O(1)
Supprimer	O(1)
Rechercher	O(N)