پشته (Stack) چیست؟

پشته: یک نگاه ساده به ساختار داده ای مهم

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

به زبان ساده، پشته یک لیست مرتب شده از اطلاعاته که فقط از یه طرف می‌تونید بهش چیزی اضافه کنید (قرار دادن) یا چیزی بردارید (حذف کردن). این طرف رو معمولاً بالای پشته می‌نامند.

عملکرد پشته

پشته دو عمل اصلی داره:

• Push (قرار دادن): اضافه کردن یک عنصر به بالای پشته. مثل گذاشتن یه بشقاب دیگه روی دسته.
• Pop (حذف کردن): حذف کردن عنصر بالای پشته. مثل برداشتن بشقاب بالایی از دسته.

این روش کار، که آخرین ورودی، اولین خروجی هست (Last In, First Out یا LIFO) خصوصیت اصلی پشته‌ست.

یک مثال ساده

فرض کنید می‌خوایم یه پشته درست کنیم و اعداد 1، 2 و 3 رو به ترتیب داخلش قرار بدیم. بعدش هم می‌خوایم اعداد رو از پشته خارج کنیم.

1. Push 1: پشته الان شامل [1] هست (1 بالاست).
2. Push 2: پشته الان شامل [1, 2] هست (2 بالاست).
3. Push 3: پشته الان شامل [1, 2, 3] هست (3 بالاست).
4. Pop: عدد 3 از پشته حذف میشه. پشته دوباره شامل [1, 2] میشه.
5. Pop: عدد 2 از پشته حذف میشه. پشته دوباره شامل [1] میشه.
6. Pop: عدد 1 از پشته حذف میشه. پشته خالی میشه.

کاربردهای پشته

پشته‌ها کاربردهای خیلی زیادی در برنامه‌نویسی و علوم کامپیوتر دارند. چندتا از مهم‌ترین‌هاش اینا هستن:

• بررسی تطابق پرانتزها: برنامه‌ای که چک می‌کنه پرانتزهای باز و بسته درست استفاده شدن.
• Undo/Redo: عملکرد دکمه‌های بازگشت و انجام دوباره در خیلی از برنامه‌ها.
• فراخوانی توابع: وقتی یک تابع، تابع دیگه‌ای رو صدا می‌زنه، اطلاعات مربوط به تابع اول (مثل متغیرها و آدرس برگشت) داخل پشته ذخیره می‌شه.
• تبدیل عبارت‌های ریاضی: تبدیل عبارت‌هایی مثل "2 + 3 * 4" به فرمی که کامپیوتر راحت‌تر بتونه اونا رو محاسبه کنه.

پیاده‌سازی پشته

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

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None  # or raise an exception

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            return None

    def size(self):
        return len(self.items)

# Example usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)

print(s.pop())  # Output: 30
print(s.peek()) # Output: 20
print(s.size()) # Output: 2

    

توی این کد، از لیست `self.items` برای نگهداری عناصر پشته استفاده کردیم. تابع `push` عنصر رو به انتهای لیست اضافه می‌کنه (بالای پشته) و تابع `pop` عنصر آخر لیست رو حذف می‌کنه (از بالای پشته).

مقایسه پشته با صف

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

ویژگی	پشته (Stack)	صف (Queue)
نحوه دسترسی به عناصر	آخرین ورودی، اولین خروجی (LIFO)	اولین ورودی، اولین خروجی (FIFO)
عملکرد اصلی	Push (قرار دادن)، Pop (حذف کردن)	Enqueue (اضافه کردن)، Dequeue (حذف کردن)
مثال	دسته بشقاب، Undo/Redo	صف نونوایی، صف پرینت

خلاصه

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

کلمات کلیدی

پشته، Stack، ساختمان داده، LIFO، Push، Pop، پایتون، برنامه نویسی

پشته دقیقا به چه دردی میخوره؟

پشته تو خیلی جاها استفاده میشه، از بررسی درست بودن پرانتزها تو کدنویسی گرفته تا مدیریت کارهایی که با دکمه های Undo و Redo انجام میدیم. حتی وقتی کامپیوتر داره توابع رو اجرا میکنه، از پشته استفاده میکنه!

فرق پشته و صف چیه؟

تصور کن یه دسته بشقاب داری. تو پشته، آخرین بشقابی که گذاشتی، اولین بشقابی هست که برمیداری. اما تو صف، مثل صف نونوایی، اولین کسی که اومده، اولین کسی هست که نون میگیره!

آیا پیاده سازی پشته با آرایه محدودیتی داره؟

بله، اگر از آرایه برای پیاده سازی پشته استفاده کنیم، باید اندازه ثابتی برای پشته در نظر بگیریم. این یعنی اگر تعداد عناصر از این اندازه بیشتر بشه، ممکنه با مشکل مواجه بشیم. اما استفاده از لیست پیوندی این مشکل رو نداره، چون اندازه لیست میتونه به صورت پویا تغییر کنه. برای همینه که لیست پیوندی یه ال**زینه** انعطاف پذیرتره.

چطور میتونم پشته رو تو برنامه خودم استفاده کنم؟

بسته به زبانی که استفاده میکنی، معمولا کتابخونه ها و کلاس های آماده ای برای استفاده از پشته وجود داره. مثلا تو پایتون میتونی از لیست به عنوان پشته استفاده کنی و از متدهای `append` و `pop` برای اضافه و حذف کردن عناصر استفاده کنی. ولی اگه میخوای یه پیاده سازی سفارشی داشته باشی، میتونی مثل مثال بالا خودت کلاس پشته رو بنویسی.

آیا پشته فقط برای اعداد استفاده میشه؟

نه اصلا! پشته میتونه هر نوع داده ای رو نگه داره. میتونی توش عدد ذخیره کنی، متن ذخیره کنی، یا حتی اشیاء پیچیده تر. مهم اینه که بتونی به ترتیب درست اطلاعات رو اضافه و حذف کنی.