موضوع مقاله: پشته (ساختمان داده‌ها) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پشته (ساختمان داده‌ها) | مقدمه: پشته در طراحی و پیاده‌سازی سیستم‌های نرم‌افزاری و سخت‌افزاری، فراوان به کار می‌رود. | ## بخش 1: پشته (ساختمان داده‌ها) | پشته (stack) ساختمان داده ای است که از لیست یا فهرست برای سازماندهی داده ها استفاده میکند و در عین حال از انتزاع نیز پشتیبانی میکند و یک نوع داده انتزاعی را فراهم میسازد. در پشته عمل اضافه کردن و حذف عنصر، فقط در یک طرف آن، بنام بالای پشته انجام میشود. بهمین دلیل گفته میشود که پشته از سیاست خروج به ترتیب عکس ورود (LIFO) پیروی میکند. عملیات های پشته در ساختمان داده ها: از آنجایی که عناصر پشته فقط از یک طرف (بالای پشته) قابل دستیابی اند. پس عملیات های متعددی را میتوان روی پشته انجام داد که چند عملیات زیر به‌عنوان عملیات اصلی پشته مطرح اند: Push : که عنصری را به بالای پشته اضافه میکند. در حقیقت پشته، یکی از سه بخش تخصیص یافته به یک برنامه در حال اجرا در حافظه (RAM) می‌باشد. پس از اجرای هر برنامه کاربردی آن برنامه برای پردازش توسط پردازشگر، به سه بخش در حافظه تقسیم و ذخیره می‌گردد تا در دسترس پردازشگر قرار بگیرد. این سه بخش شامل موارد زیر هستند: بخش کد (شامل کد برنامه) پشته بخش داده (داده + بی‌اس‌اس(نماد شروع بلوک داده) + هیپ (هرم داده FIFO و LIFO چیست؟ این سیاست اساس کار پشته‌ها را تشکیل می‌دهد و به مفهوم آن است که آخرین دادهٔ ذخیره شده در پشته، نخستین داده‌ای است که بازیابی می‌شود. | ## بخش 2: پشته (ساختمان داده‌ها) | این سیاست اساس کار صف‌ها را تشکیل می‌دهد و به مفهوم آن است که اولین دادهٔ ذخیره شده در صف، نخستین داده‌ای نیز هست که بازیابی می‌شود. با توجه به آنچه گفته شد، روشن است که در سیاست LIFO، ورود و خروج داده‌ها، از یک سمت صورت می‌گیرد (در واقع تنها یک سمت تودهٔ داده‌ها باز است) در حالی که در سیاست FIFO، ورود و خروج داده‌ها، از دو سمت صورت می‌گیرد (یک سمت برای ورودی و یک سمت برای خروجی) و ما به دو سر تودهٔ داده‌ها دست‌رسی خواهیم داشت (یکی برای ورود و دیگری برای خروج). در این حالت ما تنها می‌توانیم بر روی دستهٔ کاغذها، کاغذی بگذاریم و از طرفی تنها می‌توانیم از روی دستهٔ کاغذها، کاغذی برداریم (یعنی ورود و خروج از یک سمت انجام می‌گیرد). روشن است که در این حالت آخرین کاغذی که روی دستهٔ کاغذها قرار داده شده، نخستین کاغذی است که برداشته می‌شود و اولین کاغذی که روی میز گذاشته شده، آخر از همه برداشته خواهد شد. در این حالت، برخلاف پشته، آدم‌ها به ته صف اضافه می‌شوند و از سر صف خارج می‌شوند (یعنی ورود و خروج از دو سمت متمایز انجام می‌گیرد). به این ترتیب روشن است که آخرین کسی که وارد صف شده، آخرین کسی است که نان دریافت می‌کند و اولین کسی که وارد صف شده، نخستین فردی است که نان می‌گیرد. صرف‌نظر از این‌که از کدام‌یک استفاده می‌کنیم، پیاده‌سازی دو تابع Push (برای گذاشتن داده) و Pop (برای برداشتن داده) بسیار مهم است. نکتهٔ مهم دیگر در پیاده‌سازی پشته، نگه‌داشتن اشاره‌گری به آخرین داده است که اصطلاحاً به آن Top گفته می‌شود. این موضوع با توجه به شبه‌کد نمونه‌ای که در قسمت قبل برای پیاده‌سازی با آرایه طرح شده‌است، کاملاً قابل توجیه‌است. | ## بخش 3: پشته (ساختمان داده‌ها) | می‌بینیم که در پیاده‌سازی آرایه‌ای، پیچیدگی زمانی افزودن و برداشتن عنصرها از پشته و به پشته، با هم متفاوت است. با این وجود اگر پشته را با لیست‌های پیوندی پیاده‌سازی کنیم، به علت ساختار خاص این لیست‌ها، هردوی این اعمال برای پشته (و به همین شکل برای صف)، دارای پیچیدگی زمانی از (O(1 خواهد بود. چند حالت نامطلوب هنگام پیاده‌سازی پشته، باید حالت‌های خاص زیر را هم در نظر گرفت: هنگام صدا‌کردن تابع Push در پشته‌ها، در صورتی که پشته پر باشد، خطای سرریزOverflow رخ خواهد داد. البته این اتفاق در صورتی می‌افتد که ظرفیت پشته تعیین‌شده باشد و نتوانیم آن را افزایش دهیم. البته این خطا در صورتی اتفاق می‌افتد که ظرفیت پشته تعیین‌شده و محدود باشد و نتوانیم آن را افزایش دهیم. کاربردها پشته‌ها در زمینه‌های بسیاری به کار می‌روند که البته در هر زمینه کارایی مشابهی هم دارند. روند توسعه در سیستم‌هایی که به شدت به پشته‌ها وابسته‌اند، علاوه بر تابع‌هایی که گفته شد، تابع‌های دیگری نیز برای آسان‌تر شدن کار پیاده‌سازی می‌شوند و به این ترتیب پشته‌ها توسعه پیدا می‌کنند. برداشت:Peek بالاترین داده Pop می‌شود ولی اشاره‌گر Top تغییر نمی‌کند؛ به عبارت دیگر، داده به دست ما می‌رسد ولی کماکان در پشته هم وجود دارد. جابه‌جایی کلی:Rotate همه عناصر پشته یکی به سمت پایین جابه‌جا می‌شوند و پایین‌ترین داده در جای بالاترین داده قرار می‌گیرد. | ## جمع‌بندی | علاوه بر این‌ها، از ترکیب صف و پشته، داده‌ساختار جدیدیDeque هم ایجاد شده‌است که هم امکان افزودن عنصرها را از دوسوی تودهٔ داده‌ها می‌دهد و هم امکان برداشتن آن‌ها را.