Guide de l'interface de file d'attente Java

1. Introduction

Dans ce didacticiel, nous discuterons de l' interface de file d' attente de Java .

Tout d'abord, nous allons jeter un coup d'œil à ce que fait une file d'attente et à certaines de ses méthodes de base . Ensuite, nous allons plonger dans un certain nombre d' implémentations que Java fournit en standard.

Enfin, nous parlerons de la sécurité des threads avant de tout résumer.

2. Visualisation de la file d'attente

Commençons par une analogie rapide.

Imaginez que nous venons d'ouvrir notre première entreprise - un stand de hot-dogs. Nous voulons servir nos nouveaux clients potentiels de la manière la plus efficace possible pour notre petite entreprise; un à la fois. Tout d'abord, nous leur demandons de former une ligne ordonnée devant notre stand, avec de nouveaux clients se joignant à l'arrière. Grâce à nos capacités d'organisation, nous pouvons désormais distribuer nos savoureux hot dogs de manière équitable.

Les files d'attente en Java fonctionnent de la même manière. Après avoir déclaré notre file d'attente, nous pouvons ajouter de nouveaux éléments à l'arrière et les supprimer de l'avant.

En fait, la plupart des files d'attente que nous rencontrerons en Java fonctionnent de cette manière premier entré , premier sorti - souvent abrégé en FIFO.

Cependant, il y a une exception que nous aborderons plus tard.

3. Méthodes de base

La file d'attente déclare un certain nombre de méthodes qui doivent être codées par toutes les classes d'implémentation. Décrivons maintenant quelques-uns des plus importants :

  1. offer () - Insère un nouvel élément dans la file d'attente
  2. poll () - Supprime un élément de l'avant de la file d'attente
  3. peek () - Inspecte l'élément à l'avant de la file d'attente, sans le supprimer

4. AbstractQueue

AbstractQueue est l' implémentation de file d'attente la plus simple possible fournie par Java. Il comprend une implémentation squelettique de certaines méthodes de l' interface de file d'attente , à l'exclusion de l' offre .

Lorsque nous créons une file d'attente personnalisée étendant la classe AbstractQueue , nous devons fournir une implémentation de la méthode d' offre qui ne permet pas l'insertion d'éléments nuls.

De plus, nous devons fournir les méthodes PEEK, sondage, la taille, et java.util est iterator .

Mettons ensemble une implémentation de file d'attente simple à l' aide de AbstractQueue.

Tout d'abord, définissons notre classe avec une LinkedList pour stocker les éléments de notre file d'attente :

public class CustomBaeldungQueue extends AbstractQueue { private LinkedList elements; public CustomBaeldungQueue() { this.elements = new LinkedList(); } }

Ensuite, remplaçons les méthodes requises et fournissons le code:

@Override public Iterator iterator() { return elements.iterator(); } @Override public int size() { return elements.size(); } @Override public boolean offer(T t) { if(t == null) return false; elements.add(t); return true; } @Override public T poll() { Iterator iter = elements.iterator(); T t = iter.next(); if(t != null){ iter.remove(); return t; } return null; } @Override public T peek() { return elements.getFirst(); }

Excellent, vérifions que cela fonctionne avec un test unitaire rapide:

customQueue.add(7); customQueue.add(5); int first = customQueue.poll(); int second = customQueue.poll(); assertEquals(7, first); assertEquals(5, second);

4. Sous-interfaces

Généralement, l' interface Queue est héritée par 3 sous-interfaces principales. Blocage des files d'attente, des files d'attente de transfert et des Deques .

Ensemble, ces 3 interfaces sont implémentées par la grande majorité des files d'attente disponibles de Java . Jetons un coup d'œil à ce que ces interfaces ont été conçues pour faire.

4.1. Blocage des files d'attente

L' interface BlockingQueue prend en charge des opérations supplémentaires qui forcent les threads à attendre sur la file d'attente en fonction de l'état actuel. Un thread peut attendre sur la file d' attente d'être non vide lors d'une tentative d'extraction, ou pour qu'il devienne vide lors de l'ajout d' un nouvel élément.

Les files d'attente de blocage standard incluent LinkedBlockingQueue, SynchronousQueue et ArrayBlockingQueue .

Pour plus d'informations, consultez notre article sur le blocage des files d'attente .

4.2. Files d'attente de transfert

L' interface TransferQueue étend l' interface BlockingQueue mais est adaptée au modèle producteur-consommateur. Il contrôle le flux d'informations du producteur au consommateur, créant une contre-pression dans le système.

Java est livré avec une implémentation de l' interface TransferQueue , LinkedTransferQueue.

4.3. Deques

Deque est l'abréviation de D ouble- E nded Que ue et est analogue à un jeu de cartes - les éléments peuvent être pris au début et à la fin du Deque . Tout comme la file d'attente traditionnelle , le Deque fournit des méthodes pour ajouter, récupérer et consulter les éléments conservés en haut et en bas .

Pour un guide détaillé sur le fonctionnement du Deque , consultez notre article ArrayDeque .

5. Files d'attente prioritaires

Nous avons vu plus tôt que la plupart des files d'attente que nous rencontrons en Java suivent le principe FIFO.

One such exception to this rule is the PriorityQueue. When new elements are inserted into the PriorityQueue, they are ordered based on their natural ordering, or by a defined Comparator provided when we construct the PriorityQueue.

Let's take a look at how this works with a simple unit test:

PriorityQueue integerQueue = new PriorityQueue(); integerQueue.add(9); integerQueue.add(2); integerQueue.add(4); int first = integerQueue.poll(); int second = integerQueue.poll(); int third = integerQueue.poll(); assertEquals(2, first); assertEquals(4, second); assertEquals(9, third);

Despite the order in which our integers were added to the PriorityQueue, we can see that the retrieval order is changed according to the natural order of the numbers.

We can see that the same is also true when applied to Strings:

PriorityQueue stringQueue = new PriorityQueue(); stringQueue.add("blueberry"); stringQueue.add("apple"); stringQueue.add("cherry"); String first = stringQueue.poll(); String second = stringQueue.poll(); String third = stringQueue.poll(); assertEquals("apple", first); assertEquals("blueberry", second); assertEquals("cherry", third);

6. Thread Safety

Adding items to Queues is particularly useful in multi-threaded environments. A Queue can be shared amongst threads, and be used to block progress until space is available – helping us overcome some common multi-threaded problems.

For example, writing to a single disk from multiple threads creates resource contention and can lead to slow writing times. Creating a single writer thread with a BlockingQueue can alleviate this issue and lead to vastly improved write speeds.

Luckily, Java offers ConcurrentLinkedQueue, ArrayBlockingQueue, and ConcurrentLinkedDeque which are thread-safe and perfect for multi-threaded programs.

7. Conclusion

Dans ce didacticiel, nous avons plongé en profondeur dans l' interface Java Queue .

Tout d' abord, nous avons exploré ce qu'est une file d' attente fait , ainsi que les implémentations Java fournit.

Ensuite, nous avons examiné le principe FIFO habituel d' une file d'attente , ainsi que la PriorityQueue qui diffère dans son ordre.

Enfin, nous avons exploré la sécurité des threads et comment les files d'attente peuvent être utilisées dans un environnement multi-thread.

Comme toujours, le code est disponible sur sur GitHub.