مكدس (بنية بيانات)
يعرف المكدس بأنه بنية معطيات مجردة أو مجموعة يمكن فيها القيام بعمليات محددة على العناصر وهي إضافة عنصر جديد إلى المجموعة (تعرف هذه العملية بالدفع ) وإزالة عنصر من المجموعة (تعرف هذه العملية بالطرح "). تجعل عمليتا الدفع والطرح المكدس بنية معطيات تتمتع بخاصية "من يدخل أخيراً يخرج أولاً " أو اختصاراً LIFO. في بنية المعطيات ذات الخاصية LIFO يكون آخر عنصر تم إضافته للمجموعة هو أول عنصر تتم إزالته منها. يعرف المكدس بأنه بنية معطيات متسلسلة تتم فيها عمليات الإضافة والحذف عند نهاية واحدة فقط من السلسلة. عادةً ما يشار إلى آخر عنصر تمت إضافته إلى المكدس باسم قمة المكدس كما يزود المكدس بعملية استراق" تمكن من معرفة قيمة قمة المكدس دون القيام بإزالته منه.
للمكدس سعة محدودة. فإذا كان المكدس ممتلئاً لا يمكن عندئذ القيام بعملية دفع عنصر إليه، وتسبب محاولة القيام بهذه العملية حصول
طفحان (أو ما يعرف بتجاوز الحد الأعلى للسعة ). تقوم عملية الطرح بإزالة قمة المكدس وتسبب إما الكشف عن العناصر الموجودة داخل المكدس بالتتابع أو الحصول على مكدس فارغ، إذا كان المكدس فارغاً فإن محاولة القيام بالطرح يسبب حصول تجاوز الحد الأدنى للسعة .
يعرف المكدس أيضاً بأنه بنية معطيات "مقيدة"، يفود السبب في ذلك إلى وجود عدد قليل نسبياً من العمليات التي يمكن إجراؤها عليه. كما أن طبيعة عمليات الدفع والطرح تفرض ترتيباً طبيعياً على العناصر. ذلك أن ترتيب حذف العناصر من المكدس يعاكس تماماً ترتيب إضافتها إليه. وبالتالي فإن العناصر الموجودة "أسفل" المكدس ستبقى فترةً أطول من نظيرتها الموجودة بالقرب من قمة المكدس.
اقترح آلان تورنغ عام 1946 بنية المعطيات المكدس لأول مرة كجزء من تصميمه للكومبيوتر كطريقة لاستدعاء والعودة من الإجراءات الفرعية (وقد استخدم مصطلحات "الدفن" و"النبش" للإشارة إلى هذه العمليات). وقد اقترح الألمانيان كلاوس ساملسن وفريدريش باور من جامعة ميونيخ التقنية بنية المعطيات المكدس عام 1955 وتقدما بطلب براءة اختراع له. وقد اقترح الأسترالي تشارلز لينارد هامبلن المبدأ ذاته عام 1957.
يعرف المكدس بأنه بنية معطيات بسيطة تتمتع بعدد من العمليات المجردة والتي يمكن تحقيقها بحرية تامة. أو يمكن تعريف المكدس بأنه قائمة خطية من العناصر التي يمكن إضافتها وحذفها عند نهاية واحدة تعرف باسم "القمة".
فيما يلي قائمة بتواقيع الطرق الخاصة ببنية معطيات المكدس:
codice_1
codice_2
codice_3
codice_4
codice_5
حيث يشير N إلى نمط معطيات عناصر المكدس (في هذه الحالة عدد طبيعي)، ويشير U إلى معامل الاجتماع المنطقي.
وفيما يلي معاني هذه العمليات:
codice_6
codice_7
codice_8
codice_9
codice_10
codice_11
أبسط طريقة لتعريف المكدس هي استخدام المصفوفة في تمثيل المكدس، سوف نصرح عن المكدس كما في حالة التصريح عن المسجل بلغة الباسكال :
من التصريحات المعطاة نجد أن عناصر المكدس codice_12 الموجودة في المصفوفة codice_13 هي أعداد صحيحة وأن المكدس لن يحتوي على من أكثر من codice_14 عنصر، ويمكن تغيير عناصر المكدس بتغيير نوع عناصر المصفوفة codice_13.بما أن codice_16 هو حقل في المسجل codice_17 فإن قيمة المؤشر الذي يدل على عنصر القمة هو codice_18. إذا كانت قيمة codice_19 فهذا يدل على أن المكدس يحتوي على ثلاثة عناصر هي و و.
إذا طبقنا عملية pop على المكدس فإن قيمة codice_18 يجب أن تعدل لتصبح مساوية 2 ويصبح عنصر القمة هو codice_21، بينما إذا طبقنا عملية codice_22 على المكدس فإن قيمة codice_18 يجب أن تعدل لتصبح مساوية 4 ويصبح عنصر القمة هو codice_24. للبدء بمكدس فارغ يجب أن نكتب : codice_25.
بالاعتماد على ما سبق يمكن كتاية التابع codice_26 بلغة الباسكال كما يلي:
ويمكن استدعاء هذا التابع بالشكل :
ينفذ التابع codice_27 الذي يأخذ بعين الاعتبار حالة كون المكدس فارغ كما يلي:
ويكتب هذا التابع بلغة الباسكال كما يلي :
يتم ادخال عنصر إلى المكدس عن طريق زيادة s.top بمقدار 1 ومن ثم إدخال x إلى المصفوفة s.item. يُكتب الإجراء الذي يقوم بذلك على الشكل التالي:
قبل استدعاء الاجراء push يجب التأكد من أن المكدس غير ممتلئ وبالتالي يجب تعديل الجراء السابق بحيث يصبح كالآتي: