تم النشر اليوم 2024/05/19 | مكدس (بنية بيانات)

تحقيق المكدس بلغة سي

#include
#include

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- %dn”, stack_pop(&stack));
printf(“2- %dn”, stack_pop(&stack));
printf(“3- %dn”, stack_pop(&stack)); stack_push(&stack, 11);
stack_push(&stack, 22);
stack_push(&stack, 33); stack_inverse(&stack); printf(“1- %dn”, stack_pop(&stack));
printf(“2- %dn”, stack_pop(&stack));
printf(“3- %dn”, 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 ;
int last = object->stack[object->stack_top]; object->stack = last;
object->stack[object->stack_top] = first; int i;
for(i = 1 ; i stack_top ; i++)
object->stack[object->stack_top – i] = object->stack[i];
}

العمليات المجردة

يعرف المكدس بأنه بنية معطيات بسيطة تتمتع بعدد من العمليات المجردة والتي يمكن تحقيقها بحرية تامة. أو يمكن تعريف المكدس بأنه قائمة خطية من العناصر التي يمكن إضافتها وحذفها عند نهاية واحدة تعرف باسم القمة. فيما يلي قائمة بتواقيع الطرق الخاصة ببنية معطيات المكدس: init: -> Stack push: N x Stack -> Stack (top: Stack -> (N U ERROR pop: Stack -> Stack isempty: Stack -> Boolean حيث يشير N إلى نمط معطيات عناصر المكدس (في هذه الحالة عدد طبيعي)، ويشير U إلى معامل الاجتماع المنطقي. وفيما يلي معاني هذه العمليات: top(init()) = ERROR top(push(i,s)) = i ()pop(init()) = init pop(push(i, s)) = s isempty(init()) = true isempty(push(i, s)) = false

استخدام المكدس بلغة سي++

#include
#include using namespace std; int main () {
stack a;
int j;
while (1){
cin>>j;
a.push(j);
if (j==0) break;
}
cout<<endl<>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;
}

تاريخ المكدس

اقترح آلان تورنغ عام 1946 بنية المعطيات المكدس لأول مرة كجزء من تصميمه للكومبيوتر كطريقة لاستدعاء والعودة من الإجراءات الفرعية (وقد استخدم مصطلحات «الدفن» (بالإنجليزية: bury)‏ و«النبش» (بالإنجليزية: unbury)‏ للإشارة إلى هذه العمليات). وقد اقترح الألمانيان كلاوس ساملسن وفريدريش باور من جامعة ميونيخ التقنية بنية المعطيات المكدس عام 1955 وتقدما بطلب براءة اختراع له. وقد اقترح الأسترالي تشارلز لينارد هامبلن المبدأ ذاته عام 1957.

تحقيق المكدس بلغة الباسكال

أبسط طريقة لتعريف المكدس هي استخدام المصفوفة في تمثيل المكدس، سوف نصرح عن المكدس كما في حالة التصريح عن المسجل بلغة الباسكال: Const maxstack = 100;
Type stack = record;
Item : array [1..maxstack] of integer;
Top : 0..maxstack;
Var s:stack من التصريحات المعطاة نجد أن عناصر المكدس s الموجودة في المصفوفة s.item هي أعداد صحيحة وأن المكدس لن يحتوي على من أكثر من maxstack عنصر، ويمكن تغيير عناصر المكدس بتغيير نوع عناصر المصفوفة s.item.بما أن top هو حقل في المسجل stack فإن قيمة المؤشر الذي يدل على عنصر القمة هو s.top. إذا كانت قيمة s.top = 3 فهذا يدل على أن المكدس يحتوي على ثلاثة عناصر هي s.item وs.item وs.item .
إذا طبقنا عملية 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 {المكدس فارغ}
Else {المكدس ليس فارغاً} تحقيق عملية الطرح
ينفذ التابع (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;
End; تحقيق عملية الدفع
يتم ادخال عنصر إلى المكدس عن طريق زيادة 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;
End;

شرح مبسط

يعرف المكدس (بالإنجليزية: Stack)‏ بأنه بنية معطيات مجردة أو مجموعة يمكن فيها القيام بعمليات محددة على العناصر وهي إضافة عنصر جديد إلى المجموعة (تعرف هذه العملية بالدفع (بالإنجليزية: Push)‏ وإزالة عنصر من المجموعة (تعرف هذه العملية بالطرح (بالإنجليزية: Pop)‏).[1][2][3] تجعل عمليتا الدفع والطرح المكدس بنية معطيات تتمتع بخاصية من يدخل أخيراً يخرج أولاً (بالإنجليزية: Last-In-First-Out)‏ أو اختصاراً LIFO. في بنية المعطيات ذات الخاصية LIFO يكون آخر عنصر تم إضافته للمجموعة هو أول عنصر تتم إزالته منها. يعرف المكدس بأنه بنية معطيات متسلسلة تتم فيها عمليات الإضافة والحذف عند نهاية واحدة فقط من السلسلة. عادةً ما يشار إلى آخر عنصر تمت إضافته إلى المكدس باسم قمة (بالإنجليزية: Top)‏ المكدس كما يزود المكدس بعملية استراق (بالإنجليزية: Peek)‏ تمكن من معرفة قيمة قمة المكدس دون القيام بإزالته منه.