پشته (Stack)
پشته با اصل LIFO: عملیات push و pop، پیاده‌سازی، کاربردهای واقعی مثل Undo و فراخوانی توابع و پرانتزهای تو در تو
پشته چیست؟
پشته (Stack) ساختاری است که فقط از یک انته (بالا) اجازه ورود و خروج می‌دهد؛ به همین اصل LIFO (Last In, First Out — آخرین وارد، اولین خارج) معروف است.
مثل بشقاب‌های روی هم: آخرین بشقابی که گذاشته‌اید، اولین بشقابی است که برمی‌دارید.
عملیات اصلی
| عملیات | پیچیدگی | توضیح |
|---|---|---|
| push | O(1) | گذاشتن روی پشته |
| pop | O(1) | برداشتن از بالای پشته |
| peek/top | O(1) | دیدن بالای پشته بدون برداشتن |
| is_empty | O(1) | خالی بودن |
پیاده‌سازی
ساده‌ترین راه در پایتون، استفاده از list است:
stack = []
stack.append(10) # push
top = stack.pop() # pop
top = stack[-1] # peekکاربردهای واقعی پشته
- دکمه Undo: هر عمل روی پشته می‌رود؛ undo آخرین عمل را pop می‌کند
- فراخوانی توابع: سیستم‌عامل پشته فراخوانی (Call Stack) نگه می‌دارد — به همین دلیل بازگشت (recursion) عمیق، پشته را پر می‌کند!
- متن‌بازی (Browser History): دکمه Back پشته است
- بررسی پرانتزهای تو در تو: کامپایلرها با پشته چک می‌کنند
- تبدیل و ارزیابی عبارات: postfix و prefix
- الگوریتم DFS در گراف (مبحث آینده)
مثال کلاسیک: بررسی پرانتزها
رشته "{[()]}" معتبر است اما "([)]" نه. الگوریتم:
- پرانتز باز → push
- پرانتز بسته → pop و بررسی تطابق
- در پایان، پشته باید خالی باشد
پشته با لیست پیوندی
پشته را می‌توان با آرایه (ساده) یا لیست پیوندی (درج/حذف ابتدا O(1)) ساخت. هر دو عملیات پشته را O(1) می‌دهند؛ آرایه ساده‌تر و cache-friendlyتر است.
هشدار: pop روی پشته خالی خطا می‌دهد! همیشه قبل از pop با is_empty چک کنید یا از try/except استفاده کنید.
جمع‌بندی
- پشته = LIFO؛ فقط از بالا push/pop
- همه عملیات O(1)
- کاربردها: Undo، Call Stack، تاریخچه مرورگر، پرانتزها، DFS
- در پایتون: list با append/pop یا collections.deque
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.