توضیح و پیاده سازی پشته (Stack)

پشته یک ساختار داده خطی است که از ترتیب خاصی پیروی می کند که در آن عملیات انجام می شود. سفارش ممکن است LIFO اختصاری برای عبارتLast-in-first-out است یعنی ورودی-آخر- خروجی-اول یا FILO ورودی اول آخرین خروج باشد. در اصطلاح‌شناسی پشته عملیات درج به نام عملیات PUSH نامیده و عملیات حذف به نام POP خوانده می‌شود.

دو عمل اول ابتدایی پشته ممکن است شامل راه اندازی اولیه پشته استفاده و تخریب باشید . علاوه بر آن وقتی عنصری در پشته قرار می‌گیرد، معمولاً از این دو عملیات ابتدایی استفاده می‌شود :

• عمل push: ذخیره سازی یک عنصر پشته.
• عمل pop: حذف (دسترسی به) یک عنصر پشته.

برای اینکه از پشته استفاده بهینه کنیم باید اول وضعیت آن را بررسی کنیم. به همین خاطر چند کارکرد به پشته می توان اضافه کرد:

• دریافت بالاترین عنصر پشته بدون حذف آن: Peek
• بررسی پر بودن پشته که در صورت پر بودن یک شرط Overflow است: isFull
• بررسی خالی بودن پشته (اگر پشته خالی باشد مقدار true می دهد و یک شرط Underflow است و در غیر این صورت false بر می گرداند.): isEmpty

عملیات Push

فرایند قرار دادن یک عنصر جدید در پشته به نام عملیات push شناخته می‌شود.این عملیات شامل چندمرحله است:

1. باید بررسی کنیم که پشته پر است یا خیر.
2. اگر پر باشد ، خطا داده و خارج می شود.
3. اگر پشته ما پر نباشد، مقدار top رو یک واحد بیشتر می کنیم تا به فضای خالی بعدی اضافه شود.
4. عنصر داده ای را در صورت پر نبودن در پشته اضافه میکنیم.

عملیات POP

دسترسی به محتوای پشته در هنگام حذف آن، به نام عملیات pop شناخته می‌شود. در پیاده‌سازی آرایه‌ای از عملیات ()pop، عنصر داده‌ای واقعاً حذف نمی‌شود، بلکه به جای آن مقدار top یک واحد کاهش می‌یابد تا به مقدار کمتری در پشته اشاره کند. یک عملیات pop شامل مراحل زیر است:

1. باید بررسی کنیم که پشته خالی است یا خیر.
2. اگر خالی باشد ، خطا داده و خارج می شود.
3. اگر پشته ما خالی نباشد، عنصر داده ای را که top مورد اشاره قرار می دهد بر می گرداند.
4. مقدار top را یک واحد کم کن.

صف

مانند (پشته) Stack، (صف) Queue یک ساختار خطی است که از ترتیب خاصی پیروی می کند که در آن عملیات انجام می شود. ترتیب اولین خروجی FIFO (اولین ورودی اولین خروجی) است. یک مثال خوب از صف، هر صف مصرف کننده برای منبعی است که در آن مصرف کننده ای که اول شده است، ابتدا خدمات می دهد.

صف یک ساختار داده است که تا حدودی شبیه پشته محسوب می‌شود؛ اما بر خلاف پشته، صف از هر دو سمت باز است. از یک سمت همواره برای درج داده‌ها و از سمت دیگر برای حذف داده‌ها استفاده می‌شود. در روش FIFO هر داده‌های که اول در صف ذخیره شود، هنگام خروج نیز قبل از همه خارج می‌شود.

تفاوت بین پشته ها و صف ها در حذف است. در یک پشته، آیتمی را که اخیراً اضافه شده است حذف می کنیم. در یک صف، موردی را که اخیراً کمترین اضافه شده است حذف می کنیم.

عملیات در صف

به طور عمده چهار عملیات اساسی زیر در صف انجام می شود:

• عمل enqueue: یک مورد را به صف اضافه می کند. اگر صف پر باشد، گفته می شود که یک شرط Overflow است.
• عمل dequeue: یک مورد را از صف حذف می کند. آیتم ها به همان ترتیبی که فشار داده می شوند ظاهر می شوند. اگر صف خالی باشد، گفته می شود که یک شرط Underflow است.
• جلو (Front): آیتم جلویی را از صف دریافت کنید.
• عقب(Rear): آخرین مورد را از صف دریافت کنید.

کاربرد پشته (stack)

در زندگی واقعی و روزمره:

• قرار گیری سینی ها روی هم در رستوران ها
• در یک پارکینگ که عرض آن اندازه یک ماشین است. اولین ماشینی که وارد شده آخرین خارج می شود.

در دنیای کامپیوتر:

• عملگرد forward و backward در جستجوگرها
• عملگرد undo و redo در نرم افزارهای Word و Excel
• در تاریخچه تماس برای پیدا کردن اولین نفری که تماس گرفته باید به پایین صفحه اسکرول کنیم.

کاربرد صف (queues)

در زندگی روزمره و واقعی:

• صف بلیط سینما
• در پله برقی
• در کارواش

در دنیای کامپیوتر:

• صف پرینت: اولین صفحه زودتر چاپ می شود
• صف در روترها و سوییچ ها

پیاده سازی پشته (stack)

کد cpp:

#include <iostream>
using namespace std;
int stack[100], n=100, top=-1;
void push(int val) {
   if(top>=n-1)
   cout<<&quotStack Overflow&quot<<endl;
   else {
      top++;
      stack[top]=val;
   }
}
void pop() {
   if(top<=-1)
   cout<<&quotStack Underflow&quot<<endl;
   else {
      cout<<&quotThe popped element is &quot<< stack[top] <<endl;
      top--;
   }
}
void display() {
   if(top>=0) {
      cout<<&quotStack elements are:&quot
      for(int i=top; i>=0; i--)
      cout<<stack[i]<<&quot &quot
      cout<<endl;
   } else
   cout<<&quotStack is empty&quot
}
int main() {
   int ch, val;
   cout<<&quot1) Push in stack&quot<<endl;
   cout<<&quot2) Pop from stack&quot<<endl;
   cout<<&quot3) Display stack&quot<<endl;
   cout<<&quot4) Exit&quot<<endl;
   do {
      cout<<&quotEnter choice: &quot<<endl;
      cin>>ch;
      switch(ch) {
         case 1: {
            cout<<&quotEnter value to be pushed:&quot<<endl;
            cin>>val;
            push(val);
            break;
         }
         case 2: {
            pop();
            break;
         }
         case 3: {
            display();
            break;
         }
         case 4: {
            cout<<&quotExit&quot<<endl;
            break;
         }
         default: {
            cout<<&quotInvalid Choice&quot<<endl;
         }
      }
   }while(ch!=4);
   return 0;
}

خروجی:

1) Push in stack
2) Pop from stack
3) Display stack
4) Exit

Enter choice: 1
Enter value to be pushed: 2
Enter choice: 1
Enter value to be pushed: 6
Enter choice: 1
Enter value to be pushed: 8
Enter choice: 1
Enter value to be pushed: 7
Enter choice: 2
The popped element is 7
Enter choice: 3
Stack elements are:8 6 2
Enter choice: 5
Invalid Choice
Enter choice: 4
Exit

در برنامه بالا تابع push مقدار آرگومان را می گیرد و وارد پشته می کند. اگر top بزرگتر یا مساوی با n بود یعنی هیچ جایی در استک باقی نمانده و overflow پرینت می شود. در ادامه می توانید ببینید:

void push(int val) {
   if(top>=n-1)
   cout<<&quotStack Overflow&quot<<endl;
   else {
      top++;
      stack[top]=val;
   }
}

همانطور که در زیر می بینید تابع pop مقدار بالایی در پشته را pop می کند و اگر پشته خالی باشد underflow پرینت می شود:

void pop() {
   if(top<=-1)
   cout<<&quotStack Underflow&quot<<endl;
   else {
      cout<<&quotThe popped element is &quot<< stack[top] <<endl;
      top--;
   }
}

تابع display تمام مقادیر پشته را نمایش می دهد. برای اینکار از حلقه for استفاده می کند و اگر پشته خالی باشد stack is empty پرینت می شود:

void display() {
   if(top>=0) {
      cout<<&quotStack elements are:&quot
      for(int i=top; i>=0; i--)
      cout<<stack[i]<<&quot &quot
      cout<<endl;
   }else
   cout<<&quotStack is empty&quot
}

تابع main انتخاب هایی در اختیار کاربر قرار می دهد که آیا او می خواد عمل push, pop یا display را در پشته انجام دهد. با توجه به پاسخ کاربر تابع مناسب با استفاده از switch صدا زده می شود. اگر کاربر پاسخی ناموجود یا غیر تعریف شده بدهد invalid choice پرینت می شود:

int main() {
   int ch, val;
   cout<<&quot1) Push in stack&quot<<endl;
   cout<<&quot2) Pop from stack&quot<<endl;
   cout<<&quot3) Display stack&quot<<endl;
   cout<<&quot4) Exit&quot<<endl;
   do {
      cout<<&quotEnter choice: &quot<<endl;
      cin>>ch;
      switch(ch) {
         case 1: {
            cout<<&quotEnter value to be pushed:&quot<<endl;
            cin>>val;
            push(val);
            break;
         }
         case 2: {
            pop();
            break;
         }
         case 3: {
            display();
            break;
         }
         case 4: {
            cout<<&quotExit&quot<<endl;
            break;
         }
         default: {
            cout<<&quotInvalid Choice&quot<<endl;
         }
      }
   }while(ch!=4);
   return 0;
}

گردآورندگان:

• علی قاسمی
• حسین قربانی
• سروش زندی
• مهدی نظری
• ابوالفضل ولی الهی
• یاشار مرتاضی

استاد: دکتر مریم حاجی اسمعیلی. دکترای علوم کامپیوتر از دانشگاه کینگستون لندن. Linkedin

منابع:

• https://virgool.io/@farzadshami/%DA%A9%D9%85%DB%8C-%D8%B3%D8%A7%D8%AE%D8%AA%D9%85%D8%A7%D9%86-%D8%AF%D8%A7%D8%AF%D9%87-maze-rxxmrjmslyit
• https://blog.faradars.org/stack-expression-parsing-queue/
• https://www.geeksforgeeks.org/stack-data-structure-introduction-program/
• https://youtu.be/08QSylWv6jM
• https://www.tutorialspoint.com/cplusplus-program-to-implement-stack-using-array
• https://cse.buffalo.edu/~shapiro/Courses/CSE116/notes10.html