لماذا نحتاج إلى طابور؟
قبل أن نكتب سطر كود واحدًا، لننظر إلى ثلاثة أماكن تصادفون فيها الطابور كل يوم تقريبًا.
صندوق الدفع في السوبرماركت
الزبون الذي وصل أولًا يدفع أولًا. من يصل الآن يقف في النهاية، ولا يمكن الدخول من المنتصف.
طابعة في غرفة الحاسوب
عشرون طالبًا يرسلون ملفات للطباعة. الطابعة تطبعها حسب ترتيب الإرسال، واحدًا تلو الآخر.
مركز اتصالات هاتفي
«ستتم الإجابة على مكالمتك حسب ترتيب استلامها». الموظف المتفرّغ يتلقّى دائمًا المكالمة التي تنتظر منذ أطول وقت.
ما المشترك بين الثلاثة؟
من يدخل أولًا، يخرج أولًا. ندخل من جهة واحدة فقط (الذيل) ونخرج فقط من الجهة الأخرى (الرأس).
عرض توضيحي: طابور صندوق الدفع
الزبائن الجدد يدخلون من اليمين، وصندوق الدفع على اليسار يخدم دائمًا الزبون الواقف أولًا. شغّلوا الأزرار، وجرّبوا أيضًا التجاوز.
لماذا لا نستعمل مصفوفة ببساطة؟
في المصفوفة يمكن الوصول إلى أي خلية: arr[5], arr[0]، بأي ترتيب نريده. هذه قوة، لكنها أيضًا خطر. إذا كان الكود الذي يدير طابور الطباعة يستطيع إخراج ملف من منتصف الطابور، فسوف «يتجاوز» أحدهم ويحصل على طباعته قبل غيره.
الطابور هو مبنى معطيات مجرّد: نحدّد فقط ما هي العمليات المسموح بها (الإدخال إلى النهاية، الإخراج من الرأس، النظر إلى الرأس، فحص ما إذا كان فارغًا) وليس كيف هو مبنيّ من الداخل. هذا القيد هو بالضبط ما يحافظ على الترتيب.
واجهة – ما هي العمليات الموجودة وماذا تفعل كل واحدة منها. تنفيذ – كيف كُتبت العمليات من الداخل. كمستخدمين للطابور، يكفينا أن نعرف الواجهة.
تمرين: مناسب للطابور أم لا؟
لكل حالة، اختاروا هل سلوك FIFO مناسب لها.
كيف يتصرّف الطابور
للطابور طرفان. الرأس هو الجهة التي نخرج منها، والذيل هو الجهة التي ندخل إليها. في رسومات اللومدة يكون الرأس دائمًا على اليسار، كما في طباعة الطابور: العنصر الأول الذي يُطبع هو الذي في الرأس.
العملية البانية وأربع عمليات أساسية:
العملية البانية: تُنشئ طابورًا جديدًا فارغًا. كل عمل مع الطابور يبدأ هنا، مثلًا Queue<int> q = new Queue<int>();
تُدخل x إلى نهاية الطابور (إلى الذيل).
تُخرج العنصر الموجود في الرأس وتُعيده. العنصر الذي بعده يصبح الرأس الجديد.
تُعيد العنصر الموجود في الرأس بدون إخراجه. الطابور لا يتغيّر.
تُعيد true إذا لم يكن في الطابور أي عنصر.
محاكي
اكتبوا عددًا وشغّلوا العمليات. كل عملية تُسجَّل في السجل كسطر C#. جرّبوا أيضًا إخراج عنصر من طابور فارغ وشاهدوا ماذا يحدث.
البرنامج انهار أثناء التشغيل
استدعيتم عندما كان الطابور فارغًا. حسب واجهة وزارة التربية والتعليم، ممنوع استدعاءRemove() أوHead() على طابور فارغ: لا يوجد عنصر في الرأس، والبرنامج يتوقف مع استثناء (Exception).
العبرة: قبل Remove() أو Head() يجب التأكد من أن الطابور ليس فارغًا، عادةً بواسطة !q.IsEmpty().
تحدٍّ: توقّعوا الحالة
نبدأ من طابور فارغ ونشغّل الكود التالي. اكتبوا محتوى الطابور في النهاية، من الرأس إلى الذيل، مع فواصل بينها (مثلًا 3,5,7).
واجهة وزارة التربية والتعليم
ما هي الواجهة؟
واجهة هي قائمة العمليات التي يقدّمها لنا مبنى المعطيات: اسم كل عملية، ماذا تستقبل، ماذا تُعيد وماذا تفعل. الواجهة تقول ماذا يمكن أن نفعل، لا كيف يُنفَّذ ذلك.
فكّروا في جهاز التحكّم بالتلفاز. فيه أزرار: تشغيل، القناة التالية، الصوت. أنتم تعرفون ماذا يفعل كل زر، ولا تحتاجون إلى معرفة ما يحدث داخل الدوائر الكهربائية. الأزرار هي الواجهة. الدوائر هي التنفيذ.
هذا كل ما يراه ويشغّله المبرمج الذي يستخدم الطابور.
كيف تُحفظ العناصر في الذاكرة وكيف كُتبت كل عملية. كمستخدمين، ليس لدينا وصول إلى ذلك.
لاستخدام الطابور يكفي أن نعرف خمس عمليات. لا حاجة لفهم الكود الذي في الداخل.
التنفيذ مخفي، ولذلك لا يمكن «الالتفاف» على الواجهة وإفساد ترتيب الطابور. فقط العمليات المسموح بها متاحة.
يمكن استبدال التنفيذ (مثلًا بنسخة أسرع)، وكل الكود الذي يستخدم الطابور سيستمر في العمل كما كان، لأن الواجهة لم تتغيّر.
في البجروت تكتبون عمليات تستخدم الطابور فقط عبر الواجهة. ممنوع افتراض أي شيء عن كيفية بناء الطابور من الداخل.
ما هذا الـ<T>؟
في الواجهة سترون الاسم Queue<T>. قبل أن نشرح ما هو، لنفهم أي مشكلة يحلّها.
لنفترض أننا نحتاج إلى طابور أعداد، طابور أسماء وطابور طلاب. بدون الجنريّة (Generics) كنا سنحتاج إلى كتابة ثلاث فئات مختلفة:
ثلاث فئات مع الكود نفسه تمامًا. الفرق الوحيد هو نوع العناصر. إذا وجدنا خطأ (bug)، سنحتاج إلى إصلاحه في ثلاثة أماكن.
الحرف T هو مكان محجوز للنوع. كما أن بارامتر العملية يستقبل قيمة (مثلًا Print(5))، فإن الأقواس المثلثة تستقبل نوعًا. عندما نكتب Queue<int>، كل T في الواجهة «يتحوّل» إلىint.
كيف نستخدم ذلك
فيQueue<int> يمكن إدخال أعداد صحيحة فقط. المحاولة nums.Insert("hello") ستعطي خطأ ترجمة: البرنامج لن يعمل إطلاقًا حتى تصلحوه.
nums.Remove() تُعيد int، ولذلك يمكن الكتابة مباشرة int x = nums.Remove();.
خطأ ترجمة – الكود لا يجتاز الترجمة، مثلًا نوع غير صحيح. يُكتشف قبل التشغيل.
انهيار أثناء التشغيل – الكود يجتاز الترجمة، لكنه ينهار عندما يعمل، مثلًا Remove() على طابور فارغ.
تمرين: سليم، خطأ ترجمة أم انهيار؟
في الجدول التالي، في كل مكان كُتب فيه T، اقرأوا «النوع الذي اخترته عند الإعلان عن الطابور».
جدول الواجهة Queue<T>
في بداية الملف يجب إضافة سطر الاستيراد لمكتبة فئات وزارة التربية والتعليم:
| العملية | ماذا تفعل | شرط مسبق | التعقيد |
|---|---|---|---|
| Queue<T>() | عملية بانية: تُنشئ طابورًا فارغًا | – | O(1) |
| void Insert(T x) | تُدخل x إلى نهاية الطابور | – | O(1) |
| T Remove() | تُخرج العنصر الموجود في رأس الطابور وتُعيده | الطابور ليس فارغًا. على طابور فارغ – انهيار أثناء التشغيل | O(1) |
| T Head() | تُعيد العنصر الموجود في رأس الطابور بدون إخراجه | الطابور ليس فارغًا. على طابور فارغ – انهيار أثناء التشغيل | O(1) |
| bool IsEmpty() | تُعيد true إذا كان الطابور فارغًا، وإلا false | – | O(1) |
| string ToString() | تُعيد سلسلة نصية تصف عناصر الطابور من الرأس إلى الذيل | – | O(n) |
ما ليس موجودًا في الواجهة
لا يوجد Size() أو Count. لمعرفة عدد العناصر، يجب المرور على الطابور كله.
لا يوجد q[2]. نرى الرأس فقط.
يمكن الإدخال إلى الذيل، لكن لا يمكن رؤية ما فيه.
كل سؤال عن «الطابور كله» (كم عنصرًا، ما المجموع، هل x موجود) يتطلّب مسحًا. المسح يكلّف O(n)، وكي لا نُتلف الطابور سنستخدم طابورًا مساعدًا. هذا ما سنتعلّمه في الفصل 4.
مسح الطابور
كيف نمرّ على جميع العناصر؟
في المصفوفة نمرّ على العناصر بحلقة for مع فهرس. في الطابور لا يوجد فهرس: نرى الرأس فقط. للوصول إلى العنصر الثاني، يجب إخراج الأول.
سنبني عملية تطبع جميع عناصر الطابور. سنفعل ذلك في ثلاث محاولات، ونرى ما الخطأ في كل واحدة. شغّلوا كل محاولة خطوة بخطوة.
لماذا نحتاج إلى طابور مساعد؟
في المحاولة 2 كان الإخراج صحيحًا، فما المشكلة؟ العملية لا تستقبل نسخة من الطابور. إنها تستقبل الطابور نفسه الموجود في البرنامج الذي استدعاها. كل Remove() داخل العملية يُخرج عنصرًا من طابور البرنامج الرئيسي:
لذلك يجب حفظ كل عنصر نُخرجه في مكان ما، كي نتمكّن من إعادته. هذا المكان هو طابور مساعد. ولماذا طابور بالذات؟ لأنه يحافظ على الترتيب: ما يخرج أولًا من q يدخل أولًا إلى temp، ويعود أولًا إلى q.
1. نُنشئ طابورًا مساعدًا فارغًا.
2. طالما q ليس فارغًا: نُخرج عنصرًا، نعالجه، ونُدخله إلى temp.
3. طالما temp ليس فارغًا: نُعيد عنصرًا إلى q.
4. الآن فقط نُعيد الجواب.
أمثلة أساسية
أربع عمليات كلها مبنية على الهيكل. قارنوا بينها: ما الذي يتغيّر في كل واحدة، وما الذي يبقى مطابقًا؟
أخطاء شائعة
المسح بدون طابور مساعد يترك q فارغًا. العملية تُعيد جوابًا صحيحًا، لكن طابور من استدعاها قد أُتلف.
حلقة while (!q.IsEmpty()) تستدعي فقطHead() لا تُخرج شيئًا، ولذلك لا تنتهي أبدًا.
الخروج من العملية قبل الاسترجاع يترك q ناقصًا. أولًا نسترجع، وبعد ذلك نُعيد الجواب.
امتحان ذاتي أولي
13 سؤالًا عن الفصول 1–4: سلوك الطابور، الواجهة، الجنريّة، الطابور الفارغ والمسح مع طابور مساعد. لكل سؤال محاولة واحدة، ويظهر بعدها مباشرة شرح. عندما تنتهون من الإجابة على جميع الأسئلة، يُفتح الجزء ب.
نسخ الطابور والمراجع
لنفترض أننا نريد نسخة من q كي نعمل عليها دون المساس بالأصل. يبدو طبيعيًا أن نكتب:
هذا لا يعمل. الطابور هو كائن (object). متغيّر من نوع طابور لا يحتوي على الطابور نفسه، بل على مرجع إليه، أي مكانه في الذاكرة. الإسناد q2 = q ينسخ المرجع فقط. الآن يوجد اسمان للطابور نفسه، وكل تغيير عبر q2 يغيّر q أيضًا.
جرّبوا بأنفسكم: شغّلوا عمليات على q2 في الحالتين، ولاحظوا ماذا يحدث لـ q.
محاولة شائعة: طابور مساعد بالإسناد
أحيانًا تُكتب عملية مسح هكذا، على أمل أن يحفظ temp العناصر وأن يسترجع السطر الأخير q:
temp = q لا يُنشئ طابورًا جديدًا. temp و-q هما اسمان للكائن نفسه. كل عنصر نُخرجه من q ونُدخله إلى temp يعود إلى نهاية الطابور نفسه. الطابور لا يفرغ أبدًا، والحلقة الأولى لا تنتهي: 4، 7، 2، 4، 7، 2...
حتى لو انتهت الحلقة، q = temp يجعل المتغيّر q يشير فقط إلى الكائن الذي يشير إليه temp، وهو أصلًا الكائن نفسه. الإسناد لمتغيّر لا ينقل عناصر، ولا يغيّر الطابور نفسه.
شغّلوا ولاحظوا: في كل خطوة يبدو q و-temp متطابقين، لأنهما الطابور نفسه.
الطابور المساعد يُنشأ فقط مع new Queue<int>()، والعناصر تنتقل بين الطوابير فقط مع Remove() و-Insert(). الإسناد بين متغيّرات الطابور لا ينسخ ولا يسترجع شيئًا.
للحصول على طابور منفصل فعلًا، يجب إنشاء كائن جديد مع new وإدخال العناصر إليه واحدًا واحدًا. العملية Copy تستخدم طابورين جديدين: copy هو النتيجة، و-temp يُستخدم لاسترجاع q. لا يمكن استخدام copy للاسترجاع أيضًا، لأننا عندها سنُفرغه.
هذا أيضًا هو السبب في أن طابور البرنامج الرئيسي في الفصل 4 (البند 4.2) قد فرغ: عندما نمرّر طابورًا إلى عملية، يستقبل البارامتر مرجعًا إلى الكائن نفسه، لا نسخة.
طرق إضافية لمسح الطابور
المسح الدائري: بدون طابور مساعد
حتى الآن مسحنا مع طابور مساعد: حلقتان، وطابور إضافي يحتفظ بكل العناصر. هناك طريقة أخرى: المسح داخل الطابور نفسه. نُخرج عنصرًا من الرأس، نعالجه ونُدخله مرة أخرى إلى الذيل. بعد دورة كاملة، يكون كل عنصر قد مرّ مرة واحدة وعاد الطابور إلى ترتيبه الأصلي.
المشكلة: كيف نعرف أننا أنهينا الدورة؟ حلقة while (!q.IsEmpty()) لن تعمل، لأننا نُعيد إدخال كل عنصر نُخرجه، والطابور لا يفرغ أبدًا. سنرى حلّين.
الطريقة أ: عنصر وهمي
نُدخل إلى ذيل الطابور قيمة خاصة، عنصرًا وهميًا. ننفّذ دورات طالما العنصر الوهمي ليس في الرأس. عندما يصل العنصر الوهمي إلى الرأس، تكون كل العناصر قد مرّت مرة واحدة. في النهاية نُخرج العنصر الوهمي.
هذه الطريقة ممكنة فقط عندما توجد قيمة لا يمكن أن تظهر في الطابور. وإلا، فستتوقف الحلقة عند «وهمي» حقيقي في منتصف الطابور.
| محتوى الطابور | عنصر وهمي مناسب |
|---|---|
| علامات، من 0 إلى 100 | -1 |
| أعداد موجبة فقط | 0 |
| أسماء طلاب (سلاسل نصية) | "" أو null، إذا لم تكن في الطابور عناصر null |
| كائنات، مثلًا Queue<Point> | null، إذا لم تكن في الطابور عناصر null |
| أعداد صحيحة أيًّا كانت | لا توجد قيمة مناسبة. نستخدم الطريقة ب (Size و-for) أو طابورًا مساعدًا |
الخروج في منتصف الحلقة يترك العنصر الوهمي داخل الطابور، بين العناصر الحقيقية. نسيان Remove() في النهاية يتركه في الرأس. في الحالتين، الكود التالي الذي سيعمل مع الطابور سيحصل على قيمة خاطئة.
الطريقة ب: عملية Size وحلقة for
عندما لا توجد قيمة مناسبة للعنصر الوهمي (مثلًا في طابور أعداد صحيحة أيًّا كانت)، يمكن العدّ. إذا عرفنا مسبقًا كم عنصرًا في الطابور (n)، ننفّذ n دورة بالضبط بحلقة for.
لا يوجد q.Size()، ولا يوجد q.Count. محاولة استدعائهما ستعطي خطأ ترجمة. لاستخدام هذه الطريقة يجب أن تنفّذوا بأنفسكم عملية مساعدة تُعيد حجم الطابور، وأن تكتبوها في الكود الخاص بكم (في الامتحان أيضًا). هذه هي العملية من الفصل 4.3:
انتبهوا إلى الاستدعاء: Size(q)، عملية ستاتيكية تستقبل الطابور كبارامتر، وليس q.Size(). العملية نفسها تستخدم طابورًا مساعدًا وتسترجع q، بحيث يكون الطابور سليمًا بعد الاستدعاء ويمكن بدء الدورة.
فيreturn أو بـbreak داخل الـ for، الطابور لا يُتلف، لكنه يبقى مُدوَّرًا: العناصر التي مرّت أصبحت في النهاية. من استدعى العملية يحصل على طابور بترتيب مختلف. الحل: متغيّر علم (flag)، إكمال كل الـ n دورة، وإعادة الجواب فقط بعد الحلقة.
مقارنة بين الطرق الثلاث
| طابور مساعد | عنصرًا وهميًا | Size و-for | |
|---|---|---|---|
| ذاكرة إضافية | طابور كامل | لا يوجد | فقط داخل Size |
| ماذا نحتاج | لا شيء | قيمة لا يمكن أن تظهر في الطابور | تنفيذ Size |
| الخروج في منتصف الحلقة | الطابور يبقى ناقصًا | العنصر الوهمي يبقى داخل الطابور | الطابور يبقى مُدوَّرًا |
| التعقيد | O(n) | O(n) | O(n) |
| مناسب لنسخ الطابور | نعم | نعم، مع طابور نتيجة | نعم، مع طابور نتيجة |
في الطرق الثلاث القاعدة واحدة: أولًا نُكمل المرور على الطابور كله، وبعد ذلك فقط نُعيد الجواب.
تمرين: هل يمكن استخدام عنصر وهمي؟
النجاعة
n هو عدد العناصر في الطابور. السؤال دائمًا هو السؤال نفسه: كيف يزداد زمن التشغيل عندما يكبر الطابور؟ في الطابور هناك ثلاث إجابات من المفيد معرفتها.
O(1): عدد ثابت من العمليات
الكود ينفّذ عدد العمليات نفسه في طابور من 3 عناصر وفي طابور من مليون عنصر. كل عملية واجهة (Insert, Remove, Head, IsEmpty) هي O(1)، وكذلك كل كود ينفّذ عددًا ثابتًا منها، حتى داخل حلقة، طالما أن عدد الدورات لا يتعلّق بـ n.
O(n): نمرّ على الطابور
الكود يمرّ على كل عناصر الطابور، وعلى كل عنصر ينفّذ عددًا ثابتًا من العمليات. كل طرق المسح التي تعلّمناها (طابور مساعد، عنصر وهمي، Size و-for) هي O(n)، وكذلك Size, Sum, Exists, Count, Copy و-ToString.
كذلك عدّة عمليات مسح واحدة تلو الأخرى هي O(n): O(n) + O(n) + O(n) = 3·O(n) = O(n). عند التفكير في التعقيد نتجاهل الثابت.
O(n²): عملية مساعدة تمسح، داخل مسح
يصبح التعقيد O(n²) عندما ننفّذ على كل عنصر في الطابور عملًا بتعقيد O(n). يحدث هذا عادةً عندما نستدعي داخل المسحعملية مساعدة تمسح بنفسها طابورًا. مثلًا، العملية المساعدة ExistIn تفحص هل x موجود في الطابور. إنها تمسح الطابور كله، ولذلك هي O(n):
الآن سنستخدمها. العملية Common تُعيد طابورًا جديدًا فيه كل عناصر q1 الموجودة أيضًا في q2. لكل كل عنصر من q1 تستدعي ExistIn، التي تمرّ على كل q2:
«نرمز بـ n لعدد العناصر في q1 وبـ m لعدد العناصر في q2. الحلقة الرئيسية تنفّذ n دورة. في كل دورة تُستدعى ExistIn، التي تمسح q2 بتعقيد O(m). لذلك الحلقة هي O(n·m). استرجاع q1 هو O(n). المجموع O(n·m)، وإذا كان للطابورين الحجم نفسه n: O(n²).»
سطر واحد مثل if (ExistIn(q2, x)) يبدو بريئًا، لكنه مسح كامل. عند تحليل التعقيد، كل استدعاء لعملية مساعدة يُحسب حسب تعقيدها، وليس كعملية واحدة.
تلخيص: كيف نميّز
| ماذا نرى في الكود | التعقيد | مثال |
|---|---|---|
| عدد ثابت من عمليات الواجهة | O(1) | q.Insert(q.Remove()); |
| مسح واحد، أو عدّة عمليات مسح واحدة تلو الأخرى | O(n) | Sum(q); Size(q); |
| مسح، وداخله عملية تمسح طابورًا | O(n²) | ExistIn داخل حلقة على q |
قاعدة إبهام: العمليات المتتالية نجمعها، والعمليات المتداخلة نضربها.
تمرين: ما التعقيد؟
n هو عدد العناصر في كل طابور.
امتحان ذاتي: الجزء ب1
12 سؤالًا عن الفصول 6–8: نسخ الطابور، المسح الدائري والنجاعة. عندما تنتهون من الإجابة على جميع الأسئلة، يُفتح الجزء ب2.
أمثلة متقدّمة
هذا هو القسم الثاني من الجزء ب: نستخدم أدوات الجزء ب1 لحلّ مسائل أكثر تعقيدًا. في هذا الفصل لا تكتفي الأمثلة بقراءة الطابور، بل تغيّره أيضًا: تُدخل إلى الرأس أو إلى مكان مرتّب، تحذف عناصر وتبني طابورًا جديدًا من طابورين. سنتناول التعاود (Recursion) في الفصل القادم.
قبل أن تشغّلوا مثالًا، حاولوا توقّع محتوى الطابور في النهاية.
InsertSorted هي O(n). إذا بنينا طابورًا مرتّبًا من كل عناصر q، واحدًا واحدًا:
كل استدعاء يمرّ على كل ما هو موجود أصلًا في res: 1، 2، 3، ... حتى n عنصر. المجموع 1+2+...+n = n(n+1)/2، أي O(n²): عملية مساعدة تمسح، داخل مسح، كما في الفصل 8. هذا في الواقع ترتيب بالإدخال (Insertion Sort).
طابور كائنات
الفئة Point
يمكن للطابور أن يحتوي كائنات من أي فئة، وليس أعدادًا فقط. سنعمل مع الفئة Point، التي تمثّل نقطة في المستوى:
| العملية | ماذا تفعل |
|---|---|
| Point(int x, int y) | عملية بانية: تُنشئ نقطة بإحداثيين x و-y |
| int GetX() / int GetY() | تُعيدان إحداثي x أو y |
| void SetX(int x) / void SetY(int y) | تغيّران إحداثي x أو y |
| string ToString() | تُعيد سلسلة نصية بالشكل (x,y) |
الطابور يحتفظ بمراجع
كما رأينا في الفصل 6، متغيّر من نوع Point يحتفظ مرجع للكائن. الطابور أيضًا يحتفظ بمراجع. q.Remove() يُعيد مرجعًا إلى النقطة نفسها التي كانت في الطابور. إذا غيّرناها بـ SetY وأدخلناها مرة أخرى، يحتفظ الطابور بالنقطة المحدَّثة.
لهذا تأثير مهم على النسخ. العملية Copy (العملية نفسها من الفصل 6، مع Point بدل int) تُنشئ طابورًا جديدًا، لكنها تُدخل إليه النقاط نفسها. الطابوران منفصلان، والنقاط التي فيهما مشتركة:
الإخراج أو الإدخال في طابور واحد لا يؤثّر على الآخر، لأن الطابورين منفصلان. لكن تغيير نقطة (SetX, SetY) يظهر في الطابورين، لأنها النقطة نفسها. للحصول على نقاط منفصلة، يجب إنشاء نسخة لكل واحدة: new Point(p.GetX(), p.GetY()).
مقارنة الكائنات
العامل == بين كائنين يقارن المراجع: هل هو الكائن نفسه في الذاكرة. لا يفحص هل القيم متساوية. نقطتان (3,-4) أُنشئت كل منهما بـ new هما كائنان مختلفان، ولذلك == يُعيد false.
لفحص هل نقطتان متساويتان في قيمتهما، نقارن الحقول:
في C# العامل == بين سلسلتين نصيتين يقارن المحتوى، ولذلك s.GetName() == "دانة" يعمل كما هو متوقَّع. هذه حالة خاصة للفئة string.
null كعنصر وهمي
في طابور الكائنات يوجد عنصر وهمي طبيعي: null، مرجع لا يشير إلى أي كائن. يكون مناسبًا بشرط ألّا تكون في الطابور عناصر هي null. عندما نُدخل إلى الطابور فقط كائنات أُنشئت بـ new، يتحقّق الشرط.
أمثلة: طابور نقاط
فئة إضافية: Student
كل الطرق التي تعلّمناها تعمل على طابور من أي فئة. سنعمل مع فئة تمثّل طالبًا له اسم وعلامة:
| العملية | ماذا تفعل |
|---|---|
| Student(string name, int grade) | عملية بانية: تُنشئ طالبًا باسم وعلامة |
| string GetName() | تُعيد اسم الطالب |
| int GetGrade() | تُعيد العلامة |
| void SetGrade(int grade) | تغيّر العلامة |
مصفوفة طوابير
الطابور كائن، ولذلك يمكن بناء مصفوفة طوابير: كل خلية في المصفوفة تحتفظ بمرجع لطابور. هذا مفيد عندما توجد عدّة طوابير من النوع نفسه: طابور لكل صندوق دفع في السوبرماركت، طابور لكل صف، طابور لكل رقم.
new Queue<int>[3] يُنشئ مصفوفة من 3 خلايا، وكل خلية تحتوي null. لا يوجد بعد أي طابور. استدعاءarr[0].Insert(5) قبل إنشاء الطابور سيسبّب انهيارًا أثناء التشغيل (NullReferenceException). لذلك نضيف دائمًا حلقة تُنشئ طابورًا جديدًا في كل خلية.
arr.Length هو عدد الطوابير في المصفوفة، ويمكن الوصول إليه مباشرة. عدد العناصر في الطابور arr[i] يُحسب فقط بالمسح، مثلًا Size(arr[i]).
على arr[i] نشغّل كل عمليات الواجهة وكل العمليات المساعدة التي كتبناها. يمكن أيضًا مصفوفة من طوابير كائنات، مثلًا Queue<Student>[]، طابور طلاب لكل صف.
في مثال صندوق الدفع الأقصر، تُستدعى Size مرة واحدة على كل طابور. إجمالًا نمرّ مرة واحدة على كل العناصر في كل الطوابير: O(k + N)، حيث k هو عدد الطوابير و-N هو عدد العناصر فيها جميعًا معًا.
تمرين: ماذا سيُعيد التعبير؟
في كل سطر، a و-b متغيّران من نوع Point، و-s متغيّر من نوع Student.
التعاود على الطابور
يمكن المرور على الطابور أيضًا بالتعاود (Recursion). في كل استدعاء نُخرج عنصرًا واحدًا، نستدعي العملية على الطابور المتبقّي (الذي صغر بعنصر واحد)، وفي طريق العودة نعالج العنصر. شرط التوقف دائمًا تقريبًا: الطابور فارغ.
لا يوجد هنا طابور مساعد. كل استدعاء يحفظ عنصرًا واحدًا في متغيّر محلّي، ومكدّس الاستدعاءات يؤدّي دور الطابور المساعد. الفرق المهم: العنصر الذي خرج أخيرًا هو أول من يُعاد إدخاله، ولذلك ينقلب الترتيب.
في المثالين انتبهوا إلى مكدّس الاستدعاءات: في كل خطوة ترون أي استدعاءات «تنتظر» وأي x محفوظ في كل منها.
نجاعة التعاود
في Reverse يوجد n+1 استدعاء: واحد لكل عنصر، وواحد إضافي يجد طابورًا فارغًا. في كل استدعاء يُنفَّذ عدد ثابت من العمليات (IsEmpty, Remove, Insert). لذلك زمن التشغيل هو O(n).
للذاكرة أيضًا ثمن. كل استدعاء ما زال «ينتظر» يحفظ x الخاص به في مكدّس الاستدعاءات. في الذروة يوجد n+1 استدعاء مفتوح، أي ذاكرة بتعقيد O(n). هذا يشبه طابورًا مساعدًا بحجم n، إلا أنه مخفي في المكدّس.
امتحان ذاتي ختامي
14 سؤالًا عن الجزء ب2: أمثلة متقدّمة، طابور كائنات ومصفوفة طوابير، والتعاود، بالإضافة إلى سؤال مراجعة واحد عن الجزء الأساسي. في النهاية ستحصلون على علامة وقائمة مواضيع للمراجعة.
أسئلة مفتوحة للتمرين
اكتبوا حلًّا في الدفتر أو في بيئة التطوير، وبعد ذلك فقط افتحوا الحل.
اكتبوا عملية IsSorted(Queue<int> q) تُعيد true إذا كانت عناصر الطابور مرتّبة تصاعديًا من الرأس إلى الذيل، و-false خلاف ذلك. في نهاية العملية يجب أن يعود الطابور إلى حالته الأصلية. الطابور الفارغ يُعتبر مرتّبًا.
اعرض الحل
التعقيد: O(n). انتبهوا إلى فحص الطابور الفارغ قبل Head().
اكتبوا عملية Merge تستقبل طابورين من الأعداد الصحيحة، كل منهما مرتّب تصاعديًا، وتُعيد طابورًا جديدًا مرتّبًا تصاعديًا يحتوي كل عناصر الطابورين. مسموح إفراغ الطابورين المستقبَلين.
اعرض الحل
التعقيد: O(n+m). في كل دورة نقارن بين الرأسين ونُخرج الأصغر. عندما يفرغ أحد الطابورين، ننقل كل ما تبقّى في الآخر.
ورقة مساعدة
Insert(x) · Remove() · Head()
IsEmpty() · ToString()
على طابور فارغ ممنوع Remove() و-Head().
نُخرج من q ← نعالج العنصر ← نُدخل إلى temp. في النهاية ننقل temp عائدين إلى q.
طابور مساعد واسترجاع · عنصر وهمي، عندما توجد قيمة لا يمكن أن تظهر · Size (نفّذوها بأنفسكم!) وحلقة for. في جميعها: لا نخرج في المنتصف.
عملية واجهة: O(1)، ما عدا ToString. مسح: O(n). مسح داخل مسح: O(n²). لا نستدعي Size في شرط الحلقة.
فقط مع new وحلقة تنقل العناصر. الإسناد q2 = q لا ينسخ.
نُخرج x، نستدعي تعاوديًا، نُدخل x مرة أخرى إلى النهاية. النتيجة: ترتيب الطابور ينقلب.
كل عملية واجهة: O(1) (ما عدا ToString). كل مسح: O(n).
الفصل ما زال مغلقًا
أجيبوا إجابة صحيحة على «فحص الفهم» في نهاية الفصل السابق لفتحه.
التقدّم يُحفظ في كل حاسوب على حدة. إذا انتقلتم إلى حاسوب آخر، يمكنكم فتح الجزء الذي وصلتم إليه دون المرور مجددًا على الأجزاء التي قبله.