Stack

 

يعرف المكدس (بالإنجليزية: Stack) بأنه بنية معطيات مجردة أو مجموعة يمكن فيها القيام بعمليات محددة على العناصر وهي إضافة عنصر جديد إلى المجموعة (تعرف هذه العملية بالدفع (بالإنجليزية: Push)) وإزالة عنصر من المجموعة (تعرف هذه العملية بالطرح (بالإنجليزية: Pop)) . 

تجعل عمليتا الدفع والطرح المكدس بنية معطيات تتمتع بخاصية من يدخل أخيراً يخرج أولاً (بالإنجليزية: Last-In-First-Out) أو اختصاراً LIFO. في بنية المعطيات ذات الخاصية LIFO يكون آخر عنصر تم إضافته للمجموعة هو أول عنصر تتم إزالته منها. يعرف المكدس بأنه بنية معطيات متسلسلة تتم فيها عمليات الإضافة والحذف عند نهاية واحدة فقط من السلسلة . 

عادةً ما يشار إلى آخر عنصر تمت إضافته إلى المكدس باسم قمة (بالإنجليزية: Top) المكدس كما يزود المكدس بعملية  استراق (بالإنجليزية: Peek) تمكن من معرفة قيمة قمة المكدس دون القيام بإزالته منه .


للمكدس سعة محدودة . 

فإذا كان المكدس ممتلئاً لا يمكن عندئذ القيام بعملية دفع عنصر إليه، وتسبب محاولة القيام بهذه العملية حصول
طفحان (أو ما يعرف بتجاوز الحد الأعلى للسعة (بالإنجليزية: Overflow)) . تقوم عملية الطرح بإزالة قمة المكدس وتسبب إما الكشف عن العناصر الموجودة داخل المكدس بالتتابع أو الحصول على مكدس فارغ ، إذا كان المكدس فارغاً فإن محاولة القيام بالطرح يسبب حصول تجاوز الحد الأدنى للسعة (بالإنجليزية: Underflow) .


يعرف المكدس أيضاً بأنه بنية معطيات مقيدة، يعود السبب في ذلك إلى وجود عدد قليل نسبياً من العمليات التي يمكن إجراؤها عليه. كما أن طبيعة عمليات الدفع والطرح تفرض ترتيباً طبيعياً على العناصر. ذلك أن ترتيب حذف العناصر من المكدس يعاكس تماماً ترتيب إضافتها إليه . وبالتالي فإن العناصر الموجودة "أسفل" المكدس ستبقى فترةً أطول من نظيرتها الموجودة بالقرب من قمة المكدس .