Algorithm design & data structure

پشته (Stack) یکی از مهم‌ترین ساختارهای داده‌ای است که بر اساس اصل LIFO (Last In, First Out) عمل می‌کند. این به این معنی است که آخرین عنصری که وارد پشته می‌شود، اولین عنصری است که خارج می‌شود. پشته به عنوان یک ساختار ساده و در عین حال قدرتمند در بسیاری از الگوریتم‌ها و برنامه‌های کاربردی استفاده می‌شود.

ویژگی‌ها و عملکرد پشته:
1. LIFO (آخرین ورودی، اولین خروجی): پشته به این صورت عمل می‌کند که وقتی عنصری را وارد آن می‌کنیم (عملیات push)، آن عنصر در بالای پشته قرار می‌گیرد. زمانی که نیاز به خارج کردن عنصری داریم (عملیات pop)، آخرین عنصری که وارد شده است، خارج می‌شود.

2. توابع اصلی پشته:
-تابع push(item): این تابع یک عنصر جدید را به بالای پشته اضافه می‌کند.
-تابع pop(): این تابع آخرین عنصر اضافه‌شده به پشته را حذف و بازمی‌گرداند.
-تابع peek(): این تابع مقدار بالاترین عنصر موجود در پشته را بدون حذف آن بازمی‌گرداند.
-تابع isEmpty(): این تابع بررسی می‌کند که آیا پشته خالی است یا خیر.
-تابع size(): این تابع اندازه پشته (تعداد عناصر موجود) را بازمی‌گرداند.

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

4. کاربردها:
- محاسبات ریاضی (Postfix و Prefix): از پشته در ارزیابی عبارات ریاضی استفاده می‌شود.
- برگرداندن رشته‌ها: پشته‌ها برای معکوس کردن رشته‌ها بسیار مفید هستند. به عنوان مثال، اگر بخواهیم کلمه‌ای را معکوس کنیم، می‌توانیم حروف را یکی‌یکی در پشته قرار دهیم و سپس آنها را به ترتیب خارج کنیم.
- کنترل دسترسی به توابع (Recursion): در برنامه‌نویسی بازگشتی، سیستم پشته برای نگه‌داری وضعیت فعلی تابع استفاده می‌شود.
- مدیریت حافظه: در زمان اجرای برنامه‌ها، سیستم عامل برای مدیریت حافظه و ذخیره داده‌های موقت از پشته‌ها استفاده می‌کند.

مثال از پیاده‌سازی پشته در پایتون:

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

    def isEmpty(self):
        return self.items == []

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

    def pop(self):
        if not self.isEmpty():
            return self.items.pop()
        else:
            return None

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

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

# استفاده از پشته
stack = Stack()
stack.push(5)
stack.push(10)
print(stack.pop())  # خروجی: 10
print(stack.peek())  # خروجی: 5

در این مثال، ما یک کلاس Stack ایجاد کرده‌ایم که با استفاده از لیستی از عناصر پشته پشتیبانی می‌کند و توابع اصلی مثل push، pop و peek را پیاده‌سازی می‌کند.

پیچیدگی زمانی:
-تابع push: در حالتی که پشته به صورت لیست آرایه‌ای پیاده‌سازی شود، این عمل دارای پیچیدگی زمانی O(1) است.
-تابع pop: عمل حذف نیز مانند اضافه کردن، دارای پیچیدگی O(1) است.
-تابع peek: این عمل نیز زمان ثابت O(1) دارد.

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

#الگوریتم
👨‍💻 @AlgorithmDesign_DataStructuer

3.3K views20:43