مكدس (بنية بيانات)

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Simple representation of a stack

المكدس 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}

مثال للمكدس بالسي[عدل]

#include<stdio.h>
#include<stdlib.h>
 
typedef struct _StackObject {
    int stack_top;
    int *stack;
} StackObject;
 
int stack_init(StackObject *object, int size);
int stack_destroy(StackObject *object);
void stack_push(StackObject *object, int value);
int stack_pop(StackObject *object);
void stack_inverse(StackObject *object);
 
int main(int argc, char **argv) {
 
    StackObject stack;
    stack_init(&stack, 10);
 
    stack_push(&stack, 11);
    stack_push(&stack, 22);
    stack_push(&stack, 33);
 
    printf("1- %d\n", stack_pop(&stack));
    printf("2- %d\n", stack_pop(&stack));
    printf("3- %d\n", stack_pop(&stack));
 
    stack_push(&stack, 11);
    stack_push(&stack, 22);
    stack_push(&stack, 33);
 
    stack_inverse(&stack);
 
    printf("1- %d\n", stack_pop(&stack));
    printf("2- %d\n", stack_pop(&stack));
    printf("3- %d\n", stack_pop(&stack));
 
    stack_destroy(&stack);
    return(0);
}
 
int stack_init(StackObject *object, int size) {
    object->stack_top   = -1;
    object->stack       = (int *) malloc(sizeof(int) * size);
 
    if(object->stack == NULL)
        return(-1);
 
    return(0);
}
 
int stack_destroy(StackObject *object) {
    free(object->stack);
    return(0);
}
 
void stack_push(StackObject *object, int value) {
    object->stack_top   = object->stack_top++;
    object->stack[object->stack_top]    = value;
}
 
int stack_pop(StackObject *object) {
    int temp    = object->stack[object->stack_top];
    object->stack_top   = object->stack_top--;
    return(temp);
}
 
void stack_inverse(StackObject *object) {
    int first   = object->stack[0];
    int last    = object->stack[object->stack_top];
 
    object->stack[0]                    = last;
    object->stack[object->stack_top]    = first;
 
    int i;
    for(i = 1 ; i < object->stack_top ; i++)
        object->stack[object->stack_top - i] = object->stack[i];
}

مثال آخــر بسيط للمكدس بالسي + +[عدل]

#include <stack>
#include <iostream>
 
using namespace std;
 
int main () {
stack <int> a;
int j;
while (1){
cin>>j;
a.push(j);
if (j==0) break;
}
cout<<endl<<"how many elements you wish to delete ? ";
cin>>j;
cout<<endl<<"the last element was "<<a.top();
cout<<endl<<"after the delete ";
for (int i=1;i<=j;i++){
a.pop();
}
cout<<a.top();
return 0;
}

تحقيق العملية 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