Les files d'attente prioritaires en Java expliquées avec des exemples

Les files d'attente prioritaires sont très souvent utilisées dans des applications réelles. Dans cet article, nous allons découvrir ce que sont les files d'attente prioritaires et comment les utiliser en Java.

Avant de discuter de ce qu'est une file d'attente prioritaire, voyons ce qu'est une file d'attente normale.

Une file d'attente régulière suit une structure premier entré, premier sorti (FIFO). Cela signifie que si 3 messages - m1, m2 et m3 - entrent dans la file d'attente dans cet ordre, ils sortent de la file d'attente exactement dans le même ordre.

Pourquoi avons-nous besoin de files d'attente?

Disons que nous avons des producteurs de données (par exemple, lorsqu'un utilisateur clique sur une page Web) qui sont extrêmement rapides. Mais ensuite, nous voulons consommer ces données à un rythme plus lent plus tard.

Dans ce cas, le producteur pousserait tous les messages dans la file d'attente, et un consommateur consommerait ces messages plus tard à partir de la file d'attente à un rythme plus lent.

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

Comme mentionné précédemment, une file d'attente régulière a une structure premier entré, premier sorti. Mais dans certains scénarios, nous voulons traiter les messages dans une file d'attente en fonction de leur priorité et non en fonction du moment où le message est entré dans la file d'attente.

Les files d'attente prioritaires aident les consommateurs à consommer les messages de priorité plus élevée en premier, suivis des messages de priorité inférieure.

Files d'attente prioritaires en Java

Voyons maintenant du code Java réel qui nous montrera comment utiliser les files d'attente prioritaires.

Files d'attente prioritaires avec ordre naturel

Voici un code montrant comment créer une file d'attente de priorité simple pour les chaînes

private static void testStringsNaturalOrdering() { Queue testStringsPQ = new PriorityQueue(); testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy"); System.out.println("Strings Stored in Natural Ordering in a Priority Queue\n"); while (!testStringsPQ.isEmpty()) { System.out.println(testStringsPQ.poll()); } }

La première ligne nous indique que nous créons une file d'attente prioritaire:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue est disponible dans le package java.util.

Ensuite, nous ajoutons 5 chaînes dans un ordre aléatoire dans la file d'attente prioritaire. Pour cela, nous utilisons la fonction add () comme indiqué ci-dessous:

testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy");

Afin d'obtenir le dernier élément de la file d'attente, nous utilisons la fonction poll () comme indiqué ci-dessous:

testStringsPQ.poll()

poll () nous donnera le dernier élément et le supprimera également de la file d'attente. Si nous voulons obtenir le dernier élément de la file d'attente sans le supprimer, nous pouvons utiliser la fonction peek () :

testStringsPQ.peek()

Enfin, nous imprimons tous les éléments de la file d'attente en utilisant la fonction poll () comme indiqué ci-dessous:

while (!testStringsPQ.isEmpty()) { System.out.println(testStringsPQ.poll()); }

Voici la sortie du programme ci-dessus:

1234 23bc abcd abxy zzxx

Comme nous n'avons pas indiqué à la file d'attente prioritaire comment hiérarchiser son contenu, elle a utilisé un ordre naturel par défaut. Dans ce cas, il nous a renvoyé les données dans l'ordre croissant des chaînes. Ce n'est pas le même ordre dans lequel les éléments ont été ajoutés à la file d'attente.

Qu'en est-il d'avoir une commande personnalisée?

Ceci est également possible et nous pouvons le faire à l'aide d'un comparateur.

Créons maintenant une file d'attente de priorité entière. Mais cette fois, obtenons le résultat par ordre décroissant de valeur.

Pour y parvenir, nous devons d'abord créer un comparateur d'entiers:

 static class CustomIntegerComparator implements Comparator { @Override public int compare(Integer o1, Integer o2) { return o1 < o2 ? 1 : -1; } }

Afin de créer un comparateur, nous implémentons l' interface du comparateur et remplaçons la méthode de comparaison .

En utilisant o1 <o2? 1: -1 nous obtiendrons le résultat par ordre décroissant. Si nous avions utilisé o1> o2? 1: -1, alors nous aurions obtenu le résultat par ordre croissant

Maintenant que nous avons le comparateur, nous devons ajouter ce comparateur à la file d'attente prioritaire. Nous pouvons faire ceci comme ceci:

Queue testIntegersPQ = new PriorityQueue(new CustomIntegerComparator());

Voici le reste du code qui ajoute des éléments dans la file d'attente prioritaire et les imprime:

 testIntegersPQ.add(11); testIntegersPQ.add(5); testIntegersPQ.add(-1); testIntegersPQ.add(12); testIntegersPQ.add(6); System.out.println("Integers stored in reverse order of priority in a Priority Queue\n"); while (!testIntegersPQ.isEmpty()) { System.out.println(testIntegersPQ.poll()); }

La sortie du programme ci-dessus est donnée ci-dessous:

12 11 6 5 -1

On voit que le comparateur a bien fait son travail. Maintenant, la file d'attente prioritaire nous donne les nombres entiers dans l'ordre décroissant.

File d'attente prioritaire avec des objets Java

Jusqu'à présent, nous avons vu comment nous pouvons utiliser des chaînes et des entiers avec des files d'attente prioritaires.

Dans les applications réelles, nous utiliserions généralement des files d'attente prioritaires avec des objets Java personnalisés.

Commençons par créer une classe appelée CustomerOrder qui est utilisée pour stocker les détails de la commande client:

public class CustomerOrder implements Comparable { private int orderId; private double orderAmount; private String customerName; public CustomerOrder(int orderId, double orderAmount, String customerName) { this.orderId = orderId; this.orderAmount = orderAmount; this.customerName = customerName; } @Override public int compareTo(CustomerOrder o) { return o.orderId > this.orderId ? 1 : -1; } @Override public String toString() { return "orderId:" + this.orderId + ", orderAmount:" + this.orderAmount + ", customerName:" + customerName; } public double getOrderAmount() { return orderAmount; } }

Il s'agit d'une classe Java simple pour stocker les commandes des clients. Cette classe implémente une interface comparable, afin que nous puissions décider sur quelle base cet objet doit être ordonné dans la file d'attente prioritaire.

The ordering is decided by the compareTo function in the above code. The line o.orderId > this.orderId ? 1 : -1 instructs that the orders should be sorted based on descending order of the orderId field

Below is the code which creates a priority queue for the CustomerOrder object:

CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

In the above code three customer orders have been created and added to the priority queue.

When we run this code we get the following output:

orderId:3, orderAmount:50.0, customerName:customer3 orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1

As expected, the result comes in descending order of the orderId.

What if we want to prioritize based on orderAmount?

This is again a real life scenario. Let's say that by default the CustomerOrder object is prioritized by the orderId. But then we need a way in which we can prioritize based on orderAmount.

You may immediately think that we can modify the compareTo function in the CustomerOrder class to order based on orderAmount.

But the CustomerOrder class may be used in multiple places in the application, and it would interfere with the rest of the application if we modify the compareTo function directly.

The solution to this is pretty simple: we can create a new custom comparator for the CustomerOrder class and use that along with the priority queue

Below is the code for the custom comparator:

 static class CustomerOrderComparator implements Comparator { @Override public int compare(CustomerOrder o1, CustomerOrder o2) { return o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; } }

This is very similar to the custom integer comparator we saw earlier.

The line o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; indicates that we need to prioritize based on descending order of orderAmount.

Below is the code which creates the priority queue:

 CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(new CustomerOrderComparator()); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

In the above code we are passing the comparator to the priority queue in the following line of code:

Queue customerOrders = new PriorityQueue(new CustomerOrderComparator());

Below is the result when we run this code:

orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1 orderId:3, orderAmount:50.0, customerName:customer3

We can see that the data comes in descending order of the orderAmount.

Code

All the code discussed in this article can be found in this GitHub repo.

Congrats ?

You now know how to use priority queues in Java.

About the author

I love technology and follow the advancements in the field. I also like helping others with my technology knowledge.

Feel free to connect with me on my LinkedIn account //www.linkedin.com/in/aditya1811/

You can also follow me on twitter //twitter.com/adityasridhar18

Feel free to read more of my articles on my blog at adityasridhar.com.