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