ⓘ پشته یکی از انواع داده‌ساختارها است و برای ذخیره و بازیابی داده‌ها کاربرد دارد. پشته در طراحی و پیاده‌سازی سیستم‌های نرم‌افزاری و سخت‌افزاری، فراوان به کار می‌ر ..

                                     

ⓘ پشته

پشته یکی از انواع داده‌ساختارها است و برای ذخیره و بازیابی داده‌ها کاربرد دارد. پشته در طراحی و پیاده‌سازی سیستم‌های نرم‌افزاری و سخت‌افزاری، فراوان به کار می‌رود. شیوهٔ عملکرد پشته بر اساس سیاست LIFO است.

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

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

  • Pop: که عنصر بالای پشته را حذف میکند.
  • Clear: تمام عناصر پشته را حذف میکند.
  • StackEmpty: که خالی بودن پشته را تست میکند.
  • Contains: مشخص میکند که عنصری در پشته وجود دارد یا خیر.
  • Push: که عنصری را به بالای پشته اضافه میکند.
  • Peek: که عنصر بالای پشته را بازیابی میکند ولی حذف نمیکند.
  • CopyTo: محتویات پشته را درآرایه ای از نوع شی کپی میکند.

در حقیقت پشته ، یکی از سه بخش تخصیص یافته به یک برنامه در حال اجرا در حافظه RAM می‌باشد. پس از اجرای هر برنامه کاربردی آن برنامه برای پردازش توسط پردازشگر، به سه بخش در حافظه تقسیم شده و ذخیره می‌گردد تا در دسترس پردازشگر قرار بگیرد. این سه بخش شامل موارد زیر هستند:

  • بخش کد شامل کد برنامه
  • پشته
  • بخش داده + بی‌اس‌اس + هیپ
                                     

1. FIFO و LIFO چیست؟

LIFO کوتاه‌شدهٔ عبارت Last In First Out آخرین ورودی از همه زودتر خارج می‌شود است. این سیاست اساس کار پشته‌ها را تشکیل می‌دهد و به مفهوم آن است که آخرین دادهٔ ذخیره شده در پشته، نخستین داده‌ای است که بازیابی می‌شود.

FIFO کوتاه‌شدهٔ عبارت First In First Out اولین ورودی از همه زودتر خارج می‌شود است. این سیاست اساس کار صف‌ها را تشکیل می‌دهد و به مفهوم آن است که اولین دادهٔ ذخیره شده در صف، نخستین داده‌ای نیز هست که بازیابی می‌شود.

با توجه به آنچه گفته شد، روشن است که در سیاست LIFO، ورود و خروج داده‌ها، از یک سمت صورت می‌گیرد در واقع تنها یک سمت تودهٔ داده‌ها باز است در حالی که در سیاست FIFO، ورود و خروج داده‌ها، از دو سمت صورت می‌گیرد یک سمت برای ورودی و یک سمت برای خروجی و ما به دو سر تودهٔ داده‌ها دست‌رسی خواهیم داشت یکی برای ورود و دیگری برای خروج.

                                     

2. تفاوت پشته و صف

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

3. پیاده‌سازی

پشته‌ها ممکن است با هر یک از انواع داده‌ساختارهایی مثل آرایه، لیست پیوندی و… پیاده‌سازی شوند. صرف‌نظر از این‌که از کدام‌یک استفاده می‌کنیم، پیاده‌سازی دو تابع Push برای گذاشتن داده و Pop برای برداشتن داده بسیار مهم است. نکتهٔ مهم دیگر در پیاده‌سازی پشته، نگه‌داشتن اشاره‌گری به آخرین داده است که اصطلاحاً به آن Top گفته می‌شود. اگر فرض کنیم که پشته با آرایه پیاده‌سازی شده باشد، شبه‌کد تابع‌های Push و Pop به صورت زیر خواهد بود:

                                     

4. پیچیدگی زمانی در پیاده‌سازی آرایه‌ای

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

می‌بینیم که در پیاده‌سازی آرایه‌ای، پیچیدگی زمانی افزودن و برداشتن عنصرها از پشته و به پشته، با هم متفاوت است. با این وجود اگر پشته را با لیست‌های پیوندی پیاده‌سازی کنیم، به علت ساختار خاص این لیست‌ها، هردوی این اعمال برای پشته و به همین شکل برای صف، دارای پیچیدگی زمانی از (O(1 خواهد بود.

                                     

5. چند حالت نامطلوب

هنگام پیاده‌سازی پشته، باید حالت‌های خاص زیر را هم در نظر گرفت:

  • هنگام صداکردن تابع Dequeue در صف، اگر صف خالی باشد، خطای پاریز اتفاق می‌افتد.
  • هنگام صداکردن تابع Pop در پشته‌ها، در صورتی که پشته خالی باشد، خطای پاریز رخ می‌دهد.
  • هنگام صداکردن تابع Enqueue در صف، اگر صف پر باشد، خطای سرریز رخ خواهد داد. البته این خطا در صورتی اتفاق می‌افتد که ظرفیت پشته تعیین‌شده و محدود باشد و نتوانیم آن را افزایش دهیم.
  • هنگام صداکردن تابع Push در پشته‌ها، در صورتی که پشته پر باشد، خطای سرریز رخ خواهد داد. البته این اتفاق در صورتی می‌افتد که ظرفیت پشته تعیین‌شده باشد و نتوانیم آن را افزایش دهیم. برای مثال، خطای Stack Overflow در زمانی که حافظهٔ در نظرگرفته شده برای برنامه کافی نباشد، از طرف سیستم‌عامل تولید می‌شود.
                                     

6. کاربردها

پشته‌ها در زمینه‌های بسیاری به کار می‌روند که البته در هر زمینه کارایی مشابهی هم دارند. پشته‌ها برای محاسبهٔ یک عبارت ریاضی به طوری که ابتدا عملوندها و سپس عملگرها در پشته قرار می‌گیرند، به کار می‌روند. علاوه بر این، برای مدیریت حافظهٔ موردنیاز برنامه، نگه‌داری روند فراخوانی تابع‌های مختلف در برنامه، برای پیاده‌سازی الگوریتم جستجوی عمق اول و… نیز از پشته‌ها استفاده می‌شود.

                                     

7. روند توسعه

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

  • مشابه‌سازی: با یک بار Pop کردن دو بار Push کردن بالاترین دادهٔ پشته، این داده به دو دادهٔ مشابه تبدیل می‌شود به عبارت دیگر تکثیر می‌شود.
  • جابه‌جایی کلی: همه عناصر پشته یکی به سمت پایین جابه‌جا می‌شوند و پایین‌ترین داده در جای بالاترین داده قرار می‌گیرد.
  • برداشت: بالاترین داده Pop می‌شود ولی اشاره‌گر Top تغییر نمی‌کند؛ به عبارت دیگر، داده به دست ما می‌رسد ولی کماکان در پشته هم وجود دارد.
  • جابه‌جایی: بالاترین دو دادهٔ پشته، با هم جابه‌جا می‌شوند.

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