المكتبة العربية لعلوم الحاسوب
مرحباً بالخوارزميات › الأكوام والطوابير 7 / 19 السابق التالي

تمارين

مراجعة المفاهيم

أي عنصر يخرج أولاً من المكدس أو الطابور؟

جهّز مكدساً فارغاً S وطابوراً فارغاً Q. نفّذ على كل منهما التسلسل نفسه من العمليات:

الخطوة 1: أضف A. الخطوة 2: أضف B. الخطوة 3: أزل عنصراً واحداً وسجّله. الخطوة 4: أضف C. الخطوة 5: واصل إزالة العناصر وتسجيلها حتى تفرغ الحاوية.

اكتب ترتيب إزالة العناصر من S ومن Q. واشرح الفرق باستخدام "آخر ما يدخل يخرج أولاً" أو "أول ما يدخل يخرج أولاً".

الإجابة

ترتيب الإزالة من المكدس S هو B, C, A. بعد إضافة العنصرين A, B، يُخرَج العنصر الأحدث إضافةً، وهو B، أولاً. وبعد إضافة C، يُخرَج C, A بهذا الترتيب. وهذا هو مبدأ "آخر ما يدخل يخرج أولاً".

ترتيب الإزالة من الطابور Q هو A, B, C. بعد إضافة العنصرين A, B، يُزال العنصر الأسبق إضافةً، وهو A، أولاً. وبعد إضافة C، يُزال B, C بهذا الترتيب. وهذا هو مبدأ "أول ما يدخل يخرج أولاً".

ماذا يحدث عندما تتجاوز مؤخرة الطابور نهاية المصفوفة؟

يُنفَّذ طابور بمصفوفة دائرية طولها 5، وفهارسها 0–4. حالياً front = 3 وsize = 2؛ ويُخزَّن A, B عند الفهرسين 3 و4 على الترتيب.

  1. عند إدخال C إلى الطابور، عند أي فهرس ينبغي تخزين C؟ وما قيمة size بعد الإدخال؟
  2. بعد ذلك، أخرِج عنصراً واحداً من الطابور. أي عنصر يُزال؟ وما القيمتان الجديدتان لـfront وsize؟
  3. ما الترتيب المنطقي من المقدمة إلى المؤخرة الآن؟ وهل تتطلب عملية الإخراج تحريك بقية العناصر في المصفوفة؟ ولماذا؟

الإجابة

  1. موضع العنصر الجديد هو (front + size) % 5 = (3 + 2) % 5 = 0، لذا يُخزَّن C عند الفهرس 0. وبعد الإدخال تصبح size = 3.

  2. تُزيل عملية الإخراج عنصر المقدمة الحالي A. وفهرس المقدمة الجديد هو (3 + 1) % 5 = 4، إذن front = 4 وsize = 2.

  3. الترتيب المنطقي للعناصر الصالحة هو B, C، حيث يقع B عند الفهرس 4 وC عند الفهرس 0. وتتطلب عملية الإخراج تغيير front وsize فقط. وتستخدم المصفوفة الدائرية عملية باقي القسمة لإعادة الفهرس إلى البداية، فلا حاجة إلى إزاحة بقية العناصر إلى الأمام.

العمليات على طرفي الطابور المزدوج

هنا يضيف push_first عنصراً في المقدمة، ويضيف push_last عنصراً في المؤخرة، ويزيل pop_first عنصراً من المقدمة، ويزيل pop_last عنصراً من المؤخرة.

نفّذ العمليات التالية على طابور مزدوج فارغ deq:

  1. push_last(A)
  2. push_last(B)
  3. push_first(C)
  4. pop_last()
  5. push_last(D)
  6. pop_first()
  1. ما العنصران اللذان تعيدهما عمليتا الإخراج؟
  2. بعد اكتمال جميع العمليات، ما العناصر المتبقية من المقدمة إلى المؤخرة؟
  3. افحص العمليات الست. هل يستطيع طابور يسمح بالإضافة في المؤخرة فقط والإزالة من المقدمة فقط تنفيذها جميعاً؟ إن لم يكن، فحدد العمليات التي لا يستطيع تنفيذها. ثم بيّن هل يستطيع الطابور المزدوج تنفيذها، مع شرح السبب.

الإجابة

بعد الخطوات الثلاث الأولى، يصبح الطابور المزدوج من المقدمة إلى المؤخرة [C, A, B].

  1. يزيل pop_last() العنصر B. وبعد إضافة D يصبح الطابور المزدوج [C, A, D]، ثم يزيل pop_first() العنصر C.

  2. يتبقى [A, D].

  3. لا يستطيع طابور يسمح بالإضافة في المؤخرة فقط والإزالة من المقدمة فقط تنفيذ جميع العمليات. فالخطوة 3، push_first(C)، تتطلب الإضافة في المقدمة، والخطوة 4، pop_last()، تتطلب الإزالة من المؤخرة. وكلتاهما خارج العمليات التي يدعمها هذا الطابور. أما الطابور المزدوج فيسمح بالإضافة والإزالة من كلا الطرفين، لذا يستطيع تنفيذ العمليات الست جميعاً.

تمارين برمجية

فحص تسلسل الأقواس

معطى سلسلة نصية s تحتوي فقط على الأنواع الثلاثة من الأقواس (), []، و{}، استخدم مكدساً لتحديد ما إذا كانت السلسلة صحيحة.

يجب أن يستوفي التسلسل الصحيح شرطين معاً: أن يطابق كل قوس إغلاق نوع أقرب قوس فتح غير مطابق، وألا يتبقى أي قوس فتح غير مطابق بعد الاجتياز. أعد قيمة منطقية للنتيجة.

تلميحات

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

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

السابق ملخص التالي التجزئة