پشته

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

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

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

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

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

پشته‌ها ممکن است با هر یک از انواع داده‌ساختارهایی مثل آرایه،[4] لیست پیوندی[5] و… پیاده‌سازی شوند. صرف‌نظر از این‌که از کدام‌یک استفاده می‌کنیم، پیاده‌سازی دو تابع Push (برای گذاشتن داده) و Pop (برای برداشتن داده) بسیار مهم است. نکتهٔ مهم دیگر در پیاده‌سازی پشته، نگه‌داشتن اشاره‌گری به آخرین داده است که اصطلاحاً به آن Top گفته می‌شود. اگر فرض کنیم که پشته با آرایه پیاده‌سازی شده باشد، شبه‌کد[6] تابع‌های 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;

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

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

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

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

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

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

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

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

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

در ویکی‌انبار پرونده‌هایی دربارهٔ پشته موجود است.