مكدس
المكدس Stack : هو مجموعة مرتبة من العناصر حيث يمكن سحب أو ادخال عناصر جديدة من نهاية واحدة تدعى قمة المكدس. ويبين الشكل (1) [Stack_(data_structure) Stack] يحتوي على ثلاثة عناصر هي A، B، C وعنصر قمة المكدس هو C. لا تستغرب فان المكدس عبارة عن مصفوفة ولكن الادخال و الاخراج تكون بطريقة مختلفة ( حسب مفهوم هياكل البيانات ) .
وهذا يبين الخاصية الهامة للمكدس وهي أن العنصر المدخل أخيراً إلى المكدس هو العنصر المسحوب أولاً من المكدس لهذا السبب يدعى المكدس أحياناً بلائحة LIFO . [Last In First Out].
العمليات الأساسية على المكدس
يمكنك تصميم العمليات الاساسية حول المكدس - لمزيد من المعلومات حول تصميم هذه العمليات يمكن زيارة هذه الرابطة :-
http://fam.net84.net/talk/viewtopic.php?f=18&t=43
بفرض أنه لدينا المكدس 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 يجب التأكد من أن المكدس overflow|غير ممتلئ وبالتالي يجب تعديل الجراء السابق بحيث يصبح كالآتي:
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://fam.net84.net/talk/viewtopic.php?f=18&p=67#p67
http://www.nist.gov/dads/HTML/stack.html
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html
be-x-old:Стэк bg:Стек (структура от данни) ca:Pila (estructura de dades) cs:Zásobník (datová struktura) da:Stak (datastruktur) de:Stapelspeicher el:Στοίβα (δομή δεδομένων) Stack (abstract data type)]] es:Pila (informática) et:Pinumälu eu:Pila (informatika) fa:پشته fi:Pino fr:Pile (informatique) he:מחסנית (מבנה נתונים) hr:Stog hu:Verem (számítástechnika) id:Stack (struktur data) is:Hlaði (tölvunarfræði) it:Stack ja:スタック kk:Стек ko:스택 lb:Stack (Informatik) lt:Rietuvė lv:Steks (datu struktūra) ml:സ്റ്റാക്ക് (ഡാറ്റാ സ്ട്രക്ച്ചർ) mn:Stack nl:Stack (informatica) no:Stakk (datastruktur) pl:Stos (informatyka) pt:Pilha (informática) ro:Stivă (structură de date) ru:Стек simple:Stack (data structure) sl:Sklad (računalništvo) sq:Stack (struktura e të dhënave) sr:Стек sv:Stack (datastruktur) th:กองซ้อน tr:Yığın (bilgisayar bilimi) uk:Стек vi:Ngăn xếp zh:堆栈
