پشته (ساختمان داده‌ها)

ساختارهای خطی داده‌ها
آرایه صف‌گشایی توده لیست پیوندی صف پشته

پشته^[۱][۲] (به انگلیسی: stack) یکی از انواع داده‌ساختارها^[۳] (ساختمان داده) است و برای ذخیره و بازیابی داده‌ها کاربرد دارد. پشته در طراحی و پیاده‌سازی سیستم‌های نرم‌افزاری و سخت‌افزاری، فراوان به کار می‌رود. شیوهٔ عملکرد پشته بر اساس سیاست LIFO است.

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

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

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

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

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

FIFO و LIFO چیست؟

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

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

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

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

تصویر بالا، یک صف (داده‌های در انتظار پردازش در CPU؛ ورود و خروج داده‌ها در جهت مشخص شده انجام می‌شود و عدد ۱ ورودی و عدد ۰ خروجی هستند) و تصویر پایین یک پشته (دستهٔ کاغذها روی میز؛ تنها به کاغذ رویی دست‌رسی داریم) را نشان می‌دهند

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

پیاده‌سازی

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

شمایی از افزودن یک عنصر به پشته (Push)

شمایی از برداشتن یک عنصر از پشته (Pop)

procedure Push(data d)
begin
   stack[top]:=d; //here "stack" is the array that stores data
   top:=top+1; //here "top" is a pointer to above of top element
end;

function Pop: data
begin
   top:=top-1; //here "top" is a pointer to above of top element
   result:=stack[top]; //here "stack" is the array that stores data
end;

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

پیچیدگی زمانی^[۷] اضافه کردن یک عنصر به یک پشته یا برداشتن یک عنصر از روی یک پشته با پیاده‌سازی آرایه‌ای، از (O(1 است. این موضوع با توجه به شبه‌کد نمونه‌ای که در قسمت قبل برای پیاده‌سازی با آرایه طرح شده‌است، کاملاً قابل توجیه‌است.

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

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

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

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

کاربردها

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

روند توسعه

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

• مشابه‌سازی:^[۱۵] با یک بار Pop کردن و دو بار Push کردن بالاترین دادهٔ پشته، این داده به دو دادهٔ مشابه تبدیل می‌شود (به عبارت دیگر تکثیر می‌شود).
• برداشت:^[۱۶] بالاترین داده Pop می‌شود ولی اشاره‌گر Top تغییر نمی‌کند؛ به عبارت دیگر، داده به دست ما می‌رسد ولی کماکان در پشته هم وجود دارد.
• جابه‌جایی:^[۱۷] بالاترین دو دادهٔ پشته، با هم جابه‌جا می‌شوند.
• جابه‌جایی کلی:^[۱۸] همه عناصر پشته یکی به سمت پایین جابه‌جا می‌شوند و پایین‌ترین داده در جای بالاترین داده قرار می‌گیرد.

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

پانویس

1. حمیدرضا مقسمی (۱۳۸۳)، «آرایه و پشته و صف»، ساختمان داده‌ها، گسترش علوم پایه
2. لاری نایروف (۱۳۸۲)، ساختمان داده‌ها در ++C، ترجمهٔ جعفرنژاد قمی، نص
3. Date Structure
4. Array
5. Linked List
6. Pseudocode
7. Time Complexity
8. Overflow
9. Operating System
10. Underflow
11. Operand
12. Operator
13. Algorithm
14. Depth-First Search
15. Duplicate
16. Peek
17. Swap
18. Rotate
19. Deque

پیوند به بیرون

• Stack Implementation (Graphical & Text Mode)
• stack visualizations
• queue visualizations
• Queue program in c++
• STL Quick Reference Queue

منابع

• ویکی‌پدیای انگلیسی

• Donald Knuth (۱۹۹۷)، The Art of Computer Programming, Volume 1: Fundamental Algorithms (ویراست ۳rd Edition)، Addison-Wesley، شابک ۰-۲۰۱-۸۹۶۸۳-۴نگهداری یادکرد:متن اضافی (رده)