مقدمة
المكدس بنية بيانات خطية، وهي مجموعة من العناصر من نفس النوع. في المكدس، تتم عملية إدخال العناصر وإخراجها عند نقطة نهاية واحدة فقط. يُوصف سلوك المكدس بأنه "آخر ما يدخل، أول ما يخرج" (LIFO). عند "دفع" عنصر إلى المكدس، يكون أول ما يُخرج منه. للوصول إلى أقدم عنصر مُدرج، يجب إزالة جميع العناصر السابقة.
في هذه المقالة سوف تتعلم عن مفهوم بنية بيانات المكدس وتنفيذها باستخدام المصفوفات في C.
العمليات التي يتم إجراؤها على Stacks
فيما يلي العمليات الأساسية التي توفرها Stacks.
- دفع: إضافة عنصر إلى أعلى المكدس.
- pop: يقوم بإزالة العنصر الأعلى من المكدس.
- isEmpty: التحقق مما إذا كانت المكدس فارغًا.
- isFull: التحقق مما إذا كانت المكدس ممتلئة أم لا.
- أعلى: يعرض العنصر الأعلى في المكدس.
الآليات الأساسية للمكدسات
في البداية، يتم ضبط مؤشر (أعلى) لتتبع العنصر الأعلى في المكدس. يتم تهيئة المكدس إلى -1.
بعد ذلك، يتم التحقق من خلو المكدس من خلال مقارنة top و-1.
عند إضافة عناصر إلى المكدس، يتم تحديث الموضع العلوي.
بمجرد ظهور العناصر أو حذفها، تتم إزالة العنصر الأعلى وتحديث الموضع العلوي.
تنفيذ المكدس في C
يمكن تمثيل STACKS باستخدام الهياكل أو المؤشرات أو المصفوفات أو القوائم المرتبطة.
يقوم هذا المثال بتنفيذ المكدسات باستخدام المصفوفات في C:
#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
int top = -1, inp_array[SIZE];
void push();
void pop();
void show();
int main()
{
int choice;
while (1)
{
printf("\nPerform operations on the stack:");
printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
printf("\n\nEnter the choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
show();
break;
case 4:
exit(0);
default:
printf("\nInvalid choice!!");
}
}
}
void push()
{
int x;
if (top == SIZE - 1)
{
printf("\nOverflow!!");
}
else
{
printf("\nEnter the element to be added onto the stack: ");
scanf("%d", &x);
top = top + 1;
inp_array[top] = x;
}
}
void pop()
{
if (top == -1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nPopped element: %d", inp_array[top]);
top = top - 1;
}
}
void show()
{
if (top == -1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nElements present in the stack: \n");
for (int i = top; i >= 0; --i)
printf("%d\n", inp_array[i]);
}
}يقدم هذا البرنامج للمستخدم أربعة خيارات:
- دفع عنصر
- تفجير عنصر
- يعرض
- نهاية
ينتظر المستخدم لإدخال رقم.
- إذا اختار المستخدم 1، يُجري البرنامج عملية push(). يتحقق أولاً مما إذا كان top يساوي SIZE - 1. إذا كانت القيمة صحيحة، فسيتم عرض "Overflow!!". وإلا، يُطلب من المستخدم توفير عنصر جديد لإضافته إلى المكدس.
- إذا اختار المستخدم ٢، يُجري البرنامج دالة pop(). يتحقق أولاً مما إذا كانت قيمة top تساوي -١. إذا كانت القيمة صحيحة، فسيتم عرض "Underflow!!". وإلا، يُحذف العنصر top ويُخرج البرنامج المكدس الناتج.
- إذا اختار المستخدم 3، يُجري البرنامج دالة show(). يتحقق أولاً مما إذا كانت القيمة top تساوي -1. إذا كانت القيمة صحيحة، فسيتم عرض "Underflow!!". وإلا، يُخرج البرنامج المكدس الناتج.
- إذا اختار المستخدم 4، يخرج البرنامج.
قم بتشغيل هذا الكود لدفع الرقم "10" إلى المكدس:
Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 1
Enter the element to be inserted onto the stack: 10ثم قم بإظهار العناصر في Stack():
Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Elements present in the stack:
10ثم pop():
Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 2
الآن، المكدس فارغ. جرّب Pop() مرة أخرى:
Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Underflow!! Your code... */واصل تجربة هذا البرنامج لفهم كيفية عمل المكدس.
التعقيد الزمني لعمليات المكدس
لا يمكن الوصول إلا إلى عنصر واحد في كل مرة في المكدسات.
أثناء إجراء عمليات push() و pop() على المكدس، يستغرق الأمر وقتًا قدره O(1).
نتيجة
في هذه المقالة، تعلمت عن مفهوم بنية بيانات المكدس وتنفيذها باستخدام المصفوفات في C.
