Prioriterede køer i Java forklaret med eksempler

Prioritetskø bruges meget ofte i applikationer i det virkelige liv. I denne artikel lærer vi, hvilke prioritetskøer er, og hvordan vi kan bruge dem i Java.

Før vi diskuterer, hvad en prioritetskø er, skal vi se, hvad en almindelig kø er.

En regelmæssig kø følger en FIFO-struktur (first in first out). Dette betyder, at hvis 3 meddelelser - m1, m2 og m3 - går ind i køen i den rækkefølge, så kommer de ud af køen i nøjagtig samme rækkefølge.

Hvorfor har vi brug for køer?

Lad os sige, at vi har dataproducenter (for eksempel når en bruger klikker på en webside), som er ekstremt hurtige. Men så vil vi forbruge disse data i et langsommere tempo senere.

I dette tilfælde vil producenten skubbe alle meddelelserne ind i køen, og en forbruger vil forbruge disse meddelelser senere fra køen i et langsommere tempo.

Hvad er en prioritetskø?

Som nævnt tidligere har en almindelig kø en først ind-ud-struktur. Men i nogle scenarier vil vi behandle meddelelser i en kø baseret på deres prioritet og ikke baseret på, hvornår meddelelsen kom ind i køen.

Prioritetskø hjælper forbrugerne med at forbruge meddelelser med højere prioritet, efterfulgt af meddelelser med lavere prioritet.

Prioriterede køer i Java

Lad os nu se nogle faktiske Java-koder, der viser os, hvordan vi bruger prioritetskøer.

Prioriterede køer med naturlig bestilling

Her er nogle koder, der viser, hvordan du opretter en simpel prioritetskø til strenge

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

Den første linje fortæller os, at vi opretter en prioritetskø:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue fås i pakken java.util.

Dernæst tilføjer vi 5 strenge i tilfældig rækkefølge i prioritetskøen. Til dette bruger vi add () -funktionen som vist nedenfor:

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

For at få det nyeste element fra køen bruger vi poll () -funktionen som vist nedenfor:

testStringsPQ.poll()

afstemning () giver os det nyeste element og fjerner det også fra køen. Hvis vi vil hente det nyeste element i køen uden at fjerne det, kan vi bruge peek () -funktionen:

testStringsPQ.peek()

Endelig udskriver vi alle elementerne fra køen ved hjælp af poll () -funktionen som vist nedenfor:

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

Her er output fra ovenstående program:

1234 23bc abcd abxy zzxx

Da vi ikke fortalte prioritetskøen, hvordan man prioriterede dens indhold, brugte den en standard naturlig ordning. I dette tilfælde gav det os dataene tilbage i stigende rækkefølge af strengene. Dette er ikke den samme rækkefølge, som varer blev føjet til køen.

Hvad med at have en specialbestilling?

Dette er også muligt, og vi kan gøre det ved hjælp af en komparator.

Lad os oprette en heltals prioritetskø nu. Men denne gang lad os få resultatet i faldende rækkefølge af værdi.

For at opnå dette skal vi først oprette en heltalskomparator:

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

For at oprette en komparator implementerer vi komparatorgrænsefladen og tilsidesætter sammenligningsmetoden .

Ved at bruge o1 <o2? 1: -1 får vi resultatet i faldende rækkefølge. Hvis vi havde brugt o1> o2? 1: -1, så ville vi have fået resultatet i stigende rækkefølge

Nu hvor vi har komparatoren, skal vi tilføje denne komparator til prioritetskøen. Vi kan gøre dette sådan:

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

Her er resten af ​​koden, der tilføjer elementer i prioritetskøen og udskriver dem:

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

Resultatet af ovenstående program er angivet nedenfor:

12 11 6 5 -1

Vi kan se, at komparatoren har gjort sit job godt. Nu giver prioritetskøen os heltallene i faldende rækkefølge.

Prioritetskø med Java-objekter

Indtil dette tidspunkt har vi set, hvordan vi kan bruge strenge og heltal med prioritetskøer.

I virkelige applikationer bruger vi generelt prioritetskøer med brugerdefinerede Java-objekter.

Lad os først oprette en klasse kaldet CustomerOrder, der bruges til at gemme kundeordreoplysninger:

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

Dette er en simpel Java-klasse til at gemme kundeordrer. Denne klasse implementerer sammenlignelig grænseflade, så vi kan beslutte på hvilket grundlag dette objekt skal bestilles i prioritetskøen.

Bestillingen bestemmes af sammenligningsfunktionen i ovenstående kode. Linjen o.orderId> this.orderId? 1: -1 instruerer, at ordrene skal sorteres baseret på faldende rækkefølge i orderId- feltet

Nedenfor er koden, der opretter en prioritetskø til CustomerOrder-objektet:

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

I ovenstående kode er der oprettet tre kundeordrer og tilføjet til prioritetskøen.

Når vi kører denne kode, får vi følgende 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

Jeg elsker teknologi og følger fremskridtene inden for området. Jeg kan også godt lide at hjælpe andre med min teknologiske viden.

Du er velkommen til at oprette forbindelse til mig på min LinkedIn-konto //www.linkedin.com/in/aditya1811/

Du kan også følge mig på twitter //twitter.com/adityasridhar18

Du er velkommen til at læse flere af mine artikler på min blog på adityasridhar.com.