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

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

تابع القراءة لفهم قوائم الانتظار وقوائم الانتظار ذات الأولوية.

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

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

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

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

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

ما هي أولوية قائمة الانتظار؟

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

متعلق ب: الخوارزميات يجب أن يعرفها كل مبرمج

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

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

تحتوي قائمة انتظار الأولوية أيضًا على مجموعة متنوعة من التطبيقات الأساسية. تعد قوائم انتظار الأولوية ضرورية في خوارزميات الرسم البياني مثل Prim’s Minimum Spanning Tree و Dijkstra's Shortest Path algorithm. كما أنها مثالية في خوارزميات جدولة وحدة معالجة الكمبيوتر (CPU).

تعلم هياكل البيانات

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

تعتبر هياكل البيانات الأخرى مثل الأكوام والمكدسات والأشجار مهمة بنفس القدر للطلاب والمهنيين. من الشائع أيضًا أن يقوم القائمون بالمقابلات باستجواب المتقدمين بشأن هياكل البيانات.

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

أكوام مقابل. الأكوام: ما الذي يميزهم عن غيرهم؟

لقد سمعت عن Heaps and Stacks ، ولكن متى يجب استخدام أحدهما على الآخر؟

اقرأ التالي

نبذة عن الكاتب