Näidetega selgitatud Java prioriteetsed järjekorrad

Prioriteedijärjekordi kasutatakse päriselus rakendustes väga sageli. Sellest artiklist saame teada, mis on prioriteetsed järjekorrad ja kuidas saame neid Java-s kasutada.

Enne kui arutame, mis on prioriteetne järjekord, vaatame, mis on tavaline järjekord.

Tavapärane järjekord järgneb FIFO (first in first out) struktuurile. See tähendab, et kui 3 teadet - m1, m2 ja m3 - lähevad järjekorda selles järjekorras, siis tulevad nad järjekorrast välja täpselt samas järjekorras.

Miks me vajame järjekordi?

Oletame, et meil on andmete tootjaid (näiteks kui kasutaja klõpsab veebilehel), mis on ülikiire. Kuid siis tahame neid andmeid aeglasemas tempos hiljem tarbida.

Sellisel juhul suruks tootja kõik sõnumid järjekorda ja tarbija tarbiks neid sõnumeid hiljem järjekorrast aeglasemas tempos.

Mis on prioriteetne järjekord?

Nagu varem mainitud, on tavalise järjekorra struktuur esimesest esimesest välja. Mõnes stsenaariumis tahame sõnumeid järjekorras töödelda lähtuvalt nende prioriteedist ja mitte sellest, millal sõnum järjekorda sisenes.

Prioriteedijärjekorrad aitavad tarbijatel tarbida kõrgema prioriteediga sõnumeid, millele järgnevad madalama prioriteediga sõnumid.

Prioriteetsed järjekorrad Java-s

Nüüd vaatame mõnda tegelikku Java-koodi, mis näitab meile, kuidas kasutada prioriteetset järjekorda.

Prioriteetsed järjekorrad loomuliku tellimisega

Siin on mõni kood, mis näitab, kuidas luua stringidele lihtne prioriteetne järjekord

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

Esimene rida ütleb meile, et loome prioriteetset järjekorda:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue on saadaval paketis java.util.

Järgmisena lisame prioriteedijärjekorda 5 juhuslikku järjestust. Selleks kasutame funktsiooni add (), nagu allpool näidatud:

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

Järjekorrast viimase üksuse saamiseks kasutame poll () funktsiooni, nagu allpool näidatud:

testStringsPQ.poll()

küsitlus () annab meile viimase üksuse ja eemaldab selle ka järjekorrast. Kui tahame saada järjekorras viimase üksuse seda eemaldamata, saame kasutada funktsiooni peek () :

testStringsPQ.peek()

Lõpuks printime kõik elemendid järjekorrast välja, kasutades poll () funktsiooni, nagu allpool näidatud:

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

Siin on ülaltoodud programmi väljund:

1234 23bc abcd abxy zzxx

Kuna me ei öelnud prioriteetsele järjekorrale, kuidas selle sisu prioriseerida, kasutas see vaikimisi loomulikku järjestust. Sel juhul andis see meile andmed tagasi stringide kasvavas järjekorras. See pole sama järjekord, milles üksused järjekorda lisati.

Aga tellimusega tellimine?

See on ka võimalik ja me saame seda teha võrdluse abil.

Loome nüüd täisarvulise prioriteedijärjekorra. Kuid seekord saame tulemuse väärtuse kahanevas järjekorras.

Selle saavutamiseks peame kõigepealt looma täisarvu võrdleja:

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

Selleks, et luua võrdlusmenet- me rakendada võrdlevates liides ja alistada võrrelda meetod.

Kasutades o1 <o2? 1: -1 saame tulemuse kahanevas järjekorras. Kui me oleksime kasutanud o1> o2? 1: -1, siis oleksime tulemuse saanud kasvavas järjekorras

Nüüd, kui meil on võrdlusmasin olemas, peame selle võrdleja lisama prioriteetsesse järjekorda. Saame seda teha nii:

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

Siin on ülejäänud kood, mis lisab prioriteedijärjekorda elemendid ja prindib need:

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

Ülaltoodud programmi väljund on toodud allpool:

12 11 6 5 -1

Näeme, et võrdleja on oma tööd hästi teinud. Nüüd annab prioriteetne järjekord täisarvud kahanevas järjekorras.

Prioriteetne Java-objektidega järjekord

Siiani oleme näinud, kuidas saame stringe ja täisarvusid kasutada prioriteetsete järjekordadega.

Päriselus rakendustes kasutaksime tavaliselt Java-kohandatud objektidega prioriteetset järjekorda.

Loome kõigepealt klassi nimega CustomerOrder, mida kasutatakse klientide tellimuste üksikasjade salvestamiseks:

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

See on lihtne Java-klass klientide tellimuste salvestamiseks. See klass rakendab võrreldavat liidest, et saaksime otsustada, mille alusel see objekt prioriteedijärjekorras tuleb tellida.

Järjekord otsustab compareTo funktsiooni eespool koodi. Rida o.orderId> this.orderId? 1: -1 juhendab et tellimusi tuleb järjestatud põhineb kahanevas järjekorras TellimuseID valdkonnas

Allpool on kood, mis loob prioriteedijärjekorra objektile CustomerOrder:

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

Ülalolevas koodis on loodud kolm klienditellimust ja lisatud prioriteedijärjekorda.

Selle koodi käivitamisel saame järgmise väljundi:

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

Ootuspäraselt tuleb tulemus orderId kahanevas järjekorras .

Mis siis, kui soovime prioriteedid seada orderAmount põhjal?

See on jällegi reaalse elu stsenaarium. Oletame, et vaikimisi on objekti CustomerOrder prioriteediks orderId. Kuid siis vajame viisi, kuidas saaksime järjekorda orderAmount põhjal prioriseerida.

Võite kohe mõelda, et saame muuta CustomerOrder c lass funktsiooni võrrelda To tellimiseks, mis põhineb orderAmountil.

Kuid CustomerOrder c lass võib rakenduses kasutada mitmes kohas ja see häiriks ülejäänud rakendust, kui muudame otseselt funktsiooni CompareTo .

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

Ma armastan tehnoloogiat ja jälgin selle valdkonna edusamme. Mulle meeldib ka teisi oma tehnoloogiaalaste teadmistega aidata.

Võtke minuga ühendust oma LinkedIni kontol //www.linkedin.com/in/aditya1811/

Samuti saate mind jälgida twitteris //twitter.com/adityasridhar18

Lugege julgelt rohkem minu artikleid minu ajaveebist aadressil adityasridhar.com.