المكدسات

موضوع في مادة الكنولوجيا للصف اول ثانوي
المكدسات:
تعريفها: هي إحدى طرق تركيب البيانات التي تكون من نفس النوع.
مبدأ عملها: تتم عملية الإضافة والإزالة من طرف واحد .
من يدخل آخرا يخرج أولا LIFO.
طرق التعبير عن المكدسات
• يعبر عنها بمصفوفة أحادية .
• نحتاج إلى الإعلان عن متغير يعمل كمؤشر يشير إلى أخر عنصر موجود في المكدسة يسمى TOP ويمثل INDEX لها.
في البداية تكون قيمة TOP = -1

العمليات الممكنة عليها :
• عملية الإضافة PUSH
• عملية الحذف POP
• فحص هل المكدسة فارغة STACK EMPTY
• فحص هل المكدسة ممتلئة STACK FULL

الإضافة PUSH :
• عند القيام بعملية الإضافة لا بد من فحص المصفوفة هل هي ممتلئة أم لا .
• ملاحظة إذا كان عدد العناصر= N فإن موقع أخر عنصر= N-1
• لإضافة القيمة F :
IF TOP>=N-1 THEN
ممتلئة PRINT “OVERFLOW ”
ELSE
TOP=TOP+1
S(TOP)=F
END IF
الحذف pop :
• قبل الحذف لا بد فحص المصفوفة إذا ما كانت فارغة .
• يتم ذلك من خلال فحص قيمة TOP
IF TOP= -1 THEN
PRINT “EMPTY”
ELSE
F=S(TOP)


END IF

من أشهر التطبيقات على المكدسات :

• تستخدم لفحص التعابير الحسابية التي تحتوي على أقواس (مطابقة الأقواس).
• مثل (((5+2)*3)-1)
• المبدأ:
• قوس يسار :إضافة
• قوس يمين : إزالة
• تحليل النتيجة : 1- الانتهاء والمصفوفة (المكدسة )فارغة يكون التعبير صحيحا.
2-إذا تعرضنا لحالة إخراج pop وكانت المصفوفة فارغة
يكون عدد الأقواس اليمنى >من اليسرى.
3-الانتهاء والمصفوفة غير فارغة يكون عدد الأقواس اليسرى >من اليمنى.