پشته Stack

پشته یا Stack چیست؟

پشته (Stack) در علوم رایانه، به ساختمان داده‌ای گفته می‌شود که مجموعه‌ای از المان‌ها را براساس اصل LIFO (اولویت خروج با عناصر تازه وارد) در خود نگه‌داری می‌کند و از دو عمل Push (برای افزودن آیتم) و Pop (برای حذف آیتم) پشتیبانی می‌کند.

اعمال افزودن و حذف در Stack را می‌توان مشابه وضعیت ظروف کثیفی در نظر گرفت که به منظور شسته شدن در آشپزخانه روی یکدیگر انباشته شده‌اند، عنصر (ظرف کثیف) جدید بر روی عناصر قبلی قرار می‌گیرد و هنگام حذف یک عنصر (برداشتن ظرف برای شسته شدن)، جدیدترین عنصری که به پشته اضافه شده است زودتر حذف می‌شود. از این رو به پشته، ساختمان داده‌ی LIFO نیز گفته می‌شود.

کاربرد پشته‌ها و نحوه‌ی پیاده‌سازی

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

می‌توان استک را با ظرفیت ثابت (Fixed) و یا به صورت پویا (Dynamic) پیاده‌سازی نمود. در حالت اول، تعداد بیشینه‌ی المان‌هایی که می‌تواند در استک قرار بگیرد ثابت می‌باشد، در صورتی که پشته پر باشد و بخواهیم عنصر جدیدی به آن اضافه کنیم حالتی به نام سرریز (Overflow) رخ می‌دهد. به طور مشابه در صورتی که بخواهیم روی یک پشته‌ی خالی، عمل Pop را انجام دهیم حالت زیرریز (Underflow) رخ خواهد داد. در پیاده‌سازی پویای Stack، متناسب با تعداد المان‌ها ظرفیت استک تغییر می‌کند.

با توجه به محدودیت اعمالی که روی پشته‌ها قابل انجام است، Stack در زمره‌ی ساختمان‌داده‌های محدود (Restricted) طبقه‌بندی می‌شود.