Prioritätswarteschlangen in Java werden anhand von Beispielen erläutert

Prioritätswarteschlangen werden sehr häufig in realen Anwendungen verwendet. In diesem Artikel erfahren Sie, welche Prioritätswarteschlangen vorhanden sind und wie wir sie in Java verwenden können.

Bevor wir uns mit einer Prioritätswarteschlange befassen, wollen wir uns ansehen, was eine reguläre Warteschlange ist.

Eine reguläre Warteschlange folgt einer FIFO-Struktur (First In First Out). Dies bedeutet, dass wenn 3 Nachrichten - m1, m2 und m3 - in dieser Reihenfolge in die Warteschlange gestellt werden, sie in genau derselben Reihenfolge aus der Warteschlange kommen.

Warum brauchen wir Warteschlangen?

Nehmen wir an, wir haben Datenproduzenten (zum Beispiel, wenn ein Benutzer auf eine Webseite klickt), die extrem schnell sind. Aber dann wollen wir diese Daten später langsamer nutzen.

In diesem Fall würde der Produzent alle Nachrichten in die Warteschlange schieben, und ein Verbraucher würde diese Nachrichten später langsamer aus der Warteschlange konsumieren.

Was ist eine Prioritätswarteschlange?

Wie bereits erwähnt, hat eine reguläre Warteschlange eine First-In-First-Out-Struktur. In einigen Szenarien möchten wir jedoch Nachrichten in einer Warteschlange basierend auf ihrer Priorität und nicht basierend darauf, wann die Nachricht in die Warteschlange eingetreten ist, verarbeiten.

Prioritätswarteschlangen helfen Verbrauchern dabei, zuerst die Nachrichten mit höherer Priorität und anschließend die Nachrichten mit niedrigerer Priorität zu verwenden.

Prioritätswarteschlangen in Java

Schauen wir uns nun einen aktuellen Java-Code an, der uns zeigt, wie Prioritätswarteschlangen verwendet werden.

Prioritätswarteschlangen mit natürlicher Reihenfolge

Hier ist ein Code, der zeigt, wie eine einfache Prioritätswarteschlange für Zeichenfolgen erstellt wird

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()); } }

Die erste Zeile sagt uns, dass wir eine Prioritätswarteschlange erstellen:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue ist im Paket java.util verfügbar.

Als nächstes fügen wir der Prioritätswarteschlange 5 Zeichenfolgen in zufälliger Reihenfolge hinzu. Dazu verwenden wir die Funktion add () wie folgt:

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

Um das neueste Element aus der Warteschlange zu erhalten, verwenden wir die Funktion poll () wie folgt:

testStringsPQ.poll()

poll () gibt uns das neueste Element und entfernt es aus der Warteschlange. Wenn wir das neueste Element in der Warteschlange abrufen möchten, ohne es zu entfernen, können wir die Funktion peek () verwenden:

testStringsPQ.peek()

Schließlich drucken wir alle Elemente aus der Warteschlange mit der Funktion poll () aus, wie unten gezeigt:

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

Hier ist die Ausgabe des obigen Programms:

1234 23bc abcd abxy zzxx

Da wir der Prioritätswarteschlange nicht mitgeteilt haben, wie sie ihren Inhalt priorisieren soll, wurde eine natürliche Standardreihenfolge verwendet. In diesem Fall gab es uns die Daten in aufsteigender Reihenfolge der Zeichenfolgen zurück. Dies ist nicht dieselbe Reihenfolge, in der Elemente zur Warteschlange hinzugefügt wurden.

Was ist mit einer Sonderanfertigung?

Dies ist ebenfalls möglich, und wir können dies mit Hilfe eines Komparators tun .

Lassen Sie uns jetzt eine Warteschlange mit ganzzahliger Priorität erstellen. Aber dieses Mal erhalten wir das Ergebnis in absteigender Reihenfolge des Wertes.

Um dies zu erreichen, müssen wir zuerst einen ganzzahligen Komparator erstellen:

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

Um einen Komparator zu erstellen, implementieren wir die Komparatorschnittstelle und überschreiben die Vergleichsmethode .

Mit o1 <o2? 1: -1 erhalten wir das Ergebnis in absteigender Reihenfolge. Wenn wir o1> o2 verwendet hätten? 1: -1, dann hätten wir das Ergebnis in aufsteigender Reihenfolge erhalten

Nachdem wir den Komparator haben, müssen wir diesen Komparator zur Prioritätswarteschlange hinzufügen. Wir können das so machen:

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

Hier ist der Rest des Codes, der Elemente zur Prioritätswarteschlange hinzufügt und sie druckt:

 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()); }

Die Ausgabe des obigen Programms ist unten angegeben:

12 11 6 5 -1

Wir können sehen, dass der Komparator seine Arbeit gut gemacht hat. Jetzt gibt uns die Prioritätswarteschlange die ganzen Zahlen in absteigender Reihenfolge.

Prioritätswarteschlange mit Java-Objekten

Bis zu diesem Punkt haben wir gesehen, wie wir Zeichenfolgen und Ganzzahlen mit Prioritätswarteschlangen verwenden können.

In realen Anwendungen verwenden wir im Allgemeinen Prioritätswarteschlangen mit benutzerdefinierten Java-Objekten.

Erstellen wir zunächst eine Klasse namens CustomerOrder, in der Kundenbestelldetails gespeichert werden:

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; } }

Dies ist eine einfache Java-Klasse zum Speichern von Kundenaufträgen. Diese Klasse implementiert eine vergleichbare Schnittstelle, sodass wir entscheiden können, auf welcher Basis dieses Objekt in der Prioritätswarteschlange sortiert werden muss.

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.