قائمة الانتظار هي واحدة من هياكل البيانات الرئيسية المستخدمة في البرمجة. إنها مجموعة مرتبة من العناصر ، حيث تتم إضافة عناصر جديدة إلى نهاية قائمة الانتظار وحذفها من البداية. يسمح لك هذا المنطق بإدارة العناصر الموجودة في قائمة الانتظار وفقا لمبدأ "من يأتي أولا ، يخدم أولا".
لفهم عمل قائمة الانتظار بشكل أفضل ، يمكنك رسم تشابه مع قائمة انتظار منتظمة في الحياة الواقعية. على سبيل المثال ، في متجر حيث يوجد العديد من سجلات النقد ، يقف الناس في طابور ويقتربون تدريجيا من السجل النقدي. يتم تقديم أول قادم أولا ، والباقي في قائمة الانتظار ينتظرون دورهم.
"من يأتي أولا ، يخدم أولا"
في البرمجة ، يتم استخدام قائمة انتظار لحل المهام المختلفة. على سبيل المثال ، يمكن أن يكون مفيدا عند البحث عن العرض في الرسم البياني ، عند تنفيذ خوارزميات اجتياز الشجرة ، عند نمذجة أنظمة الطابور ، والعديد من الحالات الأخرى. غالبا ما يتم استخدام قائمة الانتظار في العديد من المهام المتعلقة بمعالجة تدفقات البيانات وجدولة المهام.
- ما هي قائمة الانتظار في البرمجة وكيف تعمل?
- المفاهيم الأساسية ومبادئ العملية
- تنفيذ قائمة انتظار باستخدام بنية البيانات
- كيف يتم استخدام قائمة الانتظار في البرمجة?
- قائمة الانتظار في التطبيقات متعددة مؤشرات الترابط
- مزايا وعيوب استخدام قائمة الانتظار
- أمثلة على استخدام قائمة الانتظار في تطبيقات العالم الحقيقي
- سؤال وجواب
- ما هو طابور في البرمجة?
- كيف تعمل قائمة الانتظار في البرمجة?
- لماذا أحتاج إلى قائمة انتظار في البرمجة?
ما هي قائمة الانتظار في البرمجة وكيف تعمل?
قائمة الانتظار هي بنية بيانات خاصة تمثل قائمة مرتبة بالعناصر التي تتم فيها إضافة عناصر جديدة إلى النهاية وحذفها من بداية القائمة. في البرمجة ، يتم استخدام قائمة انتظار لتنظيم المعالجة المتسلسلة للعناصر.
قائمة الانتظار تعمل على مبدأ" يأتي أولا ، يخدم أولا " (فيفو — أولا—في-أولا-خارج). هذا يعني أن العنصر الأول المضاف إلى قائمة الانتظار سيكون أول عنصر يتم إزالته من قائمة الانتظار.
يمكن استخدام عمليات مختلفة للعمل مع قائمة الانتظار:
- قائمة الانتظار-عملية إضافة عنصر إلى نهاية قائمة الانتظار;
- ديكو-عملية إزالة عنصر من بداية قائمة الانتظار;
- نظرة خاطفة-عملية الحصول على عنصر من بداية قائمة الانتظار دون حذفه;
- إيسمبتي-عملية للتحقق مما إذا كانت قائمة الانتظار فارغة;
- الحجم هو عملية للحصول على عدد العناصر في قائمة الانتظار.
يمكن تنفيذ قائمة الانتظار بطرق مختلفة. على سبيل المثال ، باستخدام مصفوفة أو قائمة مرتبطة. يمكن تطوير خيارات قائمة الانتظار المتخصصة ، مثل قوائم الانتظار ذات الأولوية أو قوائم الانتظار ثنائية الاتجاه ، لمهام معينة.
مثال على استخدام قائمة انتظار في البرمجة يمكن أن يكون ، على سبيل المثال ، معالجة المهام في نظام التشغيل. يتم وضع المهام في قائمة الانتظار ومعالجتها بالترتيب الذي يتم استلامها به. يمكن أيضا استخدام قائمة الانتظار لحل المهام المتعلقة بالبحث أو الزحف أو معالجة البيانات.
| class Queue: | |
| def __init__(self): | self.queue = [] |
| def enqueue(self, item): | self.queue.append(item) |
| def dequeue(self): | return self.queue.pop(0) |
| def peek(self): | return self.queue[0] |
| def isEmpty(self): | return len(self.queue) == 0 |
| def size(self): | return len(self.queue) |
Основные понятия и принципы работы
قائمة الانتظار هي بنية بيانات يتم فيها إضافة العناصر إلى النهاية واسترجاعها من البداية. ينطبق مبدأ "من يأتي أولا ، يخدم أولا" في قائمة الانتظار.
المصطلحات الأساسية المتعلقة بتشغيل قائمة الانتظار:
- قائمة الانتظار هي عملية إضافة عنصر إلى نهاية قائمة الانتظار. سيتم استرداد العنصر الذي تمت إضافته أخيرا.
- ديكو هي عملية لاستخراج عنصر من بداية قائمة الانتظار. سيتم استخراج العنصر المضاف أولا أولا.
- الجبهة هي مؤشر إلى بداية قائمة الانتظار ، أي إلى العنصر الذي يجب استخراجه بعد ذلك.
- الخلفية هي مؤشر إلى نهاية قائمة الانتظار ، أي إلى العنصر الذي تمت إضافته أخيرا.
- فارغ-تحقق مما إذا كانت قائمة الانتظار فارغة. إذا كانت قائمة الانتظار فارغة ، ثم عملية ديكو غير ممكن.
يمكن تنفيذ قائمة الانتظار باستخدام مصفوفة أو قائمة مرتبطة.
عند تنفيذ قائمة انتظار على مصفوفة ، يتم إنشاء مصفوفة ثابتة أو ديناميكية ذات حجم ثابت. عند إضافة عنصر إلى نهاية قائمة الانتظار (عملية قائمة الانتظار) ، يتم إزاحة المؤشر الخلفي عنصرا واحدا إلى اليمين ، ويتم وضع العنصر في الخلية المقابلة للمصفوفة. عند استخراج عنصر من بداية قائمة الانتظار (عملية ديكو) ، يتم حذف العنصر تحت المؤشر الأمامي ويتم تحويل المؤشر الأمامي عنصر واحد إلى اليمين.
تنفيذ قائمة انتظار على قائمة مرتبطة أكثر مرونة. ويرتبط كل عنصر مع العنصر السابق واللاحقة. عند إضافة عنصر إلى نهاية قائمة الانتظار (عملية قائمة الانتظار) ، يتم إنشاء عقدة قائمة جديدة ، ويتم نقل المؤشر الخلفي إلى هذه العقدة الجديدة. عندما يتم استخراج عنصر من بداية قائمة الانتظار (عملية ديكو) ، يتم حذف العقدة الأولى من القائمة ، ويتم نقل المؤشر الأمامي إلى العقدة التالية.
يمكن استخدام تنفيذ قائمة الانتظار لحل المهام المختلفة ، على سبيل المثال ، لتنظيم معالجة الاستعلام أو جدولة المهام أو لتنظيم تبادل البيانات بين سلاسل البرامج.
تنفيذ قائمة انتظار باستخدام بنية البيانات
قائمة الانتظار هي بنية بيانات يتم فيها إضافة العناصر إلى النهاية واسترجاعها من البداية. هذا مشابه لمجموعة من الأشخاص الذين ينتظرون الخدمة في متجر: يصل العملاء الجدد إلى نهاية قائمة الانتظار ، ويتم تقديمهم من البداية.
هناك عدة طرق لتنفيذ قائمة انتظار في البرمجة. واحدة من أكثر الطرق شيوعا هي استخدام مصفوفة أو قائمة ، والتي تدعم عمليات إضافة عنصر إلى النهاية واستخراج عنصر من البداية.
لتنفيذ قائمة انتظار باستخدام مصفوفة ، تحتاج إلى إنشاء مصفوفة ذات حجم ثابت ومؤشرين-مؤشر إلى بداية قائمة الانتظار ومؤشر إلى نهاية قائمة الانتظار. عند إضافة عنصر إلى قائمة الانتظار ، يتم وضعه في نهاية المصفوفة ويتم إزاحة المؤشر إلى نهاية قائمة الانتظار إلى اليمين. عند إزالة عنصر من قائمة الانتظار ، يتم استخراجه من بداية المصفوفة ، ويتم إزاحة المؤشر إلى بداية قائمة الانتظار إلى اليمين. إذا كانت المؤشرات تلتقي ببعضها البعض ، فإن قائمة الانتظار فارغة.
يحدث تنفيذ قائمة انتظار باستخدام قائمة بطريقة مماثلة. تتم إضافة العناصر إلى القائمة على جانب واحد ، واستخراجها من جهة أخرى. للقيام بذلك ، يتم إنشاء قائمة مرتبطة بشكل مضاعف ، حيث يتم إضافة عنصر جديد إلى نهاية القائمة ، ويتم استخراج عنصر من بداية القائمة. يحتوي كل عنصر قائمة على روابط إلى العناصر السابقة والتالية. عند إضافة عنصر ، تحتاج إلى تغيير الارتباط إلى العنصر السابق من العنصر الأخير الحالي إلى الارتباط إلى العنصر الجديد.
يعتمد اختيار طريقة التنفيذ على متطلبات المشروع ولغة البرمجة. من المهم ملاحظة أن استخدام صفيف يمكن أن يسبب مشاكل في توسيع قائمة الانتظار إذا وصل الصفيف إلى الحد الأقصى لحجمه. في حين أن استخدام القائمة عادة ما يكون أكثر مرونة ، إلا أنه يمكن أن يكون أبطأ قليلا في الوصول إلى العناصر.
بغض النظر عن الطريقة المختارة ، يتيح لك تنفيذ قائمة الانتظار إدارة إضافة العناصر واستخراجها بشكل فعال ، مما يضمن عدالة وترتيب معالجة البيانات في البرنامج.
كيف يتم استخدام قائمة الانتظار في البرمجة?
قائمة الانتظار هي بنية بيانات تعمل على مبدأ" أولا في ، أولا خارج " (فيفو — أولا في ، أولا خارج). في البرمجة ، يتم استخدام قائمة انتظار لتخزين العناصر وترتيبها ، وكذلك لإجراء عمليات لإضافة العناصر وإزالتها.
يتم استخدام قائمة الانتظار في البرمجة لحل المهام المتعلقة بمعالجة العناصر بترتيب معين. فيما يلي بعض الأمثلة حيث يمكن أن تكون قائمة الانتظار مفيدة:
- قوائم انتظار الرسائل: عندما تستخدم عمليات أو سلاسل رسائل متعددة قائمة انتظار مشتركة لإرسال رسائل إلى بعضها البعض.
- معالجة المهام: عندما يكون من الضروري إكمال مجموعة من المهام بترتيب معين وتوزيع الموارد بالتساوي.
- التخزين المؤقت للبيانات: عندما تصل البيانات بمعدل غير مستقر ويجب أن تحدث المعالجة بمعدل ثابت.
للعمل مع قائمة انتظار ، يمكن استخدام طرق وخوارزميات مختلفة في البرمجة. تتمثل إحدى الطرق الأكثر شيوعا في استخدام مصفوفة أو قائمة مرتبطة لتخزين عناصر قائمة الانتظار.
تتضمن العمليات التي يمكن إجراؤها مع قائمة الانتظار ما يلي:
- إضافة عنصر إلى نهاية قائمة الانتظار (قائمة الانتظار).
- حذف عنصر من بداية قائمة الانتظار (ديكو).
- الحصول على عنصر من بداية قائمة الانتظار دون حذفه (نظرة خاطفة).
- التحقق مما إذا كانت قائمة الانتظار فارغة (إيسمبتي).
- عملية الحصول على حجم قائمة الانتظار (الحجم).
بالإضافة إلى تنفيذ قائمة الانتظار القياسية ، هناك أيضا أنواع قائمة انتظار محددة في البرمجة ، مثل قائمة انتظار الأولوية وقائمة انتظار ثنائية الاتجاه. تسمح لك قائمة انتظار الأولوية بإضافة عناصر ذات أولوية معينة ، وتوفر قائمة الانتظار ثنائية الاتجاه القدرة على إضافة العناصر وإزالتها إلى كل من بداية ونهاية قائمة الانتظار.
يمكن أن يؤدي استخدام قائمة انتظار في البرمجة إلى تبسيط وتحسين معالجة العناصر بترتيب معين ، مما يجعلها واحدة من هياكل البيانات المهمة.
قائمة الانتظار في التطبيقات متعددة مؤشرات الترابط
في التطبيقات متعددة مؤشرات الترابط ، تلعب قائمة الانتظار دورا مهما لضمان اتساق وأمن مؤشرات الترابط. يتم استخدام قائمة انتظار لنقل ومعالجة البيانات بين مؤشرات الترابط المختلفة في البرنامج.
قائمة الانتظار في تطبيقات مؤشرات الترابط يعمل على مبدأ أولا في أول من (فيفو). يتم وضع جميع العناصر في نهاية قائمة الانتظار ، وتعالجها مؤشرات الترابط واحدة تلو الأخرى ، بدءا من العنصر الأول. في التطبيقات متعددة مؤشرات الترابط ، توفر قائمة الانتظار وصولا متزامنا إلى العناصر وتمنع التعارضات المحتملة وسباقات البيانات.
عادة ما يتم تنفيذ قائمة انتظار في التطبيقات متعددة مؤشرات الترابط باستخدام هياكل البيانات مثل قائمة أو مصفوفة ذات ارتباطين. يحتوي كل عنصر في قائمة الانتظار على بعض البيانات ومؤشر إلى العنصر التالي في قائمة الانتظار. أيضا ، لضمان سلامة العمل مع قائمة الانتظار ، يتم استخدام كائنات المزامنة أو العمليات الذرية الخاصة التي تسمح للخيوط بالتفاعل بأمان مع قائمة الانتظار.
عند استخدام قائمة انتظار في التطبيقات متعددة مؤشرات الترابط ، يمكن لمؤشر ترابط الناشر وضع العناصر في قائمة الانتظار ، ويمكن لمؤشرات ترابط المشترك أخذ هذه العناصر ومعالجتها. تضمن قائمة الانتظار نقل البيانات ومعالجتها بترتيب الوصول ، وهو أمر مهم بشكل خاص عند العمل مع العمليات غير المتزامنة أو عند تبادل البيانات بين أجزاء مختلفة من البرنامج.
فيما يلي مثال على استخدام قائمة انتظار في التطبيقات متعددة مؤشرات الترابط:
- إنشاء وتهيئة قائمة انتظار.
- إنشاء مؤشر ترابط الناشر الذي سيصطف العناصر.
- إنشاء مؤشرات الترابط المشترك التي ستأخذ ومعالجة العناصر من قائمة الانتظار.
- إطلاق تدفقات المشتركين وتدفقات الناشر.
- معالجة العناصر في تدفقات المشتركين.
- وقف تيارات.
وبالتالي ، فإن قائمة الانتظار في التطبيقات متعددة مؤشرات الترابط هي أداة مريحة وآمنة لتبادل البيانات ومعالجتها بين مؤشرات الترابط المختلفة. يسمح بإدارة البيانات بكفاءة ويضمن اتساق الخيوط ، مما يمنع مشاكل المزامنة المحتملة وسباقات البيانات.
مزايا وعيوب استخدام قائمة الانتظار
المزايا:
- بنية بيانات استثنائية: توفر قائمة الانتظار تخزينا مناسبا والوصول إلى العناصر بالترتيب الذي يتم استلامها به.
- دعم فيفو: سيكون العنصر الأول الذي يصل إلى قائمة الانتظار هو الأول الذي يتم استرجاعه ، وهي ميزة مفيدة في العديد من المهام.
- تنفيذ بسيط: يمكن تنفيذ قائمة الانتظار بناء على مصفوفة أو قائمة مرتبطة ، مما يجعلها بسيطة ومرنة للاستخدام في سيناريوهات مختلفة.
- خاصية تعدد مريحة: يمكن استخدام قائمة الانتظار لتبادل البيانات بين مؤشرات الترابط ، مما يضمن الأمان والمزامنة.
- العمل الفعال مع الخوارزميات: تتيح لك قائمة الانتظار تنفيذ مجموعة واسعة من الخوارزميات ، مثل البحث عن العرض أولا ، واجتياز الرسم البياني ، وخوارزميات الجدولة ، وما إلى ذلك.
العيوب:
- حجم محدود: قد يكون لقائمة الانتظار سعة محدودة ، مما قد يؤدي إلى فقدان البيانات أو وظائف محدودة مع عدد كبير من العناصر.
- تعقيد الوقت لعمليات الإدراج والحذف: على عكس المكدس ، يجب نقل بقية العناصر في قائمة الانتظار عند حذفها من البداية ، الأمر الذي قد يتطلب موارد إضافية.
- عدم الوصول المباشر إلى العناصر: عناصر قائمة الانتظار متاحة فقط بالتتابع ، مما قد يجعل من الصعب العمل مع عناصر متوسطة أو محددة.
أمثلة على استخدام قائمة الانتظار في تطبيقات العالم الحقيقي
تستخدم قوائم الانتظار على نطاق واسع في العديد من مجالات البرمجة وتطبيقات العالم الحقيقي. فيما يلي بعض الأمثلة حيث يتم تطبيق قوائم الانتظار:
أنظمة إدارة الطلبات: تستخدم قوائم الانتظار للتحكم في تدفق الطلبات في أنظمة توصيل البيتزا أو في التجارة الإلكترونية. تتم إضافة الطلبات إلى قائمة الانتظار ومعالجتها عند وصولها ، مما يضمن التخصيص العادل للموارد وتحسين عملية معالجة الطلبات.
مهام المعالجة المتوازية: غالبا ما تستخدم قوائم الانتظار لتنظيم المهام المتوازية في الأنظمة حيث يجب أن تتعامل سلاسل عمليات أو عمليات عامل متعددة مع المهام من نفس المجموعة. على سبيل المثال ، في أنظمة معالجة الصور أو الفيديو ، يمكن إضافة كل مهمة إلى قائمة انتظار ومعالجتها بواسطة سلاسل عمليات أو عمليات عامل منفصلة.
خوادم الشبكة: يمكن استخدام قوائم الانتظار لإدارة الطلبات القادمة إلى خوادم الشبكة. يتم وضع كل طلب في قائمة الانتظار ومعالجته بالترتيب الذي يصل إليه ، مما يضمن تخصيصا عادلا للموارد ويمنع التحميل الزائد على الخادم.
التعامل مع الحدث: تستخدم قوائم الانتظار على نطاق واسع في معالجة الأحداث في أنظمة الوقت الفعلي. على سبيل المثال ، في الألعاب ، يتم استخدام قوائم الانتظار لمعالجة إجراءات اللاعب ، وفي تطبيقات الويب لمعالجة طلبات المستخدمين ، وفي أنظمة المراقبة لمعالجة الإشعارات وإرسالها.
خوارزميات التخطيط: يمكن استخدام قوائم الانتظار لتنفيذ خوارزميات جدولة مختلفة حيث يجب إكمال المهام أو العمليات بترتيب معين. على سبيل المثال ، في أنظمة التشغيل ، يمكن لجدول العمليات استخدام قوائم الانتظار لتحديد ترتيب تنفيذ العمليات بناء على أولويتها أو المهلة.
هذه ليست سوى بعض الأمثلة على استخدام قوائم الانتظار في التطبيقات الحقيقية. قائمة الانتظار هي أداة قوية يمكن استخدامها في العديد من سيناريوهات البرمجة وحل المهام المختلفة.
سؤال وجواب
ما هو طابور في البرمجة?
قائمة الانتظار في البرمجة هي بنية بيانات تسمح لك بإضافة عناصر جديدة إلى نهاية قائمة الانتظار واستلام العناصر من بداية قائمة الانتظار. قائمة الانتظار تعمل على مبدأ" من يأتي أولا ، يخدم أولا " (فيفو — أولا في ، أولا).
كيف تعمل قائمة الانتظار في البرمجة?
تعمل قائمة الانتظار في البرمجة على النحو التالي: عند إدراج عنصر جديد في قائمة الانتظار ، يتم وضعه في نهاية قائمة الانتظار. عند إزالة عنصر من قائمة الانتظار ، يتم أخذه من بداية قائمة الانتظار. وبالتالي ، يتم إضافة العناصر إلى نهاية قائمة الانتظار واسترجاعها من بداية قائمة الانتظار ، مما يضمن الامتثال لمبدأ فيفو.
لماذا أحتاج إلى قائمة انتظار في البرمجة?
يمكن استخدام قائمة انتظار في البرمجة لحل المهام المختلفة. على سبيل المثال ، غالبا ما يتم استخدامه لإدارة المهام أو الأحداث في التطبيقات متعددة مؤشرات الترابط. تسمح لك قائمة الانتظار بتبسيط معالجة المهام أو الأحداث ، مما يضمن معالجة العنصر المضاف أولا. يمكن أيضا استخدام قائمة الانتظار لتنفيذ خوارزميات لاجتياز الأشجار أو الرسوم البيانية ، وكذلك لنمذجة العمليات المختلفة حيث يكون ترتيب عناصر المعالجة مهما.