المحتوى

• رسم بياني للمقارنة
• تعريف المكدس
• مثال
• تعريف قائمة الانتظار
• مثال
• تنفيذ المكدس
• قائمة انتظار التنفيذ
• العمليات على المكدس
• العمليات على قائمة الانتظار
• تطبيقات المكدس
• تطبيقات قائمة الانتظار
• خاتمة

كومة و قائمة الانتظار كلاهما بنيات البيانات غير البدائية. الاختلافات الرئيسية بين المكدس وقائمة الانتظار هي أن المكدس يستخدم أسلوب LIFO (الأخير في أول الخروج) للوصول إلى عناصر البيانات وإضافتها ، بينما تستخدم قائمة الانتظار أسلوب FIFO (الأول في الخروج أولاً) للوصول إلى عناصر البيانات وإضافتها.

يحتوي Stack على طرف واحد مفتوح فقط لدفع عناصر البيانات وظهورها على الجانب الآخر. تحتوي قائمة الانتظار على كلا الطرفين مفتوحًا لتحديد عناصر البيانات وإلغاء تحديدها.

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

1. رسم بياني للمقارنة
2. تعريف
3. الاختلافات الرئيسية
4. التنفيذ
5. عمليات
6. تطبيقات
7. خاتمة

رسم بياني للمقارنة

أساس للمقارنة	كومة	طابور
مبدأ العمل	LIFO (الأخير في الأول خارج)	FIFO (الأول في الأول خارج)
بناء	يتم استخدام نفس الغاية لإدراج وحذف العناصر.	يتم استخدام نهاية واحدة للإدخال ، أي النهاية الخلفية ويتم استخدام نهاية أخرى لحذف العناصر ، أي الواجهة الأمامية.
عدد المؤشرات المستخدمة	واحد	اثنان (في حالة قائمة الانتظار البسيطة)
العمليات المنجزة	دفع والبوب	Enqueue و dequeue
فحص حالة فارغة	أعلى == -1	الجبهة == -1 | الجبهة == الخلفي + 1
فحص الحالة الكاملة	أعلى == ماكس - 1	الخلفي == ماكس - 1
المتغيرات	ليس لديها المتغيرات.	لديها متغيرات مثل قائمة الانتظار الدائرية ، قائمة انتظار الأولوية ، قائمة انتظار مزدوجة.
التنفيذ	بساطة	معقدة نسبيا

تعريف المكدس

المكدس هو بنية بيانات خطية غير بدائية. إنها قائمة مرتبة حيث يتم إضافة العنصر الجديد ويتم حذف العنصر الموجود من طرف واحد فقط ، يُسمى أعلى المكدس (TOS). نظرًا لأن جميع عمليات الحذف والإدراج في الرصة تتم من أعلى الرصة ، فإن العنصر الأخير الذي تم إضافته سيكون الأول الذي تتم إزالته من الرصة. هذا هو السبب في أن المكدس يسمى Last-in-First-out (LIFO) نوع القائمة.

لاحظ أن العنصر الذي يتم الوصول إليه غالبًا في الرصة هو العنصر الأعلى ، في حين أن آخر عنصر متاح موجود في أسفل الرصة.

مثال

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

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

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

مثال

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

1. تتبع المكدس آلية LIFO من ناحية أخرى تتبع قائمة الانتظار آلية FIFO لإضافة عناصر وإزالتها.
2. في المكدس ، يتم استخدام نفس النهاية لإدراج وحذف العناصر. على العكس ، يتم استخدام نهايتين مختلفتين في قائمة الانتظار لإدراج العناصر وحذفها.
3. نظرًا لأن Stack لها طرف واحد مفتوح هو سبب استخدام مؤشر واحد فقط للإشارة إلى الجزء العلوي من المكدس. لكن قائمة الانتظار تستخدم مؤشرين للإشارة إلى الأمام والنهاية الخلفية لقائمة الانتظار.
4. يقوم Stack بتنفيذ عمليتين تعرفان باسم push و pop في قائمة الانتظار المعروفة باسم enqueue و dequeue.
5. تنفيذ المكدس أسهل بينما تطبيق قائمة الانتظار صعبة.
6. تحتوي قائمة الانتظار على متغيرات مثل قائمة الانتظار الدائرية ، قائمة انتظار الأولوية ، قائمة انتظار ذات مضاعفة ، وما إلى ذلك.

تنفيذ المكدس

يمكن تطبيق المكدس بطريقتين:

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

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

يمكن تنفيذ قائمة الانتظار بطريقتين:

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

العمليات على المكدس

العمليات الأساسية التي يمكن تشغيلها على المكدس هي كما يلي:

1. إدفع: عندما يتم إضافة عنصر جديد إلى الجزء العلوي من المكدس يعرف باسم عملية الدفع. يؤدي دفع عنصر في الحزمة إلى استدعاء إضافة العنصر ، حيث سيتم إدراج العنصر الجديد في الأعلى. بعد كل عملية دفع ، يتم زيادة الجزء العلوي بواحد. إذا كان الصفيف ممتلئًا ، ولا يمكن إضافة أي عنصر جديد ، فسيتم استدعاؤه باسم STACK-FULL condition أو STACK OVERFLOW. دفع العملية - وظيفة في C:
   النظر في كومة كما أعلن
   تكدس int ، أعلى = -1 ؛
دفع باطل ()
{
البند كثافة العمليات ؛
إذا (أعلى من 4)
{
f ("أدخل الرقم") ؛
المسح الضوئي ("٪ d" ، & العنصر) ؛
top = top + 1؛
كومة = البند ؛
}
آخر
{
f ("المكدس ممتلئ") ؛
}
}
2. POP: عندما يتم حذف عنصر من أعلى الحزمة ، يُعرف باسم عملية POP. يتم تقليل المكدس بمقدار واحد ، بعد كل عملية منبثقة. إذا لم يتبق عنصر على المكدس وتم تنفيذ البوب ​​، فسيؤدي ذلك إلى حالة STACK UNDERFLOW مما يعني أن مجموعتك فارغة. تشغيل POP - وظائف في C:
   النظر في كومة كما أعلن
   تكدس int ، أعلى = -1 ؛
البوب ​​باطل ()
{
البند كثافة العمليات ؛
إذا (أعلى> = 4)
{
البند = المكدس.
أعلى = أعلى - 1 ؛
f ("الرقم المحذوف هو =٪ d" ، عنصر) ؛
}
آخر
{
f ("المكدس فارغ") ؛
}
}

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

العمليات الأساسية التي يمكن تنفيذها في قائمة الانتظار هي:

1. إدراج بقائمة الانتظار: لإدراج عنصر في قائمة انتظار. وظيفة التشغيل في C:
   تم إعلان قائمة الانتظار كـ
   قائمة انتظار int ، الجبهة = -1 والخلفية = -1 ؛
إضافة باطلة ()
{
البند كثافة العمليات ؛
إذا (الخلفية <4)
{
f ("أدخل الرقم") ؛
المسح الضوئي ("٪ d" ، & العنصر) ؛
إذا (الجبهة == -1)
{
الجبهة = 0 ؛
الخلفي = 0 ؛
}
آخر
{
الخلفي = الخلفي + 1.
}
قائمة انتظار = عنصر ؛
}
آخر
{
f ("قائمة الانتظار ممتلئة") ؛
}
}

2. Dequeue: لحذف عنصر من قائمة الانتظار. وظيفة التشغيل في C:
   تم إعلان قائمة الانتظار كـ
   قائمة انتظار int ، الجبهة = -1 والخلفية = -1 ؛
حذف الفراغ ()
{
البند كثافة العمليات ؛
إذا (الجبهة! = -1)
{
البند = قائمة الانتظار ؛
إذا (الجبهة == الخلفية)
{
الجبهة = -1 ؛
الخلفي = -1 ؛
}
آخر
{
الجبهة = الجبهة + 1 ؛
f ("الرقم المحذوف هو =٪ d" ، عنصر) ؛
}
}
آخر
{
f ("قائمة الانتظار فارغة") ؛
}
}

تطبيقات المكدس

• تحليل في مترجم.
• آلة جافا الافتراضية.
• التراجع في معالج النصوص.
• زر العودة في متصفح الويب.
• لغة بوستسكريبت ل ers.
• تنفيذ استدعاءات الوظائف في برنامج التحويل البرمجي.

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

• مخازن البيانات
• نقل البيانات غير المتزامن (ملف IO ، أنابيب ، مآخذ).
• تخصيص الطلبات على مورد مشترك (إيه ، معالج).
• تحليل حركة المرور.
• تحديد عدد من الصرافين لديك في سوبر ماركت.

خاتمة

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