واجهة Java Queue وتطبيقاتها

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

هيكل بيانات قائمة الانتظار

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

قائمة الانتظار في جافا

قائمة الانتظار في Java هي واجهة. وفقًا لوثائق Oracle، تحتوي واجهة قائمة الانتظار على واجهتين فائقتين، و4 واجهات مختلفة ترث من قائمة الانتظار، وقائمة رائعة للغاية من الفئات. ماذا يعني ذلك؟ أولاً، تعد Java Queue جزءًا من Collection Framework وتقوم بتنفيذ واجهة Collection. لذلك فهو يدعم جميع طرق واجهة المجموعة مثل الإدراج والحذف وما إلى ذلك. تطبق قائمة الانتظار واجهة قابلة للتكرار، والتي تسمح للكائن بأن يكون هدفًا لعبارة "لكل حلقة".

طرق قائمة الانتظار جافا

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

• العرض المنطقي () - يُدرج عنصرًا جديدًا في قائمة الانتظار إذا كان ذلك ممكنًا
• إضافة منطقية (E e) - تُدرج عنصرًا جديدًا في قائمة الانتظار إذا كان ذلك ممكنًا. يُرجع صحيحًا في حالة النجاح ويطرح IllegalStateException إذا لم يكن هناك مساحة.
• استقصاء الكائن () – يقوم باسترداد وإزالة عنصر من رأس الملف. إرجاع قيمة فارغة إذا كانت قائمة الانتظار فارغة.
• إزالة الكائن () - استرداد وإزالة عنصر من رأس قائمة الانتظار.
• نظرة خاطفة على الكائن () - تسترد عنصرًا من رأس قائمة الانتظار، ولكنها لا تزيله. إرجاع قيمة فارغة إذا كانت قائمة الانتظار فارغة.
• عنصر الكائن () - يسترد عنصرًا من رأس قائمة الانتظار، لكنه لا يزيله.

الواجهات الفرعية لقائمة انتظار Java

يتم توريث واجهة قائمة الانتظار من خلال 4 واجهات فرعية - BlockingDeque<E>، BlockingQueue<E>، Deque<E>، TransferQueue<E> . يمكنك تقسيمها إلى 3 مجموعات: Deques، وBlocking Queues، وTransfer Queues مع BlockingDeque التي تنتمي إلى المجموعتين الأوليين. دعونا نلقي نظرة على هذه المجموعات.

ديك

Deque يعني D ouble- Ended Q ueue ويدعم الإضافة أو الإزالة من أي من ذيل البيانات كقائمة انتظار (first-in-first-out/FIFO) أو من الرأس كبنية بيانات شائعة أخرى تسمى المكدس ( last - in- أول خارج/LIFO). الفئات التي تطبق واجهة Deque: ArrayDeque، وConcurrentLinkedDeque، وLinkedBlockingDeque، وLinkedList.

حظر قوائم الانتظار

قائمة انتظار الحظر هي قائمة انتظار تحظر سلسلة رسائل في حالتين:

• يحاول مؤشر الترابط الحصول على عناصر من قائمة انتظار فارغة
• يحاول مؤشر الترابط وضع العناصر في قائمة الانتظار الكاملة

عندما يحاول خيط الحصول على عناصر من قائمة انتظار فارغة، فإنه ينتظر حتى يقوم خيط آخر بوضع العناصر في قائمة الانتظار. وبالمثل، عندما يحاول خيط وضع عناصر في قائمة انتظار كاملة، فإنه ينتظر حتى يقوم خيط آخر بإخراج العناصر من قائمة الانتظار للحصول على مساحة خالية للعناصر. من المؤكد أن مفهوم "قائمة الانتظار الكاملة" يعني أن قائمة الانتظار لها حجم محدود، وهو ما يتم تحديده عادةً في المُنشئ. تتضمن قوائم الحظر القياسية LinkedBlockingQueue وSynchronousQueue وArrayBlockingQueue. تنفيذ فئات واجهة BlockingQueue : ArrayBlockingQueue، DelayQueue، LinkedBlockingDeque، LinkedBlockingQueue، LinkedTransferQueue، PriorityBlockingQueue، SynchronousQueue. BlockingDeque هي واجهة فرعية لـ BlockingQueue. BlockingDeque مثل BlockingQueue عبارة عن قائمة انتظار محظورة، ولكنها ثنائية الاتجاه. لذلك فهو يرث خصائص واجهة Deque. إنه موجه نحو التنفيذ متعدد الخيوط، ولا يسمح بوجود عناصر صفرية وقد تكون السعة محدودة. تعمل تطبيقات واجهة BlockingDeque على منع عملية الحصول على العناصر إذا كانت قائمة الانتظار فارغة، وإضافة عنصر إلى قائمة الانتظار إذا كانت ممتلئة.

طوابير النقل

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

تطبيقات قائمة انتظار جافا

هناك العديد من الفئات التي تنفذ واجهة قائمة الانتظار:

• AbstractQueue وفقًا لمستندات Queue Java 8، توفر هذه الفئة المجردة تطبيقات أساسية لبعض عمليات قائمة الانتظار. لا يسمح بالعناصر الفارغة. هناك ثلاث طرق إضافية للإضافة والإزالة والعنصر بناءً على العرض الكلاسيكي لقائمة الانتظار والاستطلاع والنظرة الخاطفة على التوالي. ومع ذلك، فهم يطرحون استثناءات بدلاً من الإشارة إلى الفشل من خلال إرجاعات خاطئة أو فارغة.
• ArrayBlockingQueue - قائمة انتظار حظر FIFO ذات حجم ثابت مدعومة بمصفوفة
• ArrayDeque — تطبيق مصفوفة يمكن تغيير حجمها لواجهة Deque
• ConcurrentLinkedDeque - مجموعة متزامنة غير محدودة تعتمد على العقد المرتبطة.
• ConcurrentLinkedQueue — قائمة انتظار غير محدودة وآمنة تعتمد على العقد المرتبطة.
• DelayQueue - قائمة انتظار جدولة تعتمد على الوقت ومدعومة بكومة
• LinkedBlockingDeque — التنفيذ المتزامن لواجهة Deque.
• LinkedBlockingQueue - قائمة انتظار حظر FIFO محدودة اختياريًا ومدعومة بالعقد المرتبطة
• LinkedList — تنفيذ قائمة مرتبطة بشكل مزدوج لواجهات List وDeque. ينفذ جميع عمليات القائمة الاختيارية، ويسمح بجميع العناصر (بما في ذلك العناصر الخالية)
• LinkedTransferQueue - قائمة انتظار نقل غير محدودة تعتمد على العقد المرتبطة
• PriorityBlockingQueue - قائمة انتظار ذات أولوية حظر غير محدودة مدعومة بكومة
• PriorityQueue - قائمة انتظار ذات أولوية تعتمد على بنية بيانات الكومة
• SynchronousQueue - قائمة انتظار حظر حيث يجب أن تنتظر كل عملية إدراج عملية إزالة مقابلة بواسطة مؤشر ترابط آخر، والعكس صحيح.

التطبيقات الأكثر شيوعًا هي LinkedList وArrayBlockingQueue وPriorityQueue. دعونا نلقي نظرة عليها ونقوم ببعض الأمثلة لفهم أفضل.

قائمة مرتبطة

يقوم Class LinkedList في Java بتنفيذ واجهات List وDeque. لذلك، فهي عبارة عن مزيج من List وDeque، وهي قائمة انتظار ثنائية الاتجاه، تدعم إضافة العناصر وإزالتها من كلا الجانبين. في Java، LinkedList عبارة عن قائمة مرتبطة بشكل مزدوج: كل عنصر في القائمة يستدعي Node ويحتوي على كائن ومراجع إلى كائنين متجاورين - السابق والتالي. يمكنك القول أن LinkedList ليس فعالًا جدًا من حيث استخدام الذاكرة. هذا صحيح، ولكن بنية البيانات هذه يمكن أن تكون مفيدة في حالة أداء عمليات الإدراج والحذف. ومع ذلك، يحدث ذلك فقط إذا كنت تستخدم التكرارات لهم (في هذه الحالة يحدث في وقت ثابت). تتم عمليات الوصول بالفهرس من خلال البحث من بداية النهاية (أيهما أقرب) إلى العنصر المطلوب. ومع ذلك، لا تنس التكاليف الإضافية لتخزين المراجع بين العناصر. لذلك، LinkedList هو تطبيق قائمة الانتظار الأكثر شيوعًا في Java. إنه تطبيق لـ List و Deque أيضًا ويسمح لنا بإنشاء قائمة انتظار ثنائية الاتجاه تتكون من أي كائنات بما في ذلك العناصر الخالية. LinkedList عبارة عن مجموعة من العناصر.

منشئو القائمة المرتبطة

يتم استخدام LinkedList() بدون معلمات لإنشاء قائمة فارغة. LinkedList(Collection<? Extends E> c) مخصص لإنشاء قائمة تحتوي على عناصر المجموعة المحددة، بالترتيب، يتم إرجاعها بواسطة مكرر المجموعة.

طرق القائمة المرتبطة الرئيسية:

• add(E element) يُلحق العنصر المحدد بنهاية هذه القائمة؛
• add(int Index, E element) يُدخل العنصر في فهرس الموضع المحدد؛
• get(int Index) يُرجع العنصر إلى الموضع المحدد في هذه القائمة؛
• إزالة (int Index) إزالة العنصر الموجود في فهرس الموضع؛
• إزالة (Object o) يزيل التواجد الأول للعنصر ?o من هذه القائمة إذا كان موجودًا.
• Remove() يسترد ويزيل العنصر الأول من القائمة.
• addFirst() وaddLast() تضيف عنصرًا إلى بداية/نهاية القائمة
• Clear () يزيل جميع العناصر من القائمة
• يحتوي على (Object o) يُرجع صحيحًا إذا كانت القائمة تحتوي على العنصر o.
• يقوم مؤشر IndexOf(Object o) بإرجاع فهرس التواجد الأول للعنصر o، أو -1 إذا لم يكن موجودًا في القائمة.
• set(int Index, E element) يستبدل العنصر الموجود في موضع الفهرس بالعنصر
• size() يُرجع كمية العناصر الموجودة في القائمة.
• تُرجع الدالة toArray()‎ مصفوفة تحتوي على جميع عناصر القائمة من العنصر الأول إلى العنصر الأخير.
• pop() الذي ينبثق عنصرًا من المكدس (ممثلًا بالقائمة)
• Push(E e) الذي يدفع عنصرًا إلى المكدس (ممثلًا بهذه القائمة)

مثال لقائمة انتظار Java - LinkedList (وضع العناصر وإزالتها بطرق مختلفة)

import java.util.*;

public class LinkedListTest {

       public static void main(String args[]){

           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

طابور الأولوية

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

طرق قائمة الأولوية الرئيسية:

• تقوم الإضافة المنطقية (الكائن) بإدراج العنصر المحدد في قائمة انتظار الأولوية. يعود صحيحا في حالة النجاح. إذا كانت قائمة الانتظار ممتلئة، فستطرح الطريقة استثناءً.
• يقوم العرض المنطقي (الكائن) بإدراج العنصر المحدد في قائمة انتظار الأولوية هذه. إذا كانت قائمة الانتظار ممتلئة، فسترجع الطريقة خطأ.
• إزالة منطقية (كائن) تزيل مثيلًا واحدًا للعنصر المحدد من قائمة الانتظار هذه، إذا كان موجودًا.
• يقوم Object poll() باسترداد وإزالة رأس قائمة الانتظار هذه. إرجاع قيمة فارغة إذا كانت قائمة الانتظار فارغة.
• يزيل void Clear() كافة العناصر من قائمة انتظار الأولوية.
• يسترد Object element() رأس قائمة الانتظار هذه دون إزالته. يرمي NoSuchElementException إذا كانت قائمة الانتظار فارغة.
• يسترد Object peek() رأس قائمة الانتظار دون إزالته. إرجاع قيمة فارغة إذا كانت قائمة الانتظار فارغة.
• تحتوي القيمة المنطقية على (Object o) على إرجاع صحيح إذا كانت قائمة الانتظار تحتوي على العنصر o.
• int size() يُرجع عدد العناصر في قائمة الانتظار هذه.

مثال على قائمة انتظار الأولوية

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
   public static void main(String[] args) {

       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();

       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }

       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval):
1
2
3
4
5

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

ArrayBlockingQueue

تعتمد بنية البيانات الداخلية لـ ArrayBlockingQueue على مصفوفة دائرية لتخزين العناصر. إنها قائمة انتظار نموذجية (FIFO) في حالة إدراج عناصر جديدة في ذيل قائمة الانتظار، وتقوم عمليات الاستخراج بإرجاع عنصر من رأس قائمة الانتظار. وبمجرد إنشاء سعة قائمة الانتظار، لا يمكن تغييرها. تؤدي محاولات إدراج (وضع) عنصر في قائمة انتظار كاملة إلى عرقلة التدفق؛ محاولة أخذ عنصر من قائمة انتظار فارغة تؤدي أيضًا إلى حظر الخيط. كما قلنا من قبل، هذه المصفوفة دائرية. وهذا يعني أنه يتم التعامل مع العنصرين الأول والأخير من المصفوفة بشكل منطقي. تعمل قائمة الانتظار على تحسين مؤشرات عناصر الرأس والذيل في كل مرة تقوم فيها بوضع العنصر في قائمة الانتظار أو إزالته من قائمة الانتظار. إذا قام بعض الفهرس بتقديم العنصر الأخير في المصفوفة، فسيتم إعادة تشغيله من 0. ومن ثم، لا يتعين على قائمة الانتظار تغيير جميع العناصر في حالة إزالة الرأس (كما هو الحال في المصفوفة المعتادة). ومع ذلك، في حالة إزالة عنصر من الوسط (باستخدام Iterator.remove)، يتم إزاحة العناصر. يدعم ArrayBlockingQueue سياسة عدالة إضافية ذات معلمة عادلة في المنشئ لترتيب عمل التدفقات المنتظرة للمنتجين (إدراج العناصر) والمستهلكين (استخراج العناصر). بشكل افتراضي، لا يتم ضمان الطلب. ومع ذلك، إذا تم إنشاء قائمة الانتظار باستخدام "fair == true"، فإن تطبيق فئة ArrayBlockingQueue يوفر الوصول إلى مؤشر الترابط بترتيب FIFO. عادةً ما تقلل الأسهم من عرض النطاق الترددي، ولكنها تقلل أيضًا من التقلبات وتمنع نفاد الموارد.

ArrayBlockingQueue فئة المنشئين

• يقوم ArrayBlockingQueue (سعة int) بإنشاء قائمة انتظار ذات سعة ثابتة وبسياسة وصول افتراضية.
• يقوم ArrayBlockingQueue (سعة int، معرض منطقي) بإنشاء قائمة انتظار ذات سعة ثابتة وسياسة وصول محددة.
• تقوم ArrayBlockingQueue (سعة int، boolean fair، Collection <? Extends E> c) بإنشاء قائمة انتظار ذات سعة ثابتة تحددها سياسة الوصول وتتضمن عناصر في قائمة الانتظار.

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

import java.util.concurrent.*;

public class ArrayBlockingQueueExample {

   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};

       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }

       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

الإخراج هو قائمة الانتظار بالترتيب الطبيعي؛ يظهر العنصران الأولان مع تأخير. لتعزيز ما تعلمته، نقترح عليك مشاهدة درس فيديو من دورة Java الخاصة بنا

يتم استخدام قائمة الانتظار لإدراج العناصر في نهاية قائمة الانتظار وإزالتها من بداية قائمة الانتظار. إنه يتبع مفهوم FIFO.

تعد Java Queue جزءًا من Collection Framework وتقوم بتنفيذ واجهة Collection. لذلك فهو يدعم جميع طرق واجهة المجموعة مثل الإدراج والحذف وما إلى ذلك.

تطبيقات قائمة الانتظار الأكثر استخدامًا هي LinkedList وArrayBlockingQueue وPriorityQueue.

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

إذا تم تنفيذ أي عملية فارغة على BlockingQueues، فسيتم طرح NullPointerException.