Опашки с приоритет в Java, обяснени с примери

Приоритетни опашки се използват много често в реални приложения. В тази статия ще научим какво представляват приоритетните опашки и как можем да ги използваме в Java.

Преди да обсъдим какво е приоритетна опашка, нека видим какво представлява обикновената опашка.

Редовната опашка следва структура първи в първи изход (FIFO). Това означава, че ако 3 съобщения - m1, m2 и m3 - влязат в опашката в този ред, тогава те излизат от опашката в точно същия ред.

Защо се нуждаем от опашки?

Нека кажем, че имаме производители на данни (например, когато потребител кликне върху уеб страница), които са изключително бързи. Но тогава искаме да консумираме тези данни по-бавно по-късно.

В този случай производителят щраква всички съобщения в опашката и потребителят ще консумира тези съобщения по-късно от опашката с по-бавни темпове.

Какво е приоритетна опашка?

Както бе споменато по-рано, обикновената опашка има структура първи в първи изход. Но в някои сценарии искаме да обработваме съобщения в опашка въз основа на техния приоритет, а не въз основа на това кога съобщението е влязло в опашката.

Опашките с приоритет помагат на потребителите да консумират съобщенията с по-висок приоритет, последвани от съобщенията с по-нисък приоритет.

Опашки с приоритет в Java

Сега нека видим някои действителни Java кодове, които ще ни покажат как да използваме приоритетни опашки.

Опашки с приоритет с естествено подреждане

Ето малко код, показващ как да създадете проста опашка с приоритет за низове

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

Първият ред ни казва, че създаваме приоритетна опашка:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue се предлага в пакета java.util.

След това добавяме 5 низа в произволен ред в приоритетната опашка. За това използваме функцията add (), както е показано по-долу:

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

За да получим най-новия елемент от опашката, използваме функцията poll (), както е показано по-долу:

testStringsPQ.poll()

poll () ще ни даде най-новия елемент и също така ще го премахне от опашката. Ако искаме да получим най-новия елемент в опашката, без да го премахваме, можем да използваме функцията peek () :

testStringsPQ.peek()

И накрая, разпечатваме всички елементи от опашката, като използваме функцията poll (), както е показано по-долу:

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

Ето резултата от горната програма:

1234 23bc abcd abxy zzxx

Тъй като не казахме на приоритетната опашка как да приоритизираме съдържанието й, тя използва естествено подреждане по подразбиране. В този случай тя ни върна данните във възходящ ред на низовете. Това не е същият ред, в който елементи са добавени към опашката.

Какво ще кажете за поръчка по поръчка?

Това също е възможно и можем да го направим с помощта на компаратор.

Нека създадем опашка с целочислени приоритети сега. Но този път нека вземем резултата в низходящ ред на стойността.

За да постигнем това, първо трябва да създадем целочислено сравнение:

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

За да създадем компаратор, ние прилагаме интерфейса за сравнение и заместваме метода за сравнение .

Като използвате o1 <o2? 1: -1 ще получим резултата в низходящ ред. Ако бяхме използвали o1> o2? 1: -1, тогава щяхме да получим резултата във възходящ ред

Сега, когато разполагаме с компаратора, трябва да добавим този компаратор към приоритетната опашка. Можем да направим това по следния начин:

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

Ето останалата част от кода, който добавя елементи в опашката с приоритет и ги отпечатва:

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

Резултатът от горната програма е даден по-долу:

12 11 6 5 -1

Виждаме, че компараторът си е свършил добре работата. Сега приоритетната опашка ни дава целите числа в низходящ ред.

Приоритетна опашка с Java обекти

До този момент видяхме как можем да използваме низове и цели числа с приоритетни опашки.

В реални приложения обикновено бихме използвали приоритетни опашки с персонализирани Java обекти.

Нека първо създадем клас, наречен CustomerOrder, който се използва за съхраняване на подробности за поръчки на клиенти:

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

Това е прост Java клас за съхраняване на поръчки на клиенти. Този клас изпълнява сравним интерфейс, така че да можем да решим на каква основа този обект трябва да бъде подреден в приоритетната опашка.

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.