Antrian Prioritas di Jawa Dijelaskan dengan Contoh

Antrean Prioritas sangat sering digunakan dalam aplikasi kehidupan nyata. Pada artikel ini kita akan mempelajari apa itu antrian prioritas dan bagaimana kita dapat menggunakannya di Java.

Sebelum kita membahas apa itu antrian prioritas, mari kita lihat apa itu antrian biasa.

Antrian reguler mengikuti struktur first in first out (FIFO). Artinya, jika 3 pesan - m1, m2, dan m3 - masuk ke antrean dengan urutan tersebut, maka pesan keluar dari antrean dengan urutan yang sama persis.

Mengapa kita membutuhkan antrian?

Katakanlah kita memiliki produsen data (misalnya, ketika pengguna mengklik halaman web) yang sangat cepat. Namun kemudian kami ingin menggunakan data ini dengan kecepatan yang lebih lambat nanti.

Dalam kasus ini, produsen akan memasukkan semua pesan ke antrean, dan konsumen akan menggunakan pesan ini nanti dari antrean dengan lebih lambat.

Apa itu antrian prioritas?

Seperti disebutkan sebelumnya, antrian biasa memiliki struktur first in first out. Tetapi dalam beberapa skenario kami ingin memproses pesan dalam antrian berdasarkan prioritasnya dan bukan berdasarkan pada saat pesan masuk antrian.

Antrian prioritas membantu konsumen mengonsumsi pesan dengan prioritas lebih tinggi terlebih dahulu diikuti oleh pesan prioritas lebih rendah.

Antrian prioritas di Jawa

Sekarang mari kita lihat beberapa kode Java yang akan menunjukkan kepada kita bagaimana menggunakan antrian prioritas.

Antrian prioritas dengan pemesanan alami

Berikut adalah beberapa kode yang menunjukkan cara membuat antrian prioritas sederhana untuk string

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

Baris pertama memberi tahu kita bahwa kita membuat antrian prioritas:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue tersedia dalam paket java.util.

Selanjutnya kami menambahkan 5 string secara acak ke dalam antrian prioritas. Untuk ini kami menggunakan fungsi add () seperti yang ditunjukkan di bawah ini:

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

Untuk mendapatkan item terbaru dari antrian kita menggunakan fungsi poll () seperti yang ditunjukkan di bawah ini:

testStringsPQ.poll()

poll () akan memberi kita item terbaru dan juga menghapusnya dari antrian. Jika kita ingin mendapatkan item terbaru dalam antrian tanpa menghapusnya, kita bisa menggunakan fungsi peek () :

testStringsPQ.peek()

Akhirnya, kami mencetak semua elemen dari antrian dengan menggunakan fungsi poll () seperti yang ditunjukkan di bawah ini:

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

Berikut adalah output dari program diatas:

1234 23bc abcd abxy zzxx

Karena kami tidak memberi tahu antrian prioritas bagaimana memprioritaskan kontennya, itu menggunakan pengurutan alami default. Dalam hal ini, ini memberi kami data kembali dalam urutan menaik dari string. Ini bukan urutan yang sama saat item ditambahkan ke antrean.

Bagaimana dengan pemesanan khusus?

Ini juga dimungkinkan, dan kami dapat melakukannya dengan bantuan komparator.

Mari buat antrian prioritas integer sekarang. Tapi kali ini mari kita dapatkan hasilnya dalam urutan nilai yang menurun.

Untuk mencapai ini, pertama kita perlu membuat pembanding integer:

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

Untuk membuat pembanding, kami menerapkan antarmuka pembanding dan mengganti metode perbandingan .

Dengan menggunakan o1 <o2? 1: -1 kita akan mendapatkan hasilnya dalam urutan menurun. Jika kita telah menggunakan o1> o2? 1: -1, maka kita akan mendapatkan hasilnya dalam urutan naik

Sekarang kita memiliki pembanding, kita perlu menambahkan pembanding ini ke antrian prioritas. Kita bisa melakukan ini seperti ini:

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

Berikut adalah kode lainnya yang menambahkan elemen ke dalam antrian prioritas dan mencetaknya:

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

Output dari program di atas diberikan di bawah ini:

12 11 6 5 -1

Kita dapat melihat bahwa pembanding telah melakukan tugasnya dengan baik. Sekarang antrian prioritas memberi kita bilangan bulat dalam urutan menurun.

Antrian prioritas dengan objek Java

Sampai saat ini, kita telah melihat bagaimana kita dapat menggunakan string dan integer dengan antrian prioritas.

Dalam aplikasi kehidupan nyata, kami biasanya menggunakan antrian prioritas dengan objek Java khusus.

Mari pertama-tama buat kelas yang disebut CustomerOrder yang digunakan untuk menyimpan detail pesanan pelanggan:

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

Ini adalah kelas Java sederhana untuk menyimpan pesanan pelanggan. Kelas ini mengimplementasikan antarmuka yang sebanding, sehingga kita dapat memutuskan atas dasar apa objek ini perlu diurutkan dalam antrian prioritas.

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.