ما هي قائمة الانتظار Queue؟
قائمة الانتظار هي هيكلة بيانات خطية تتبع ترتيبًا معينًا يتم تنفيذ العمليات به، ويتبع الترتيب مبدأ (FIFO) أي (First In First Out)، وتعني أن العناصر التي تم إدراجها في قائمة الانتظار في البداية ستظهر أولاً، والعناصر التي تم إدراجها في قائمة الانتظار مؤخراً ستظهر أخيرًا، من الأمثلة الواقعية الجيدة على قائمة الانتظار هي قائمة انتظار المستهلكين لمورد ما حيث يتم تقديم المستهلك الذي جاء أولاً أولاً.
ويتم استخدام قائمة الانتظار عندما لا يلزم معالجة الأشياء على الفور، ولكن يجب معالجتها بترتيب “العنصر المُدخل أولا يعالج أولاً” كما في خوارزمية البحث بالعرض أولاً (BFS)، هذه الخاصية لقائمة الانتظار مفيدة أيضًا في النوع التالي من السيناريوهات:
- عندما يتم مشاركة مورد بين عدة مستهلكين، تتضمن الأمثلة جدولة وحدة المعالجة المركزية وجدولة القرص الصلب.
- عند نقل البيانات بشكل غير متزامن (لا يتم استلام البيانات بالضرورة بنفس معدل إرسالها) بين عمليتين، تتضمن الأمثلة مخازن الإدخال والإخراج، والأنابيب، وملفات (IO)، إلخ.
أنواع قوائم الانتظار في هياكل البيانات:
هناك خمسة أنواع مختلفة من قوائم الانتظار المستخدمة في سيناريوهات مختلفة، وهم:
قائمة الانتظار الدائرية:
وهي عبارة عن بنية بيانات خطية يتم فيها تنفيذ العمليات بناءً على مبدأ العناصر التي يتم وضعها أولاً تتم معالجتها أولاً، ويتم توصيل الموضع الأخير بالموضع الأول لإنشاء دائرة، وتسمى قائمة الانتظار هذه أيضًا بـ “Ring Buffer”، ويتم استخدام قائمة الانتظار هذه بشكل أساسي في الحالات التالية:
- إدارة الذاكرة: يمكن برمجة مواقع الذاكرة غير المستخدمة باستخدام نوع قوائم الانتظار الدائرية.
- نظام المرور: في نظام المرور المتحكم فيه بواسطة الكمبيوتر، يتم استخدام قوائم الانتظار الدائرية لتشغيل إشارات المرور واحدة تلو الأخرى بشكل متكرر حسب الوقت المحدد.
- جدولة وحدة المعالجة المركزية: غالبًا ما تحتفظ أنظمة التشغيل بقائمة انتظار من العمليات الجاهزة للتنفيذ أو التي تنتظر حدوث حدث معين.
قائمة الانتظار مقيدة الإدخال:
في هذا النوع من قائمة الانتظار، يمكن أخذ الإدخال من جانب واحد فقط (الجانب الخلفي)، ويمكن حذف العنصر من كلا الجانبين (الجانب الأمامي والخلفي)، ولا يتبع هذا النوع من قائمة الانتظار مبدأ (FIFO).
يتم استخدام قائمة الانتظار هذه في الحالات التي يجب أن يكون فيها استهلاك البيانات بترتيب (FIFO)، ولكن إذا كانت هناك حاجة لإزالة البيانات التي تم إدراجها مؤخرًا لبعض الأسباب، ويمكن أن تكون إحدى هذه الأسباب أن البيانات غير ذات صلة أو مشكلة في الأداء وما إلى ذلك.
قائمة الانتظار مقيد الإخراج:
في هذا النوع من قائمة الانتظار، يمكن أخذ الإدخال من كلا الجانبين (الخلفي والأمامي)، ويمكن حذف العنصر من جانب واحد فقط (الجانب الأمامي)، ويتم استخدام قائمة الانتظار هذه في الحالة التي يكون فيها للمدخلات بعض الأولوية ليتم تنفيذها، ويمكن وضع المدخلات في أول قائمة الانتظار بحيث يتم تنفيذها أولاً.
قائمة الانتظار مزدوجة النهاية:
قائمة الانتظار مزدوجة النهاية المعروفة بـ (Deque) اختصاراً لـ (double-ended queue)، هي أيضًا نوع أخر من أنواع هياكل البيانات قائمة الانتظار حيث يتم تنفيذ عمليات الإدراج والحذف في كلا الطرفين (الأمامي والخلفي)، هذا يعني أنه يمكننا الإدراج في كل من المواضع الأمامية والخلفية ويمكننا الحذف من كل من المواضع الأمامية والخلفية.
نظرًا لأن قائمة الانتظار مزدوجة النهاية تدعم كلاً من عمليات المكدس وقائمة الانتظار، فيمكن استخدامه على حد سواء، وتدعم بنية بيانات قائمة الانتظار مزدوجة النهاية الدوران في اتجاه عقارب الساعة وعكس اتجاه عقارب الساعة بتعقيد وقت مقداره “O(1)” والذي يمكن أن يكون مفيدًا في تطبيقات معينة، أيضًا، يمكن حل المشكلات التي تحتاج إلى إزالة العناصر أو إضافة كلا الطرفين بكفاءة باستخدام قائمة الانتظار المزدوجة.
قائمة الانتظار ذات الأولوية:
قائمة انتظار ذات الأولوية هي نوع خاص من قائمة الانتظار حيث يرتبط كل عنصر بأولوية ويتم تقديمه وفقًا لأولويته، ويتم استخدام قائمة الانتظار ذات الأولوية بشكل أساسي لتنفيذ خوارزميات جدولة وحدة المعالجة المركزية، وهناك نوعان من قوائم انتظار ذات الأولوية، هم:
- قائمة انتظار ذات الأولوية التصاعدية: يمكن إدراج العنصر بشكل عشوائي، لكن يمكن إزالة أصغر عنصر فقط، على سبيل المثال افترض أن هناك مصفوفة تحتوي على العناصر (4، 2، 8) بنفس الترتيب. بالتالي عند إدخال العناصر لقائمة انتظار الأولوية سيكون الإدخال بنفس التسلسل، ولكن سيكون الترتيب أثناء الحذف (2، 4، 8).
- قائمة انتظار ذات الأولوية التنازلية: يمكن إدراج العنصر بشكل عشوائي، لكن يمكن إزالة العنصر الأكبر فقط أولاً، على سبيل المثال، افترض أن هناك مصفوفة تحتوي على العناصر (4، 2، 8) بنفس الترتيب، بالتالي عند إدخال العناصر لقائمة انتظار الأولوية سيكون الإدخال بنفس التسلسل، ولكن أثناء الحذف سيكون الترتيب (8، 4، 2).
