مكدس

تعريف المكدس :

المكدس : هو مجموعة مرتبة من العناصر حيث يمكن سحب أو ادخال عناصر جديدة من نهاية واحدة تدعى قمة المكدس . ويبين الشكل (1) Stack يحتوي على ثلاثة عناصر هي A ، B ، C وعنصر قمة المكدس هو C .

وهذا يبين الخاصية الهامة للمكدس وهي أن العنصر المدخل أخيراً إلى المكدس هو العنصر المسحوب أولاً من المكدس لهذا السبب يدعى المكدس أحياناً بلائحة LIFO .

العمليات الأساسية على المكدس :

بفرض أنه لدينا المكدس s والعنصر I عندئذ :

• العملية PUSH هي إضافة عنصر إلى المكدس وبشكل عام نكتب :

(Push (s,i

• العملية POP هي سحب عنصر من قمة المكدس وبشكل عام نكتب :

(I:=pop(s

ملاحظة : لايمكن إجراء عملية POP على مكدس فارغ لا يحتوي أية عناصر لذلك وقبل تطبيق عملية POP يجب أن نتأكد من أن المكدس ليس فارغاً بواسطة العملية EMPTY . الشكل العام لهذه العملية التي تحدد فيما اذا كان المكدس فارغا أم لا هو (empty (s هذه العملية تعطي قيمة true اذا كان المكدس فارغا وإلا تعطي قيمة false . هناك عملية أخرى على المكدس وهي stacktop وهي عملية تحدد قيمة العنصر الموجود في قمة المكدس دون سحبه من المكدس والشكل العام لهذه التعليمة :

(i:=stacktop (s

العملية السابقة تعد عملية مركبة ويمكن تحليلها إلى عمليتين :

(I:=pop (s

Push(s,i

نلاحظ أن التعليمة stacktop لا يمكن تطبيقها على المكدس الفارغ أيضا إذا تم تطبيق العمليتين pop ، stacktop على مكدس فارغ نحصل على ما يسمى بالجفاف ولتجنب الدخول في حالة جفاف يجب أن نضمن بأن قيمة (empty (s تساوي false قبل تطبيق عملية pop أو stacktop .

تمثيل المكدس بلغة الباسكال :

أبسط طريقة لتعريف المكدس هي استخدام المصفوفة في تمثيل المكدس ، سوف نصرح عن المكدس كما في حالة التصريح عن المسجل بلغة الباسكال :

Const maxstack = 100
Type stack = record
Item : array [1..maxstack] of integer;
Top : 0..maxstack
End;
Var s:stack من التصريحات المعطاة نجد أن عناصر المكدس s الموجودة في المصفوفة s.item هي أعداد صحيحة وأن المكدس لن يحتوي على من أكثر من maxstack عنصر ، ويمكن تغيير عناصر المكدس بتغيير نوع عناصر المصفوفة s.item .بما أن top هو حقل في المسجل stack فإن قيمة المؤشر الذي يدل على عنصر القمة هو s.top . اذا كانت قيمة s.top = 3 فهذا يدل على أن المكدس يحتوي على ثلاثة عناصر هي : [s.item[1] ، s.item[2] ، s.item[3 . إذا طبقنا عملية pop على المكدس فإن قيمة s.top يجب أن تعدل لتصبح مساوية 2 ويصبح عنصر القمة هو [s.item[2 ، بينما إذا طبقنا عملية push على المكدس فإن قيمة s.top يجب أن تعدل لتصبح مساوية 4 ويصبح عنصر القمة هو [s.item[4 . للبدء بمكدس فارغ يجب أن نكتب : s.top=0 . بالاعتماد على ما سبق يمكن كتاية التابع (empty(s بلغة الباسكال كما يلي:

Function empty(s:stack) : Boolean;
Begin
If s.stop = 0
Then empty:=true
Else empty:=false
End

ويمكن استدعاء هذا التابع بالشكل :

If empty(s)
Then {stack is empty}

Else{stack is not empty}

تحقيق العملية POP :

ينفذ التابع (pop(s الذي يأخذ بعين الاعتبار حالة الجفاف للمكدس ما يلي:

• إذا كان المكدس فارغاً فإنه يطبع رسالة تدل على الخطأ.
• وإلا يتم سحب عنصر القمة من المكدس وإعطاء هذا العنصر إلى البرنامج المستدعي .

ويكتب هذا التابع بلغة الباسكال كما يلي :
Function pop (var s:stack):integer
Begin
If empty(s)
Then error('stack underflow')
Else begin
Pop:=s.item[s.top]
s.top:=s.top - 1
end { else begin}
end {function pop

ولاستدعاء هذا التابع نكتب التصريح التالي :

Var x:integer

لكي يتوافق مع النتيجة التي يعطيها التابع pop ، ومن ثم نكتب :

(X:=pop(s

وبالتالي فإن x تأخذ قيمة العنصر الذي تم سحبه من قمة المكدس .

تحقيق العملية PUSH :

يتم ادخال عنصر إلى المكدس عن طريق زيادة s.top بمقدار 1 ومن ثم إدخال x إلى المصفوفة s.item . يُكتب الإجراء الذي يقوم بذلك على الشكل التالي :
(Procedure push (var s:stack;x:integer
Begin
s.top:=s.top + 1

s.item[s.top]:=x

end
قبل استدعاء الاجراء push يجب التأكد من أن المكدس[غير ممتلئ] وبالتالي يجب تعديل الجراء السابق بحيث يصبح كالآتي:

Procedure push (var s:stack;x:integer)
Begin
If s.top=maxstack
Then error('stack overflow')
Else begin
s.top:=s.top + 1
s.item[s.top]:=x
end{else begin}
end{procedure push

راجع أيضاً :

http://www.nist.gov/dads/HTML/stack.html
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html