مقدمة
قائمة الانتظار هي مجموعة من العناصر ، حيث يجب أن يكون العنصر الأول المضاف إلى القائمة هو العنصر الأول الذي يجب إزالته بعد ذلك. لذلك كلما تمت إضافة العناصر إلى المجموعة ، يزداد حجمها ، أي أنها تنمو في الطول. عندما تتم إزالة أي عنصر ، يجب أن يكون أول عنصر مضاف. إذا تمت إزالة العناصر بشكل مستمر ، فإن العنصر التالي الذي تمت إزالته هو العنصر الثاني ؛ تتم إزالة الثالث بعد ذلك ، وهكذا.
بعد إزالة العنصر الأول من القائمة الأصلية ، يصبح العنصر الثاني هو العنصر الأول. بعد إزالة العنصر الثاني ، يصبح العنصر الثالث هو العنصر الأول ، وهكذا.
من الأمثلة الواقعية الجيدة لقائمة الانتظار عندما يصطف الناس لانتظار الخدمة أو الخير. يتم تقديم الشخص الأول أولاً قبل الأخير. ومع ذلك ، فإن قائمة الانتظار التي تحدثنا عنها في هذا البرنامج التعليمي ، هي قائمة انتظار البرامج ، كما تم تصميمها في C ++.
FIFO
يرمز FIFO إلى First-In ، First-Out. إنها طريقة أخرى لتقدير قائمة الانتظار. هذا يعني أن العنصر الأول الذي يدخل القائمة ، هو العنصر الأول الذي يجب إزالته ، عندما تتم الإزالة. بداية القائمة تسمى الرأس أو الجبهة ؛ نهاية القائمة تسمى الظهر أو الذيل.
العمليات الأساسية
يجب أن تحتوي قائمة انتظار البرامج على العمليات التالية على الأقل:
يدفع
تضيف هذه العملية عنصرًا جديدًا في الجزء الخلفي من قائمة الانتظار. تسمى هذه العملية رسميًا ، قائمة الانتظار.
تحول
تزيل هذه العملية العنصر الأول من قائمة الانتظار ، ويصبح العنصر الثاني هو العنصر الأول الجديد. تسمى هذه العملية رسميًا dequeue. يطلق عليه pop في C ++.
يشرح هذا المقال كيفية استخدام بنية بيانات قائمة انتظار C ++. يجب أن تعرف مؤشرات ومراجع C ++ لفهم بقية هذه المقالة.
فئة وكائنات
الفئة عبارة عن مجموعة من المتغيرات والوظائف التي تعمل معًا ، حيث لا تحتوي المتغيرات على قيم معينة. عندما يتم تعيين القيم للمتغيرات ، تصبح الفئة كائنًا. القيم المختلفة المعطاة لنفس الفئة تؤدي إلى كائنات مختلفة ؛ أي أن الكائنات المختلفة هي نفس الفئة بقيم مختلفة. يُقال إن إنشاء كائن من فئة ما يؤدي إلى إنشاء الكائن.
الاسم ، قائمة الانتظار ، هو فئة. كائن تم إنشاؤه من فئة قائمة الانتظار له اسم مبرمج تم اختياره.
هناك حاجة إلى وظيفة تنتمي إلى فئة لإنشاء مثيل لكائن من الفئة. في C ++ ، هذه الوظيفة لها نفس اسم اسم الفئة. الكائنات التي تم إنشاؤها (تم إنشاء مثيل لها) من الفصل لها أسماء مختلفة تم إعطاؤها لها من قبل المبرمج.
إنشاء كائن من الفصل يعني بناء الكائن ؛ هذا يعني أيضًا إنشاء مثيل.
يبدأ برنامج C ++ الذي يستخدم فئة queue بالأسطر التالية في أعلى الملف:
#يشمل#يشمل
استخدام اسم للمحطة؛
السطر الأول للإدخال / الإخراج. السطر الثاني هو السماح للبرنامج باستخدام جميع ميزات فئة قائمة الانتظار. يسمح السطر الثالث للبرنامج باستخدام الأسماء في مساحة الاسم القياسية.
زيادة التحميل على وظيفة
عندما يكون لتوقيعين مختلفين أو أكثر نفس الاسم ، يُقال أن هذا الاسم محمّل بشكل زائد. عندما يتم استدعاء دالة واحدة ، رقم ونوع الوسيطات ، حدد الوظيفة التي يتم تنفيذها بالفعل.
بناء
طابور<نوع>اسم()يقوم الإعلان التالي بإنشاء مثيل لقائمة انتظار مسماة ، قائمة انتظار من النوع int.
طابور<int>الذي - التي؛قائمة الانتظار فارغة. يبدأ الإعلان بالكلمة المحجوزة ، قائمة الانتظار متبوعة بأقواس زاوية بنوع البيانات. ثم لديك اسم معين للمبرمج لقائمة الانتظار.
الإنشاء باستخدام قائمة المُهيئ
يوضح التعريف التالي كيفية إنشاء قائمة انتظار مع قائمة التهيئة:
طابور<تطفو>الذي - التي({1.1و 2.2و 3.3و 4.4})؛تدمير طابور
لتدمير قائمة انتظار ، فقط اتركها تخرج عن النطاق.
الوصول إلى عنصر قائمة الانتظار
دفع (القيمة)
قائمة الانتظار هي قائمة First-In-First-Out. لذلك ، يتم إضافة كل قيمة من الخلف. يُنشئ مقطع التعليمات البرمجية التالي قائمة انتظار فارغة ، يتم بعدها إضافة خمس قيم عائمة من الخلف:
طابور<تطفو>الذي - التي؛الذي - التي.يدفع(1.1)؛
الذي - التي.يدفع(2.2)؛
الذي - التي.يدفع(3.3)؛
الذي - التي.يدفع(4.4)؛
الذي - التي.يدفع(5.5)؛
الحجم ()
يؤدي هذا إلى إرجاع عدد العناصر في قائمة الانتظار. يوضح الكود التالي:
طابور<تطفو>الذي - التي؛الذي - التي.يدفع(1.1)؛الذي - التي.يدفع(2.2)؛الذي - التي.يدفع(3.3)؛الذي - التي.يدفع(4.4)؛الذي - التي.يدفع(5.5)؛
كلفة<<الذي - التي.بحجم() << 'ن'؛
الخرج هو 5.
أمام()
يؤدي هذا إلى إرجاع مرجع إلى العنصر الأول في قائمة الانتظار ، دون إزالة العنصر. ناتج الكود التالي هو 1.1.
طابور<تطفو>الذي - التي؛الذي - التي.يدفع(1.1)؛الذي - التي.يدفع(2.2)؛الذي - التي.يدفع(3.3)؛الذي - التي.يدفع(4.4)؛الذي - التي.يدفع(5.5)؛
كلفة<<الذي - التي.أمام() << 'ن'؛
لا يتم إزالة العنصر من قائمة الانتظار.
الجبهة () const
عندما يسبق إنشاء قائمة الانتظار بـ const ، يتم تنفيذ التعبير front () const بدلاً من front (). يتم استخدامه في الكود التالي ، على سبيل المثال.
مقدار ثابتطابور<تطفو>الذي - التي({1.1و 2.2و 3.3و 4.4و 5.5})؛كلفة<<الذي - التي.أمام() << 'ن'؛
يتم إرجاع مرجع ثابت. لا يتم إزالة العنصر من المتجه. لا يمكن تغيير عناصر قائمة الانتظار.
الى الخلف()
يؤدي هذا إلى إرجاع مرجع إلى العنصر الأخير في قائمة الانتظار ، دون إزالة العنصر. إخراج الكود التالي هو 5.5.
طابور<تطفو>الذي - التي؛الذي - التي.يدفع(1.1)؛الذي - التي.يدفع(2.2)؛الذي - التي.يدفع(3.3)؛الذي - التي.يدفع(4.4)؛الذي - التي.يدفع(5.5)؛
كلفة<<الذي - التي.الى الخلف() << 'ن'؛
رجوع () const
عندما يسبق إنشاء قائمة الانتظار بـ const ، يتم تنفيذ التعبير back () const بدلاً من back (). يتم استخدامه في الكود التالي ، على سبيل المثال.
مقدار ثابتطابور<تطفو>الذي - التي({1.1و 2.2و 3.3و 4.4و 5.5})؛كلفة<<الذي - التي.الى الخلف() << 'ن'؛
يتم إرجاع مرجع ثابت. لا يتم إزالة العنصر من قائمة الانتظار. مع الثابت السابق لبناء قائمة الانتظار ، لا يمكن تغيير العناصر الموجودة في قائمة الانتظار.
سعة قائمة الانتظار
الحجم ()
- أنظر فوق
فارغ () const
يؤدي هذا إلى إرجاع 1 لصحيح إذا لم تكن هناك عناصر في قائمة الانتظار ، أو 0 للخطأ إذا كانت قائمة الانتظار فارغة. يوضح الكود التالي هذا:
طابور<تطفو>هذا 1({1.1و 2.2و 3.3و 4.4و 5.5})؛كلفة<<هذا 1.فارغة() << 'ن'؛
طابور<تطفو>هذا 2؛
كلفة<<هذا 2.فارغة() << 'ن'؛
الخرج هو:
01
معدِّلات قائمة الانتظار
البوب ()
قائمة الانتظار هي FIFO ، لذا يجب إزالة أي عنصر يجب إزالته من أعلى (رأس) قائمة الانتظار. تقوم وظيفة العضو هذه بإزالة العنصر الأول دون إعادته. يوضح الكود التالي هذا:
طابور<تطفو>الذي - التي({1.1و 2.2و 3.3و 4.4و 5.5})؛كلفة<<الذي - التي.أمام() << 'ن'؛
الذي - التي.البوب()؛
كلفة<<الذي - التي.بحجم() << 'ن'؛
الخرج هو:
1.14
أ. swap (ب)
يمكن تبديل قائمتين من قوائم الانتظار ، كما هو موضح في مقطع الكود هذا:
طابور<تطفو>هذا 1({1.1و 2.2و 3.3و 4.4و 5.5})؛طابور<تطفو>هذا 2({10و عشرين})؛
هذا 1.مبادلة، مقايضة(هذا 2)؛
كلفة<< العنصر الأول وحجم que1:
'<<هذا 1.أمام() <<'،'<<هذا 1.بحجم() << 'ن'؛
كلفة<< العنصر الأول وحجم que2<<
هذا 2.أمام() <<'،'<<هذا 2.بحجم() << 'ن'؛
الخرج هو:
العنصر الأول وحجم que1: 10 ، 2
العنصر الأول وحجم que2: 1.1 ، 5
لاحظ أنه يتم زيادة طول قائمة الانتظار إذا لزم الأمر. أيضًا ، يتم استبدال القيم التي لا تحتوي على بدائل ببعض القيم الافتراضية. يجب أن تكون أنواع البيانات من نفس النوع.
عوامل المساواة والعلائقية لقوائم الانتظار
بالنسبة للأحرف العادية في C ++ ، بترتيب تصاعدي ، تأتي الأرقام قبل الأحرف الكبيرة ، والتي تأتي قبل الأحرف الصغيرة. تأتي شخصية الفضاء قبل الصفر وكلها.
عوامل المساواة
إرجاع 1 لصحيح و 0 للخطأ.
عامل التشغيل ==
تُرجع 1 إذا كان لقائمتا الانتظار نفس الحجم والعناصر المقابلة لها متساوية ؛ وإلا فإنها ترجع 0. مثال:
طابور<مقدار ثابت شار*>هذا 1({'طيب القلب'و 'شيء آخر'})؛طابور<مقدار ثابت شار*>هذا 2({'شريرة'})؛
intعلى واحد=هذا 1==هذا 2؛
كلفة<<على واحد<< 'ن'؛
الخرج هو: 0.
عامل التشغيل! =
- عكس ما سبق. مثال:
طابور<مقدار ثابت شار*>هذا 1({'طيب القلب'و 'شيء آخر'})؛طابور<مقدار ثابت شار*>هذا 2({'شريرة'})؛
intعلى واحد=هذا 1! =هذا 2؛
كلفة<<على واحد<< 'ن'؛
الخرج هو: 1.
العوامل العلاقية
إرجاع 1 لصحيح و 0 للخطأ.
ال
تُرجع 1 إذا كانت قائمة الانتظار الأولى هي المجموعة الفرعية الأولية لقائمة الانتظار الثانية ، مع كون عناصر الجزأين المتساويين متطابقتين وبنفس الترتيب. إذا كانت كلتا الطابور من نفس الحجم أو أحجام مختلفة ، والانتقال من اليسار إلى اليمين ، فقد تمت مصادفة عنصر في قائمة الانتظار الأولى أقل من العنصر المقابل في قائمة الانتظار الثانية ، فسيظل يتم إرجاع 1. وإلا يتم إرجاع 0. مثال:
طابور<مقدار ثابت شار*>هذا 1({'طيب القلب'و 'شيء آخر'})؛طابور<مقدار ثابت شار*>هذا 2({'شريرة'})؛
intعلى واحد=هذا 1<هذا 2؛
كلفة<<على واحد<< 'ن'؛
الخرج هو 1. > عامل التشغيل - عكس ما سبق. مثال: الإخراج: 0 ال<= Operator - مثل الإخراج: 1 عامل التشغيل> = - عكس ما سبق. مثال: الإخراج: 0 القيمة هي نوع بيانات ، حيث أن الكائن الذي تم إنشاء مثيل له هو فئة. يمكن أن يقبل إنشاء قائمة الانتظار أيضًا فئة كنوع بيانات. البرنامج التالي يوضح هذا: الخرج هو 5. تسمى قائمة الانتظار تقنيًا قائمة مرتبطة. هناك نوعان من القوائم المرتبطة لقائمة الانتظار: قائمة مرتبطة منفردة وقائمة مرتبطة بشكل مضاعف. يمكن تنفيذ عنصر قائمة مرتبط بشكل فردي عن طريق هيكل مكون من عضوين. أحد الأعضاء يحمل مؤشرًا للعنصر التالي والعضو الآخر يحمل المسند (مفرد البيانات). يمكن تنفيذ عنصر قائمة مرتبط بشكل مضاعف من خلال هيكل من ثلاثة أعضاء. يحتفظ العضو الأوسط بالمرجع ، بينما يحمل العضوان الأول والثالث مؤشرات للعناصر المجاورة. قائمة الانتظار هي بنية بيانات يدخل أولاً يخرج أولاً. هناك مواقف في الحوسبة عندما تصل البيانات في شكل قائمة انتظار ، مما يستلزم سلوكًا أولًا يصرف أولاً. المورد في الكمبيوتر هو أي مكون مادي أو افتراضي للتوافر المحدود. وهي تشمل وحدة المعالجة المركزية وبطاقة الفيديو والقرص الصلب والذاكرة. تقاسم مثل هذا المورد يحتاج إلى قائمة انتظار. تحتاج الأجهزة الطرفية للكمبيوتر إلى مقاطعة الكمبيوتر من وقت لآخر. يجب التعامل مع المقاطعات بنفس طريقة وصولها. هذا يحتاج إلى قائمة انتظار. يمكن استخدام قائمة الانتظار ، على سبيل المثال ، لإدارة ملفات التطبيق لوظيفة ما ، إذا كانت الملفات مخزنة في الكمبيوتر. قائمة الانتظار هي بنية بيانات قائمة ، وهي إما قائمة مرتبطة بشكل فردي أو قائمة مرتبطة بشكل مزدوج. كقاعدة عامة ، العنصر الأول الذي يدخل القائمة هو العنصر الأول الذي يظهر. يوفر C ++ بنية بيانات قائمة انتظار في مكتبته القياسية. فئات وظائف الأعضاء والمشغلين المتاحة لهذا الهيكل هي إنشاء قائمة الانتظار ، والوصول إلى عنصر قائمة الانتظار ، وسعة قائمة الانتظار ، ومعدلات قائمة الانتظار ، ومشغلي الطابور المحملين. يجب أن توفر أي بنية بيانات قائمة انتظار على الأقل ، وظائف عضو push () و pop (). push () يعني إرسال عنصر جديد في الجزء الخلفي من قائمة الانتظار ؛ و pop () يعني إزالة العنصر الموجود في مقدمة قائمة الانتظار. لسوء الحظ ، في C ++ ، لا تُرجع هذه الوظائف القيمة المدفوعة أو المنبثقة. لذلك ، لمعرفة العنصر الأخير قبل الدفع ، يجب استخدام وظيفة العودة الإضافية () ؛ ولمعرفة العنصر الأول قبل التفرقع ، يجب استخدام وظيفة الواجهة الإضافية (). القيمة هي نوع بيانات ، حيث أن الكائن الذي تم إنشاء مثيل له هو فئة. لذلك ، يمكن استخدام فئة معينة كنوع بيانات لإنشاء مثيل لقالب قائمة الانتظار. تصبح الكائنات المختلفة للفصل مثل قيم مختلفة للفصل. قائمة الانتظار لها تطبيقات على الكمبيوتر. يمكن استخدامه ، على سبيل المثال ، لإدارة ملفات التطبيق لوظيفة ما ، إذا كانت الملفات مخزنة في الكمبيوتر. كريس
طابور<مقدار ثابت شار*>هذا 2({'شريرة'})؛
intعلى واحد=هذا 1>هذا 2؛
كلفة<<على واحد<< 'ن'؛
طابور<مقدار ثابت شار*>هذا 2({'شريرة'})؛
intعلى واحد=هذا 1<=هذا 2؛
كلفة<<على واحد<< 'ن'؛
طابور<مقدار ثابت شار*>هذا 2({'شريرة'})؛
intعلى واحد=هذا 1> =هذا 2؛
كلفة<<على واحد<< 'ن'؛ الفئة وكائناتها المتشابهة
#يشمل
استخدام اسم للمحطة؛
فئة TheCla
{
عام:
intعلى واحد؛
ثابتة شارالفصل؛
فارغوظيفة(شارلاو مقدار ثابت شار *ص)
{
كلفة<< 'يوجد ' <<على واحد<< 'كتب تستحق' <<لا<<ص<< ' في المتجر.' << 'ن'؛
}
ثابتة فارغمرح(شارالفصل)
{
لو (الفصل== 'إلى')
كلفة<< 'وظيفة العضو الرسمية الثابتة' << 'ن'؛
}
}؛
intالأساسية()
{
TheCla obj1؛TheCla obj2؛TheCla obj3؛TheCla obj4؛TheCla obj5؛
طابور<TheCla>الذي - التي؛
الذي - التي.يدفع(obj1)؛الذي - التي.يدفع(obj2)؛الذي - التي.يدفع(obj3)؛الذي - التي.يدفع(obj4)؛الذي - التي.يدفع(obj5)؛
كلفة<<الذي - التي.بحجم() << 'ن'؛
إرجاع 0؛
} قائمة مرتبطة
تطبيقات الطابور
تقاسم موارد الكمبيوتر
معالجة المقاطعات
إدارة المعلومات.
استنتاج