ملخص

مراجعة النقاط الرئيسية

• المكدس (stack) بنية بيانات تتبع مبدأ "آخر ما يدخل يخرج أولاً" (LIFO)، ويمكن تنفيذه باستخدام المصفوفات أو القوائم المترابطة.
• من حيث كفاءة الزمن، يتمتع تنفيذ المكدس بالمصفوفة بكفاءة متوسطة أعلى، لكن عند التوسّع يتدهور التعقيد الزمني لعملية إدخال واحدة إلى $O(n)$. في المقابل، يقدّم تنفيذ المكدس بالقائمة المترابطة أداءً أكثر استقراراً.
• من حيث كفاءة المساحة، قد يؤدي تنفيذ المكدس بالمصفوفة إلى قدر من هدر المساحة. ومع ذلك، تجدر الإشارة إلى أن المساحة التي تشغلها عقد القائمة المترابطة أكبر من تلك التي تشغلها عناصر المصفوفة.
• الطابور (queue) بنية بيانات تتبع مبدأ "أول ما يدخل يخرج أولاً" (FIFO)، ويمكن أيضاً تنفيذه باستخدام المصفوفات أو القوائم المترابطة. والاستنتاجات المتعلقة بمقارنة كفاءة الزمن وكفاءة المساحة في الطوابير مشابهة لتلك الخاصة بالمكدسات المذكورة أعلاه.
• الطابور المزدوج (deque) طابور بمرونة أكبر يتيح إضافة العناصر وإزالتها من كلا الطرفين.

أسئلة وأجوبة

س: هل وظيفة التقدم والرجوع في المتصفح منفَّذة بقائمة مترابطة مزدوجة؟

سلوك التقدم والرجوع في المتصفح هو في جوهره تطبيق لـ"المكدس". عندما يزور المستخدم صفحة جديدة، تُضاف تلك الصفحة إلى قمة المكدس؛ وعندما ينقر المستخدم على زر الرجوع، تُخرَج تلك الصفحة من قمة المكدس. ويمكن للطابور المزدوج أن يدعم بيسر بعض العمليات الإضافية، كما ذُكر في قسم "الطابور المزدوج".

س: بعد الإخراج من المكدس، هل نحتاج إلى تحرير ذاكرة العقدة المُخرَجة؟

إذا كانت العقدة المُخرَجة ستكون مطلوبة لاحقاً، فلا حاجة إلى تحرير الذاكرة. أما إذا لن تُستخدم بعد ذلك، فإن لغات مثل Java وPython تمتلك جمع قمامة تلقائياً، فلا حاجة إلى تحرير الذاكرة يدوياً؛ وفي C وC++ يكون تحرير الذاكرة يدوياً ضرورياً.

س: يبدو الطابور المزدوج وكأنه مكدسان ملتحمان معاً. فما الغرض منه؟

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

س: كيف تُنفَّذ عمليتا التراجع والإعادة تحديداً؟

استخدم مكدسين: المكدس A للتراجع والمكدس B للإعادة.

1. كلما نفّذ المستخدم عملية، ادفع هذه العملية إلى المكدس A وامسح المكدس B.
2. عندما ينفّذ المستخدم "التراجع"، أخرِج أحدث عملية من المكدس A وادفعها إلى المكدس B.
3. عندما ينفّذ المستخدم "الإعادة"، أخرِج أحدث عملية من المكدس B وادفعها إلى المكدس A.