Java Queue Interface et ses implémentations

Ici, nous allons discuter de l'interface Java Queue. Vous découvrirez ce qu'est la structure de données de file d'attente , comment elle est représentée en Java, quelles méthodes sont les plus importantes pour toutes les files d'attente. En outre, quelles implémentations de Queue sont en langage Java. Après cela, nous examinons de plus près les implémentations les plus importantes et les apprenons avec des exemples.

Structure des données de la file d'attente

Une file d'attente est une structure de données abstraite linéaire avec l'ordre particulier d'exécution des opérations - First In First Out (FIFO). Cela signifie que vous pouvez ajouter un élément (ou enqueue, mettre dans la file d'attente) uniquement à la fin de la structure, et prendre un élément (dequeue ou supprimer de la file d'attente) uniquement à partir de son début. Vous pouvez imaginer très facilement la structure des données de la file d'attente. Cela ressemble à une file d'attente ou à une file de clients dans la vraie vie. Le client arrivé en premier sera également servi en premier. Si vous avez quatre personnes en ligne au McDonalds ou ailleurs, le premier à faire la queue sera le premier à entrer dans le magasin. Si le nouveau client vient, il sera le 5ème en ligne pour obtenir des hamburgers. Ainsi, lorsque vous travaillez avec une file d'attente, de nouveaux éléments sont ajoutés à la fin, et si vous souhaitez obtenir un élément, il sera repris depuis le début. C'est le principe de base du travail classique de structure de données de file d'attente.

File d'attente en Java

La file d'attente en Java est une interface. Selon la documentation d'Oracle, l'interface Queue possède 2 superinterfaces, 4 interfaces différentes qui héritent de la file d'attente et une liste de classes extrêmement impressionnante.Qu'est-ce que ça veut dire? Tout d'abord, Java Queue fait partie de Collection Framework et implémente l'interface Collection. Ainsi, il prend en charge toutes les méthodes de l'interface Collection telles que l'insertion, la suppression, etc. Queue implémente l'interface Iterable, qui permet à un objet d'être la cible de l'instruction "for-each loop".

Méthodes de file d'attente Java

La file d'attente déclare un certain nombre de méthodes. En tant que méthodes d'interface, elles doivent être représentées dans toutes les classes qui implémentent Queue. Les méthodes de file d'attente les plus importantes, Java :

• Offre booléenne() - insère un nouvel élément dans la file d'attente si c'est possible
• Add(E e) booléen – insère un nouvel élément dans la file d'attente si c'est possible. Renvoie true en cas de succès et lève une IllegalStateException s'il n'y a pas d'espace.
• Object poll() – récupère et supprime un élément de la tête du. Renvoie null si la file d'attente est vide.
• Object remove() - récupère et supprime un élément de la tête de la file d'attente.
• Object peek() - récupère, mais ne supprime pas un élément de la tête de la file d'attente. Renvoie null si la file d'attente est vide.
• Object element() - récupère, mais ne supprime pas un élément de la tête de la file d'attente.

Sous-interfaces de Java Queue

L'interface de file d'attente est héritée par 4 sous-interfaces - BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Vous pouvez les diviser en 3 groupes : Deques, Blocking Queues et Transfer Queues avec BlockingDeque appartenant aux deux premiers. Jetons un coup d'œil à ces groupes.

Deques

Deque signifie D ouble- Ended Q ueue et prend en charge l'ajout ou la suppression de l'une ou l'autre queue des données sous forme de file d'attente (premier entré, premier sorti/FIFO) ou de la tête sous la forme d'une autre structure de données populaire appelée pile (dernier entré ) . premier sorti/LIFO). Classes qui implémentent l'interface Deque : ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Blocage des files d'attente

Une file d'attente bloquante est une file d'attente qui bloque un thread dans deux cas :

• le thread essaie d'obtenir des éléments d'une file d'attente vide
• le thread essaie de mettre des éléments dans la file d'attente complète

Lorsqu'un thread essaie d'obtenir des éléments d'une file d'attente vide, il attend qu'un autre thread place les éléments dans la file d'attente. De même, lorsqu'un thread essaie de placer des éléments dans une file d'attente complète, il attend qu'un autre thread retire les éléments de la file d'attente pour obtenir de l'espace libre pour les éléments. Bien sûr, le concept de "file d'attente complète" implique que la file d'attente a une taille limitée, qui est généralement spécifiée dans le constructeur. Les files d'attente de blocage standard incluent LinkedBlockingQueue, SynchronousQueue et ArrayBlockingQueue. Implémentation des classes de l'interface BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDeque est une sous-interface pour BlockingQueue. BlockingDeque tel que BlockingQueue est une file d'attente bloquante, mais bidirectionnelle. Il hérite donc des propriétés de l'interface Deque. Il est orienté vers une exécution multithread, n'autorise pas les éléments zéro et la capacité peut être limitée. Les implémentations de l'interface BlockingDeque bloquent l'opération consistant à obtenir des éléments si la file d'attente est vide et à ajouter un élément dans la file d'attente si elle est pleine.

Files d'attente de transfert

L'interface TransferQueue étend l'interface BlockingQueue. Cependant, contrairement à l'implémentation des files d'attente d'interface BlockingQueue, où les threads peuvent être bloqués si la file d'attente est vide (lecture) ou si la file d'attente est pleine (écriture), les files d'attente d'interface TransferQueue bloquent le flux d'écriture jusqu'à ce qu'un autre flux récupère l'élément. Utilisez une méthode de transfert pour cela. En d'autres termes, l'implémentation de BlockingQueue garantit que l'élément créé par le Producer doit être dans la file d'attente, tandis que l'implémentation de TransferQueue garantit que l'élément Producer est "reçu" par le Consumer. Il n'y a qu'une seule implémentation Java officielle de l'interface TransferQueue - LinkedTransferQueue.

Implémentations de la file d'attente Java

Il existe de nombreuses classes qui implémentent l'interface Queue :

• AbstractQueue selon la documentation Queue Java 8, cette classe abstraite fournit des implémentations de base de certaines opérations Queue. Il n'autorise pas les éléments nuls. Il existe 3 autres méthodes d'ajout, de suppression et d'élément basées sur l'offre classique de la file d'attente , le sondage et le coup d'œil , respectivement. Cependant, ils lèvent des exceptions au lieu d'indiquer un échec via des retours faux ou nuls.
• ArrayBlockingQueue - une file d'attente de blocage FIFO de taille fixe soutenue par un tableau
• ArrayDeque - implémentation de tableau redimensionnable de l'interface Deque
• ConcurrentLinkedDeque — un deque simultané illimité basé sur des nœuds liés.
• ConcurrentLinkedQueue - une file d'attente thread-safe illimitée basée sur des nœuds liés.
• DelayQueue - une file d'attente de planification basée sur le temps soutenue par un tas
• LinkedBlockingDeque - l'implémentation simultanée de l'interface Deque.
• LinkedBlockingQueue - une file d'attente de blocage FIFO facultativement limitée soutenue par des nœuds liés
• LinkedList - implémentation de liste à double liaison des interfaces List et Deque. Implémente toutes les opérations de liste facultatives et autorise tous les éléments (y compris null)
• LinkedTransferQueue — une TransferQueue illimitée basée sur des nœuds liés
• PriorityBlockingQueue - une file d'attente de priorité de blocage illimitée soutenue par un tas
• PriorityQueue - une file d'attente prioritaire basée sur la structure de données du tas
• SynchronousQueue - une file d'attente de blocage où chaque opération d'insertion doit attendre une opération de suppression correspondante par un autre thread, et vice versa.

Les implémentations les plus populaires sont LinkedList, ArrayBlockingQueue et PriorityQueue. Regardons-les et faisons quelques exemples pour une meilleure compréhension.

Liste liée

La classe LinkedList en Java implémente les interfaces List et Deque. Il s'agit donc d'une combinaison de List et Deque, une file d'attente bidirectionnelle, qui prend en charge l'ajout et la suppression d'éléments des deux côtés. En Java, LinkedList est une liste à double lien : chaque élément de List appelle Node et contient un objet et des références à deux objets voisins - le précédent et le suivant. Vous pouvez dire que LinkedList n'est pas très efficace en termes d'utilisation de la mémoire. C'est vrai, mais cette structure de données peut être utile en cas de performance des opérations d'insertion et de suppression. Cependant, cela ne se produit que si vous utilisez des itérateurs pour eux (dans ce cas, cela se produit en temps constant). Les opérations d'accès par index sont effectuées en recherchant du début à la fin (celui qui est le plus proche) jusqu'à l'élément souhaité. Cependant, n'oubliez pas les coûts supplémentaires liés au stockage des références entre les éléments. Ainsi, LinkedList est l'implémentation de file d'attente la plus populaire en Java. C'est aussi une implémentation de List et Deque et cela nous permet de créer une file d'attente bidirectionnelle composée de tous les objets, y compris null. LinkedList est une collection d'éléments.

Constructeurs de listes liées

LinkedList() sans paramètres est utilisé pour construire une liste vide. LinkedList(Collection<? extend E> c) sert à créer une liste contenant les éléments de la collection spécifiée, dans l'ordre, ils sont renvoyés par l'itérateur de la collection.

Principales méthodes LinkedList:

• add(E element) Ajoute l'élément spécifié à la fin de cette liste ;
• add(int index, E element) Insère l'élément à l'index de position spécifié ;
• get(int index) Renvoie l'élément à la position spécifiée dans cette liste ;
• remove(int index) Supprime l'élément qui se trouve à la position index ;
• remove(Object o) Supprime la première occurrence de l'élément ?o de cette liste si elle s'y trouve.
• remove() Récupère et supprime le premier élément de la liste.
• addFirst(), addLast() ajoutent un élément au début/à la fin d'une liste
• clear() supprime tous les éléments de la liste
• contains(Object o) renvoie true si la liste contient l'élément o.
• indexOf(Object o) renvoie l'index de la première occurrence de l'élément o, ou -1 s'il n'est pas dans la liste.
• set(int index, E element) remplace l'élément à la position d'index par l'élément
• size() Renvoie la quantité d'éléments dans la liste.
• toArray() renvoie un tableau contenant tous les éléments de la liste du premier au dernier élément.
• pop() qui extrait un élément de la pile (représenté par la liste)
• push(E e) qui pousse un élément sur la pile (représenté par cette liste)

Exemple de file d'attente Java - LinkedList (mettre et supprimer des éléments de différentes manières)

import java.util.*;

public class LinkedListTest {

       public static void main(String args[]){

           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

File d'attente de priorité

PriorityQueue n'est pas exactement la file d'attente au sens général FIFO. Les éléments de la file d'attente prioritaire sont classés selon leur ordre naturel, ou par un comparateur fourni au moment de la construction de la file d'attente, selon le constructeur utilisé. Cependant, ce n'est pas un ordre comme il pourrait l'être dans une structure linéaire telle qu'une liste (du plus grand au plus petit ou vice versa). Une file d'attente prioritaire basée sur un tas min de priorité. Heap est une structure de données basée sur un arbre binaire. La priorité de chaque parent est plus grande que les priorités de ses enfants. Un arbre est dit binaire complet si chaque parent n'a pas plus de deux enfants, et le remplissage des niveaux va de haut en bas (du même niveau — de gauche à droite). Le tas binaire se réorganise chaque fois qu'un nouvel élément y est ajouté ou supprimé. En cas de min-heap, le plus petit élément va à la racine quel que soit l'ordre de son insertion. File d'attente prioritaire basée sur ce tas min, donc si nous avons une PriorityQueue d'entiers, son premier élément sera le plus petit de ces nombres. Si vous supprimez la racine, la plus petite suivante devient une racine.

Principales méthodes PriorityQueue :

• boolean add(object) insère l'élément spécifié dans la file d'attente prioritaire. Renvoie true en cas de succès. Si la file d'attente est pleine, la méthode lève une exception.
• booléen offre(objet) insère l'élément spécifié dans cette file d'attente prioritaire. Si la file d'attente est pleine, la méthode renvoie false.
• boolean remove(object) supprime une seule instance de l'élément spécifié de cette file d'attente, si elle est présente.
• L'objet poll() récupère et supprime la tête de cette file d'attente. Renvoie null si la file d'attente est vide.
• void clear() supprime tous les éléments de la file d'attente prioritaire.
• L'objet element() récupère la tête de cette file d'attente sans la supprimer. Lève NoSuchElementException si la file d'attente est vide.
• Object peek() récupère la tête de la file d'attente sans la supprimer. Renvoie null si la file d'attente est vide.
• boolean contains(Object o) renvoie vrai si la file d'attente contient l'élément o.
• int size() renvoie le nombre d'éléments dans cette file d'attente.

Exemple de file d'attente prioritaire

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
   public static void main(String[] args) {

       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();

       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }

       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval):
1
2
3
4
5

Il est important de comprendre que les files d'attente prioritaires sont basées sur des tas binaires, elles ne conservent donc pas les éléments dans un ordre de tri linéaire. Chaque chemin de la racine à la feuille est ordonné, mais les différents chemins de la racine ne le sont pas. Cela signifie que vous pouvez obtenir très rapidement l'élément minimal de la file d'attente. Si vous supprimez l'en-tête à chaque fois, vous imprimerez une structure triée.

ArrayBlockingQueueArrayBlockingQueue

Structure de données interne de ArrayBlockingQueueest basé sur un tableau circulaire pour stocker des éléments. Il s'agit d'une file d'attente typique (FIFO) dans le cas où de nouveaux éléments sont insérés à la fin de la file d'attente et que les opérations d'extraction renvoient un élément de la tête de la file d'attente. Une fois créée, la capacité de la file d'attente ne peut pas être modifiée. Les tentatives d'insertion (placement) d'un élément dans une file d'attente pleine entraînent le blocage du flux ; essayer de prendre un élément d'une file d'attente vide bloque également le thread. Comme nous l'avons dit précédemment, ce tableau est circulaire. Cela signifie que le premier et le dernier élément du tableau sont traités logiquement adjacents. La file d'attente avance les index des éléments de tête et de queue chaque fois que vous placez l'élément dans la file d'attente ou que vous le supprimez de la file d'attente. Si un index avance le dernier élément du tableau, il redémarre à partir de 0. Par conséquent, la file d'attente n'a pas à décaler tous les éléments en cas de suppression de la tête (comme dans un tableau habituel). Cependant, en cas de suppression d'un élément du milieu (à l'aide de Iterator.remove), les éléments sont décalés. ArrayBlockingQueue prend en charge une politique d'équité supplémentaire avec un paramètre équitable dans le constructeur pour ordonner le travail des flux d'attente des producteurs (insertion d'éléments) et des consommateurs (extraction d'éléments). Par défaut, la commande n'est pas garantie. Cependant, si la file d'attente est créée avec "fair == true", l'implémentation de la classe ArrayBlockingQueue fournit un accès aux threads dans l'ordre FIFO. L'équité réduit généralement la bande passante, mais réduit également la volatilité et évite de manquer de ressources.

Constructeurs de classe ArrayBlockingQueue

• ArrayBlockingQueue (int capacity) crée une file d'attente de capacité fixe et avec une politique d'accès par défaut.
• ArrayBlockingQueue (int capacity, boolean fair) crée une file d'attente avec une capacité fixe et une politique d'accès spécifiée.
• ArrayBlockingQueue (int capacity, boolean fair, Collection <? extend E> c) crée une file d'attente avec une capacité fixe spécifiée par la politique d'accès et inclut des éléments dans la file d'attente.

Ici, nous avons l'exemple BlockingQueueExample. Nous créons une file d'attente de la ArrayBlockingQueue avec une capacité d'un élément et un indicateur équitable. Deux threads sont lancés. Le premier d'entre eux, le thread Producer, met en file d'attente les messages du tableau de messages à l'aide de la méthode put. Le second, Consumer, thread lit les éléments de la file d'attente à l'aide de la méthode take et les affiche dans la console. L'ordre des éléments est celui naturel pour la file d'attente.

import java.util.concurrent.*;

public class ArrayBlockingQueueExample {

   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};

       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }

       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

La sortie est la file d'attente dans l'ordre naturel ; les deux premiers éléments apparaissent avec un retard. Pour renforcer ce que vous avez appris, nous vous suggérons de regarder une leçon vidéo de notre cours Java

Conclusion

• La file d'attente est utilisée pour insérer des éléments à la fin de la file d'attente et supprime depuis le début de la file d'attente. Il suit le concept FIFO.
• Java Queue fait partie de Collection Framework et implémente l'interface Collection. Ainsi, il prend en charge toutes les méthodes de l'interface Collection telles que l'insertion, la suppression, etc.
• Les implémentations les plus fréquemment utilisées de Queue sont LinkedList, ArrayBlockingQueue et PriorityQueue.
• Les éléments de la file d'attente prioritaire sont classés selon leur ordre naturel, ou par un comparateur fourni au moment de la construction de la file d'attente, selon le constructeur utilisé.
• Si une opération nulle est effectuée sur BlockingQueues, NullPointerException est levée.