https://virgool.ir/feed/@abolfazl.vlofa2026-11-11 13:50:26https://files.virgool.ir/upload/users/1336668/avatar/La57Ji.jpeghttps://virgool.ir/@abolfazl.vlohttps://virgool.ir/@abolfazl.vlo/توضیح-و-پیاده-سازی-پشته-stack-rjqy9spz284hپشته یک ساختار داده خطی است که از ترتیب خاصی پیروی می کند که در آن عملیات انجام می شود. سفارش ممکن است LIFO اختصاری برای عبارتLast-in-first-out است یعنی ورودی-آخر- خروجی-اول یا FILO ورودی اول آخرین خروج باشد. در اصطلاح‌شناسی پشته عملیات درج به نام عملیات PUSH نامیده و عملیات حذف به نام POP خوانده می‌شود.دو عمل اول ابتدایی پشته ممکن است شامل راه اندازی اولیه پشته استفاده و تخریب باشید . علاوه بر آن وقتی عنصری در پشته قرار می‌گیرد، معمولاً از این دو عملیات ابتدایی استفاده می‌شود :عمل push: ذخیره سازی یک عنصر پشته.عمل pop: حذف (دسترسی به) یک عنصر پشته.برای اینکه از پشته استفاده بهینه کنیم باید اول وضعیت آن را بررسی کنیم. به همین خاطر چند کارکرد به پشته می توان اضافه کرد:دریافت بالاترین عنصر پشته بدون حذف آن: Peekبررسی پر بودن پشته که در صورت پر بودن یک شرط Overflow است: isFullبررسی خالی بودن پشته (اگر پشته خالی باشد مقدار true می دهد و یک شرط Underflow است و در غیر این صورت false بر می گرداند.): isEmptyعملیات Pushفرایند قرار دادن یک عنصر جدید در پشته به نام عملیات push شناخته می‌شود.این عملیات شامل چندمرحله است:باید بررسی کنیم که پشته پر است یا خیر.اگر پر باشد ، خطا داده و خارج می شود.اگر پشته ما پر نباشد، مقدار top رو یک واحد بیشتر می کنیم تا به فضای خالی بعدی اضافه شود.عنصر داده ای را در صورت پر نبودن در پشته اضافه میکنیم.عملیات POPدسترسی به محتوای پشته در هنگام حذف آن، به نام عملیات pop شناخته می‌شود. در پیاده‌سازی آرایه‌ای از عملیات ()pop، عنصر داده‌ای واقعاً حذف نمی‌شود، بلکه به جای آن مقدار top یک واحد کاهش می‌یابد تا به مقدار کمتری در پشته اشاره کند. یک عملیات pop شامل مراحل زیر است:باید بررسی کنیم که پشته خالی است یا خیر.اگر خالی باشد ، خطا داده و خارج می شود.اگر پشته ما خالی نباشد، عنصر داده ای را که top مورد اشاره قرار می دهد بر می گرداند.مقدار 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<<"Stack Overflow"<<endl;    else {       top++;       stack[top]=val;    } } void pop() {    if(top<=-1)    cout<<"Stack Underflow"<<endl;    else {       cout<<"The popped element is "<< stack[top] <<endl;       top--;    } } void display() {    if(top>=0) {       cout<<"Stack elements are:"       for(int i=top; i>=0; i--)       cout<<stack[i]<<" "       cout<<endl;    } else    cout<<"Stack is empty" } int main() {    int ch, val;    cout<<"1) Push in stack"<<endl;    cout<<"2) Pop from stack"<<endl;    cout<<"3) Display stack"<<endl;    cout<<"4) Exit"<<endl;    do {       cout<<"Enter choice: "<<endl;       cin>>ch;       switch(ch) {          case 1: {             cout<<"Enter value to be pushed:"<<endl;             cin>>val;             push(val);             break;          }          case 2: {             pop();             break;          }          case 3: {             display();             break;          }          case 4: {             cout<<"Exit"<<endl;             break;          }          default: {             cout<<"Invalid Choice"<<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<<"Stack Overflow"<<endl;    else {       top++;       stack[top]=val;    } }همانطور که در زیر می بینید تابع pop مقدار بالایی در پشته را pop می کند و اگر پشته خالی باشد underflow پرینت می شود:void pop() {    if(top<=-1)    cout<<"Stack Underflow"<<endl;    else {       cout<<"The popped element is "<< stack[top] <<endl;       top--;    } }تابع display تمام مقادیر پشته را نمایش می دهد. برای اینکار از حلقه for استفاده می کند و اگر پشته خالی باشد stack is empty پرینت می شود:void display() {    if(top>=0) {       cout<<"Stack elements are:"       for(int i=top; i>=0; i--)       cout<<stack[i]<<" "       cout<<endl;    }else    cout<<"Stack is empty" }تابع main انتخاب هایی در اختیار کاربر قرار می دهد که آیا او می خواد عمل push, pop یا display را در پشته انجام دهد. با توجه به پاسخ کاربر تابع مناسب با استفاده از switch صدا زده می شود. اگر کاربر پاسخی ناموجود یا غیر تعریف شده بدهد invalid choice پرینت می شود:int main() {    int ch, val;    cout<<"1) Push in stack"<<endl;    cout<<"2) Pop from stack"<<endl;    cout<<"3) Display stack"<<endl;    cout<<"4) Exit"<<endl;    do {       cout<<"Enter choice: "<<endl;       cin>>ch;       switch(ch) {          case 1: {             cout<<"Enter value to be pushed:"<<endl;             cin>>val;             push(val);             break;          }          case 2: {             pop();             break;          }          case 3: {             display();             break;          }          case 4: {             cout<<"Exit"<<endl;             break;          }          default: {             cout<<"Invalid Choice"<<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-rxxmrjmslyithttps://blog.faradars.org/stack-expression-parsing-queue/https://www.geeksforgeeks.org/stack-data-structure-introduction-program/https://youtu.be/08QSylWv6jMhttps://www.tutorialspoint.com/cplusplus-program-to-implement-stack-using-arrayhttps://cse.buffalo.edu/~shapiro/Courses/CSE116/notes10.htmlابوالفضل ولی الهیابوالفضل ولی الهیFri, 08 Apr 2022 23:53:55 +0430