فهم قوائم الانتظار ذات الأولوية (Priority Queues) في Java: دليل شامل مع الأمثلة

مقدمة إلى قوائم الانتظار (Queues) ومفهوم الأولوية

تُعد قوائم الانتظار ذات الأولوية (Priority Queues) من هياكل البيانات الأساسية التي تجد تطبيقات واسعة في العديد من الأنظمة البرمجية الواقعية. على عكس قوائم الانتظار التقليدية، التي تتبع مبدأ First-In, First-Out (FIFO)، تتيح لنا قوائم الانتظار ذات الأولوية معالجة العناصر بناءً على أهميتها أو أولويتها المحددة. في هذا المقال، سنتعمق في فهم ماهية هذه القوائم، وكيفية استخدامها بفعالية في لغة Java، مع أمثلة عملية توضح مختلف سيناريوهات التطبيق.

ما هي قائمة الانتظار العادية؟ (FIFO)

تتبع قائمة الانتظار العادية مبدأ First-In, First-Out (FIFO)، مما يعني أن العنصر الذي يدخل القائمة أولاً هو نفسه الذي يخرج منها أولاً. تخيل ثلاثة رسائل، m1 و m2 و m3، تدخل القائمة بهذا الترتيب. ستخرج الرسائل من القائمة بنفس الترتيب تمامًا: m1 ثم m2 ثم m3.

لماذا نحتاج إلى قوائم الانتظار؟

تنشأ الحاجة إلى قوائم الانتظار في سيناريوهات متعددة حيث يكون هناك تباين في سرعات معالجة البيانات. على سبيل المثال، قد يكون لدينا منتجون للبيانات (مثل نقرات المستخدمين على صفحة ويب) يعملون بسرعة فائقة ويولدون كميات كبيرة من البيانات. في المقابل، قد نحتاج إلى استهلاك هذه البيانات ومعالجتها بوتيرة أبطأ لاحقًا. في هذه الحالة، يقوم المنتج بدفع جميع الرسائل إلى قائمة الانتظار، ويقوم المستهلك بسحب هذه الرسائل من القائمة ومعالجتها ببطء، مما يضمن سلاسة العمليات وتجنب فقدان البيانات.

ما هي قائمة الانتظار ذات الأولوية (Priority Queue)؟

كما ذكرنا سابقًا، تتبع قائمة الانتظار العادية هيكل First-In, First-Out. ولكن في بعض السيناريوهات، نحتاج إلى معالجة الرسائل في قائمة الانتظار بناءً على أولويتها وليس بناءً على وقت دخولها. هنا يأتي دور قوائم الانتظار ذات الأولوية، حيث تمكّن المستهلكين من معالجة الرسائل ذات الأولوية الأعلى أولاً، تليها الرسائل ذات الأولوية الأقل. هذا يضمن أن المهام الحرجة أو البيانات الأكثر أهمية تُعالج بشكل فوري.

تطبيق قوائم الانتظار ذات الأولوية في Java

الآن، دعنا نستعرض بعض أكواد Java الفعلية التي توضح كيفية استخدام قوائم الانتظار ذات الأولوية.

قوائم الانتظار ذات الأولوية مع الترتيب الطبيعي (Natural Ordering)

يوضح الكود التالي كيفية إنشاء قائمة انتظار ذات أولوية بسيطة لسلاسل نصية (Strings) تستخدم الترتيب الطبيعي الافتراضي:

 private static void testStringsNaturalOrdering () {
    Queue<String> 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<String> testStringsPQ = new PriorityQueue<>();

الفئة PriorityQueue متاحة ضمن الحزمة java.util. بعد ذلك، نقوم بإضافة خمس سلاسل نصية بترتيب عشوائي إلى قائمة الانتظار ذات الأولوية. لهذا الغرض، نستخدم الدالة add() كما هو موضح أدناه:

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

للحصول على العنصر ذي الأولوية الأعلى من القائمة وإزالته منها، نستخدم الدالة poll():

testStringsPQ.poll()

إذا أردنا الحصول على العنصر ذي الأولوية الأعلى دون إزالته من القائمة، يمكننا استخدام الدالة peek():

testStringsPQ.peek()

أخيرًا، نطبع جميع العناصر من القائمة باستخدام الدالة poll() حتى تصبح القائمة فارغة:

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

إليك مخرجات البرنامج أعلاه:

1234
23bc
abcd
abxy
zzxx

نظرًا لأننا لم نحدد لقائمة الانتظار ذات الأولوية كيفية ترتيب محتواها، فقد استخدمت ترتيبًا طبيعيًا افتراضيًا. في هذه الحالة، أعادت لنا البيانات بترتيب تصاعدي للسلاسل النصية (ترتيب أبجدي). لاحظ أن هذا ليس نفس الترتيب الذي أُضيفت به العناصر إلى القائمة.

تخصيص ترتيب الأولوية باستخدام واجهة Comparator

ماذا لو أردنا ترتيبًا مخصصًا؟ هذا ممكن أيضًا، ويمكننا تحقيقه بمساعدة واجهة Comparator. دعنا ننشئ الآن قائمة انتظار ذات أولوية للأعداد الصحيحة، ولكن هذه المرة نريد الحصول على النتيجة بترتيب تنازلي للقيمة. لتحقيق ذلك، نحتاج أولاً إلى إنشاء Comparator للأعداد الصحيحة:

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

لإنشاء Comparator، نقوم بتطبيق واجهة Comparator وتجاوز الدالة compare. باستخدام التعبير الشرطي o1 < o2 ? 1 : -1، سنحصل على النتيجة بترتيب تنازلي. لو استخدمنا o1 > o2 ? 1 : -1، لحصلنا على النتيجة بترتيب تصاعدي.

الآن بعد أن أصبح لدينا Comparator، نحتاج إلى إضافته إلى قائمة الانتظار ذات الأولوية. يمكننا القيام بذلك على النحو التالي:

Queue<Integer> 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

يمكننا أن نرى أن Comparator قد أدى وظيفته بشكل جيد. الآن، تُرجع قائمة الانتظار ذات الأولوية الأعداد الصحيحة بترتيب تنازلي.

استخدام قوائم الانتظار ذات الأولوية مع الكائنات المخصصة (Custom Objects)

حتى هذه النقطة، رأينا كيف يمكننا استخدام السلاسل النصية والأعداد الصحيحة مع قوائم الانتظار ذات الأولوية. في تطبيقات الحياة الواقعية، سنستخدم عادةً قوائم الانتظار ذات الأولوية مع كائنات Java المخصصة. دعنا أولاً ننشئ فئة تسمى CustomerOrder تُستخدم لتخزين تفاصيل طلبات العملاء:

 public class CustomerOrder implements Comparable < CustomerOrder > {
    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 بسيطة لتخزين طلبات العملاء. هذه الفئة تُطبق واجهة Comparable، حتى نتمكن من تحديد الأساس الذي يجب أن تُرتّب به هذه الكائنات في قائمة الانتظار ذات الأولوية. يُحدد الترتيب بواسطة الدالة compareTo في الكود أعلاه. يشير السطر o.orderId > this.orderId ? 1 : -1 إلى أن الطلبات يجب أن تُرتّب بناءً على الترتيب التنازلي لحقل orderId.

أدناه الكود الذي ينشئ قائمة انتظار ذات أولوية لكائنات 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<CustomerOrder> customerOrders = new PriorityQueue<>();
customerOrders.add(c1);
customerOrders.add(c2);
customerOrders.add(c3);

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

في الكود أعلاه، تم إنشاء ثلاثة طلبات عملاء وإضافتها إلى قائمة الانتظار ذات الأولوية. عند تشغيل هذا الكود، نحصل على المخرجات التالية:

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

كما هو متوقع، تأتي النتيجة بترتيب تنازلي لحقل orderId.

تحديد أولوية الكائنات المخصصة باستخدام Comparator خارجي

ماذا لو أردنا تحديد الأولوية بناءً على orderAmount؟ هذا سيناريو واقعي آخر. لنفترض أن كائن CustomerOrder يُعطى الأولوية افتراضيًا بواسطة orderId. ولكننا نحتاج إلى طريقة يمكننا من خلالها تحديد الأولوية بناءً على orderAmount. قد تفكر فورًا في تعديل الدالة compareTo في فئة CustomerOrder للترتيب بناءً على orderAmount. ولكن فئة CustomerOrder قد تُستخدم في أماكن متعددة في التطبيق، وقد يتعارض تعديل الدالة compareTo مباشرةً مع بقية التطبيق. الحل لهذا بسيط جدًا: يمكننا إنشاء Comparator مخصص جديد لفئة CustomerOrder واستخدامه مع قائمة الانتظار ذات الأولوية.

أدناه الكود الخاص بـ Comparator المخصص:

 static class CustomerOrderComparator implements Comparator < CustomerOrder > {
    @Override
    public int compare (CustomerOrder o1, CustomerOrder o2) {
        return o1.getOrderAmount() < o2.getOrderAmount() ? 1 : - 1 ;
    }
}

هذا مشابه جدًا لـ Comparator الأعداد الصحيحة المخصص الذي رأيناه سابقًا. يشير السطر o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; إلى أننا نحتاج إلى تحديد الأولوية بناءً على الترتيب التنازلي لـ orderAmount.

أدناه الكود الذي ينشئ قائمة الانتظار ذات الأولوية:

 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<CustomerOrder> customerOrders = new PriorityQueue<>( new CustomerOrderComparator());
customerOrders.add(c1);
customerOrders.add(c2);
customerOrders.add(c3);

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

في الكود أعلاه، نقوم بتمرير Comparator إلى قائمة الانتظار ذات الأولوية في السطر التالي من الكود:

Queue<CustomerOrder> customerOrders = new PriorityQueue<>( new CustomerOrderComparator());

إليك النتيجة عند تشغيل هذا الكود:

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

يمكننا أن نرى أن البيانات تأتي بترتيب تنازلي لـ orderAmount.

يمكن العثور على جميع الأكواد التي نوقشت في هذا المقال في مستودع GitHub هذا: PriorityQueuesInJava.

الخلاصة التقنية

تُعد قوائم الانتظار ذات الأولوية أداة قوية ومرنة في عالم هياكل البيانات، لا سيما في بيئات Java. لقد استعرضنا كيف توفر هذه القوائم حلاً فعالاً لتحديات معالجة البيانات التي تتطلب ترتيبًا قائمًا على الأولوية، متجاوزةً بذلك قيود قوائم الانتظار التقليدية ذات مبدأ FIFO. من خلال استخدام الترتيب الطبيعي الافتراضي أو تخصيص سلوك الترتيب عبر واجهتي Comparable و Comparator، يمكن للمطورين تصميم أنظمة أكثر استجابة وكفاءة. سواء كنت تتعامل مع سلاسل نصية بسيطة، أعداد صحيحة، أو كائنات معقدة، فإن فهم هذه المفاهيم يفتح آفاقًا واسعة لتحسين أداء التطبيقات وإدارة الموارد بشكل أمثل.