المكدس في هياكل البيانات: الإضافة والحذف وفكرة التراجع

ما هو المكدس؟

القاعدة تصف واجهة وترتيبًا، بينما يمكن أن تختلف طريقة التخزين. ولا تخلط بين نوع البيانات المجرد وبين كل استخدام لكلمة stack، مثل مكدس استدعاءات البرنامج.

تتبع العمليات

نكتب العناصر من الأقدم إلى الأحدث، والعنصر الأعلى هو الأحدث.

العنصر التالي للحذف هو 40، وليس 10. هذا يختلف عن قاعدة الطابور.

مثال باستخدام C++

#include <iostream>
#include <stack>

int main() {
    std::stack<int> history;
    history.push(10);
    history.push(20);
    while (!history.empty()) {
        std::cout << history.top() << '\n';
        history.pop();
    }
}

الناتج 20 ثم 10 في سطرين. يفحص البرنامج عدم الفراغ قبل قراءة top. في std::stack تزيل pop العنصر ولا تعيد قيمته؛ لو تحتاج القيمة، اقرأ top قبل الحذف.

في هذا المثال الصغير، الحاوية الافتراضية تدعم عمليات الطرف المعتادة بزمن ثابت. عند تحليل تنفيذ آخر، راجع تكلفة عملياته بدل افتراضها من اسم المكدس فقط.

هل المكدس وحده يصنع التراجع؟

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

اسم الإجراء وحده قد لا يكفي؛ ربما تحتاج القيمة السابقة أو بيانات تعيد الحالة. وإضافة إعادة التنفيذ بعد التراجع تحتاج قواعد أخرى، خاصة إذا حدث تعديل جديد.

لا تهمل حالة الفراغ

حدد ما يحدث عندما يطلب المستخدم تراجعًا ولا يوجد إجراء محفوظ. يمكن تعطيل التحكم أو توضيح عدم وجود إجراء، لكن التنفيذ يجب ألا يقرأ عنصرًا غير موجود.

اختبر عنصرًا واحدًا وعدة عناصر ثم حذفها كلها. اكتب الحالة المتوقعة بعد كل عملية قبل مراجعة الكود.

تمرين

أضف 3 ثم 7 ثم 2. احذف مرتين، ثم أضف 9. المحتوى النهائي 3 ثم 9، والأعلى 9. اشرح السبب دون تشغيل برنامج.

تأتي هياكل البيانات بعد C++ في جمال تك. استخدم المثال لفهم قاعدة الترتيب، ثم قارنها بالطابور. معرفة العنصر الذي يجب معالجته تاليًا تسبق اختيار اسم البنية.