مقدمه
Stack یک ساختار داده خطی است، مجموعه ای از موارد از همان نوع.در یک Stack، درج و حذف عناصر فقط در یک نقطه پایانی اتفاق می افتد. رفتار یک Stack به عنوان “آخرین ورود، اولین خروج” (LIFO) توصیف می شود. هنگامی که یک عنصر بر روی پشته “PUSHED” می شود، اولین موردی است که از پشته “پاپ” می شود. برای رسیدن به قدیمی ترین آیتم وارد شده، باید تمام آیتم های قبلی را باز کنید.
در این مقاله با مفهوم ساختار داده پشته و پیاده سازی آن با استفاده از آرایه ها در C آشنا خواهید شد.
عملیات انجام شده بر روی Stacks
در زیر عملیات اساسی ارائه شده توسط Stacks آمده است.
- push: یک عنصر را به بالای پشته اضافه می کند.
- pop: بالاترین عنصر را از پشته حذف می کند.
- isEmpty: خالی بودن پشته را بررسی می کند.
- isFull: بررسی می کند که آیا پشته پر است یا خیر.
- top: بالاترین عنصر پشته را نمایش می دهد.
مکانیک زیربنایی Stacks
در ابتدا، یک اشاره گر (بالا) برای پیگیری بالاترین آیتم در پشته تنظیم شده است. پشته به -1 مقداردهی اولیه می شود.
سپس، بررسی خالی بودن پشته با مقایسه top و -1 انجام می شود.
با اضافه شدن عناصر به پشته، موقعیت بالا به روز می شود.
به محض پاپ یا حذف عناصر، بالاترین عنصر حذف می شود و موقعیت بالا به روز می شود.
پیاده سازی Stack در 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]);
}
}این برنامه چهار گزینه را در اختیار کاربر قرار می دهد:
- Push دادن المنت
- pop کردن المنت
- Show
- End
منتظر می ماند تا کاربر عددی را وارد کند.
- اگر کاربر 1 را انتخاب کند، برنامه یک push(). ابتدا بررسی می کند که آیا بالا معادل SIZE – 1 است یا خیر. اگر درست است، “سرریز!!” نمایش داده می شود. در غیر این صورت، از کاربر خواسته می شود تا عنصر جدید را برای افزودن به پشته ارائه دهد.
- اگر کاربر 2 را انتخاب کند، برنامه یک pop() را مدیریت می کند. ابتدا بررسی می کند که آیا top معادل ۱- است یا خیر. اگر درست است، “Underflow!!” نمایش داده می شود. در غیر این صورت، بالاترین عنصر حذف می شود و برنامه پشته حاصل را خروجی می دهد.
- اگر کاربر 3 را انتخاب کند، برنامه یک show() را مدیریت می کند. ابتدا بررسی می کند که آیا top معادل ۱- است یا خیر. اگر درست است، “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 آشنا شدید.
