Tärkeät jonot Java-selityksessä esimerkeillä

Prioriteettijonoja käytetään hyvin usein tosielämän sovelluksissa. Tässä artikkelissa opit, mitkä prioriteettijonot ovat ja miten voimme käyttää niitä Java-käyttöjärjestelmässä.

Ennen kuin keskustelemme prioriteettijonosta, katsotaanpa, mikä on tavallinen jono.

Säännöllinen jono seuraa FIFO-rakennetta. Tämä tarkoittaa, että jos 3 viestiä - m1, m2 ja m3 - menee jonoon siinä järjestyksessä, ne tulevat ulos jonosta täsmälleen samassa järjestyksessä.

Miksi tarvitsemme jonoja?

Sanotaan, että meillä on tietojen tuottajia (esimerkiksi kun käyttäjä napsauttaa verkkosivua), jotka ovat erittäin nopeita. Mutta sitten haluamme kuluttaa nämä tiedot myöhemmin hitaammin.

Tällöin tuottaja työntäisi kaikki viestit jonoon ja kuluttaja kuluttaisi nämä viestit myöhemmin jonosta hitaammin.

Mikä on prioriteettijono?

Kuten aiemmin mainittiin, tavallisella jonolla on rakenne ensimmäisestä ensimmäiseksi. Joissakin tilanteissa haluamme käsitellä viestejä jonossa niiden prioriteetin perusteella eikä sen perusteella, milloin viesti tuli jonoon.

Prioriteettijonot auttavat kuluttajia kuluttamaan korkeamman prioriteetin viestejä, joita seuraavat ensin matalamman prioriteetin viestit.

Prioriteettijonot Javalla

Katsotaan nyt joitain todellisia Java-koodeja, jotka osoittavat meille, kuinka prioriteettijonoja käytetään.

Ensisijaiset jonot luonnollisella järjestyksellä

Tässä on koodi, joka näyttää yksinkertaisen prioriteettijonon luomisen merkkijonoille

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

Ensimmäisellä rivillä kerrotaan, että olemme luomassa prioriteettijonoa:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue on saatavana paketissa java.util.

Seuraavaksi lisätään 5 merkkijonoa satunnaisessa järjestyksessä prioriteettijonoon. Tätä varten käytämme add () -funktiota alla olevan kuvan mukaisesti:

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

Saadaksesi viimeisimmän kohteen jonosta käytämme poll () -toimintoa alla olevan kuvan mukaisesti:

testStringsPQ.poll()

poll () antaa meille viimeisimmän kohteen ja poistaa sen myös jonosta. Jos haluamme saada viimeisimmän jonon kohteen poistamatta sitä, voimme käyttää peek () -toimintoa:

testStringsPQ.peek()

Lopuksi tulostamme kaikki jonon elementit käyttämällä poll () -funktiota alla esitetyllä tavalla:

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

Tässä on yllä olevan ohjelman tulos:

1234 23bc abcd abxy zzxx

Koska emme kertoneet prioriteettijonolle, miten sen sisältö priorisoidaan, se käytti oletusarvoista luonnollista järjestystä. Tässä tapauksessa se antoi meille tiedot takaisin merkkijonojen nousevassa järjestyksessä. Kohteet lisättiin jonoon samassa järjestyksessä.

Entä mukautettu tilaus?

Tämä on myös mahdollista, ja voimme tehdä sen vertailijan avulla.

Luodaan nyt kokonaislukuinen prioriteettijono. Mutta tällä kertaa saadaan tulos laskevassa arvojärjestyksessä.

Tämän saavuttamiseksi meidän on ensin luotava kokonaislukuvertailija:

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

Vertailijan luomiseksi toteutamme vertailurajapinnan ja ohitamme vertailumenetelmän .

Käyttämällä o1 <o2? 1: -1 saamme tuloksen laskevassa järjestyksessä. Jos olisimme käyttäneet o1> o2? 1: -1, niin olisimme saaneet tuloksen nousevassa järjestyksessä

Nyt kun meillä on vertailija, meidän on lisättävä tämä vertailija prioriteettijonoon. Voimme tehdä tämän näin:

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

Tässä on loput koodista, joka lisää elementit prioriteettijonoon ja tulostaa ne:

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

Edellä olevan ohjelman tulos on annettu alla:

12 11 6 5 -1

Voimme nähdä, että vertailija on tehnyt työnsä hyvin. Nyt prioriteettijono antaa meille kokonaisluvut laskevassa järjestyksessä.

Prioriteettijono Java-objekteilla

Tähän asti olemme nähneet, kuinka voimme käyttää merkkijonoja ja kokonaislukuja prioriteettijonoilla.

Tosielämän sovelluksissa käytämme yleensä prioriteettijonoja mukautettujen Java-objektien kanssa.

Luodaan ensin luokka nimeltä CustomerOrder, jota käytetään asiakkaiden tilaustietojen tallentamiseen:

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

Tämä on yksinkertainen Java-luokka asiakkaiden tilausten tallentamiseen. Tämä luokka toteuttaa vertailukelpoisen käyttöliittymän, jotta voimme päättää, minkä perusteella tämä objekti on tilattava prioriteettijonoon.

Tilauksen päättää vertailutoiminto yllä olevassa koodissa. Rivi o.orderId> this.orderId? 1: -1 kehottaa tilauksia lajittelemaan orderId- kentän laskevaan järjestykseen perustuen

Alla on koodi, joka luo prioriteettijonon CustomerOrder-objektille:

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

Yllä olevassa koodissa on luotu kolme asiakastilausta, jotka on lisätty prioriteettijonoon.

Kun suoritamme tämän koodin, saamme seuraavan tuloksen:

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

Kuten odotettiin, tulos tulee orderId : n laskevassa järjestyksessä .

Entä jos haluamme priorisoida orderAmountin perusteella?

Tämä on jälleen tosielämän skenaario. Oletetaan, että oletusarvoisesti CustomerOrder-objekti priorisoidaan orderId: llä. Mutta sitten tarvitsemme tavan, jolla voimme priorisoida orderAmountin perusteella.

Saatat heti ajatella, että voimme muuttaa compareTo toiminto CustomerOrder C tyttö Tilauksen perustuu orderAmount.

Mutta CustomerOrder c -laskinta voidaan käyttää sovelluksen useissa paikoissa, ja se häiritsisi muuta sovellusta, jos muokkaamme vertailutoimintoa suoraan.

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

Rakastan tekniikkaa ja seuraan alan edistystä. Pidän myös muiden auttamisesta tekniikan tuntemuksellani.

Ota rohkeasti yhteyttä minuun LinkedIn-tililläni //www.linkedin.com/in/aditya1811/

Voit myös seurata minua twitterissä //twitter.com/adityasridhar18

Voit vapaasti lukea lisää artikkeleitani blogissani osoitteessa adityasridhar.com.