پایتون

جلسه ۷۶: پشته (stack) در پایتون

در این بخش شما با ساختمان داده‌ی پشته یا Stack و پیاده‌سازی آن در پایتون آشنا میشوید که در مسائل این فصل استفاده خواهیم کرد. در این درس، ما ساختمان داده stack را بررسی میکنیم و طریقه پیاده‌سازی آن را یاد میگیریم.در درس های دیگر مسائلی را مطرح میکنیم که stack ها مفید خواهند بود. در آنجا از پیاده سازی هایی که در این درس یاد میگیریم، استفاده خواهیم کرد.

stack چیست؟

اول از همه، اجازه بدهید تا تشریح کنیم که stack ها چه هستند که  بر اساس نام آنها، باید مفهومی آشنا باشد.فرض کنید که ۴ کتاب با عناوین زیر دارید:
  • A
  • B
  • C
  • D
این کتاب ها روی زمین نامرتب قرار دارند، میخواهیم آن ها را به صورت مرتب، جمع(stack) کنیم.

اکنون یک مجموعه و stack خوب داریم. اگر خواسته باشیم که یک کتاب را از این stack برداریم، میتوانیم کتاب مدنظر را از بالا برداریم. برداشتن کتاب از پایین خطرناک است چراکه باعث سقوط این پشته (stack) کتاب ها خواهد شد. بنابراین ما کتاب را از بالا برمیداریم و در پایین قرار میدهیم. این کتاب را میخوانیم و هر کاری که بخواهیم انجام میدهیم.اکنون اگر بخواهیم که کتاب A که در انتهای این پشته است را برداریم، باید اول کتاب D را برداریم و در انتهای آن قرار دهیم و این کار را برای کتاب B و c هم انجام دهیم. در نهایت میتوانیم به کتاب A دسترسی داشته باشیم.این ایده اصلی stack است.ساختمان داده stack خیلی شبیه به پشته ها یا stack های فیزیکی دنیای ماست، که این اتفاق باعث میشود تا نسبت به آن حس بدی نداشته باشید.ساختمان داده stack این امکان را میدهد که متغیر یا یک شی برنامه نویسی را، روی آن قرار دهیم، مانند مثال ما که کتاب ها را روی هم گذاشته ایم.

عملیات‌های stack

Push

عملیاتی که به کمک آن میتوانیم المان هایی را به stack اضافه کنیم push است. وقتی ما یک کتاب را به یک پشته push میکنیم در واقع آن را روی المان بالای پشته قرار میدهیم که در این حالت المان جدید به عنوان المان بالای پشته شناخته میشود.  منظور ما این است که وقتی از عملیات push استفاده میکنیم، المان های جدید را روی stack قرار میدهیم. وقتی المان های مختلفی را به یک پشته push میکنیم آخرین المان push شده، به عنوان بالاترین المان آن در نظر گرفته میشود.

Pop

عملیات دیگری که میتوان در stack  ها بکار برد، عملیات Pop کردن است. pop کردن منظور این است که المان بالای پشته را برمیداریم. این بدان معناست که وقتی عنصری را از پشته حذف میکنیم، stack به صورت First in Last out عمل میکند. یعنی اینکه عمل pop کردن، عنصر بالایی، که آخرین موردی است که وارد شده است، حذف میشود.pop و push دو عملیات روتین هستند که ما برای کار با ساختمان داده‌ها نیاز داریم.

Peek

کار دیگری که میتوانیم انجام دهیم، این است که بالاترین عضو یک stack را ببینیم. که در واقع از ساختمان داده مدنظر میپرسیم که “المان بالا چیست؟”  و آن این المان را به ما میدهد. این کار توسط peek انجام میشود. توجه شود که عملیات peek فقط بالاترین المان را به ما میدهد، ولی آن را حذف نمیکند.ما همچنین میتوانیم بررسی کنیم که آیا یک stack خالی است یا نه و کلی کارهای دیگر که در ادامه پیاده‌سازی میکنیم.اکنون یک کلاس stack میسازیم که آغازگر این کلاس یک لیست را میسازد. لیست های پایتون چیزهای دارد که ما بدنبالش در stackها هستیم. و این کار باعث میشود که ما بتوانیم پیاده‌سازی ساده‌تری داشته باشیم و تا آنچه از stack ها مانند push و pop انتظار داریم را بسازیم و با آن‌ها سازگار باشد.
"""
Stack Data Structure.
"""
class Stack():
    def __init__(self):
        self.items = []
یک متغیر کلاسی تعریف کرده ایم و آن را item نامیده‌ایم. همچنین آن را به یک لیست خالی نسبت داده‌ایم. self.items زمانی که یک stack جدید میسازیم، ساخته میشود. اکنون متد push را میسازیم:
"""
Stack Data Structure.
"""
class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)	
push نیز یک عضو از کلاس ما خواهد بود و از item به عنوان آرگومان آن استفاده کرده‌ایم. در مثال ما این item کتاب است. ما اسم کتاب را به بالای لیست اضافه میکنیم.append یک متد داخلی پایتون است که item را به انتهای لیست اضافه میکند. این دقیقا همان چیزی است که ما برای متد push در stack ها نیاز داریم.
"""
Stack Data Structure.
"""
class Stack():
    def __init__(self):
        self.items = []

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

    def pop(self):
        return self.items.pop()
متد دیگری که ما به آن احتیاج داریم، pop است. از آنجایی که ما آن را از لیست خارج میکنیم، پایتون این کار را برای ما آسان میکند. یک روش pop در پایتون وجود دارد که اخرین عنصری که به لیست اضافه شده است را به ما برمیگرداند.کار دیگری که باید انجام دهیم، اضافه کردن یکسری متد های دیگر است اما قبل از آن موارد گفته شده را تست میکنیم.
"""
Stack Data Structure.
"""
class Stack():
    def __init__(self):
        self.items = []

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

    def pop(self):
        return self.items.pop()

    def get_stack(self):
        return self.items

myStack = Stack()
myStack.push("A")
myStack.push("B")
print(myStack.get_stack())
myStack.push("C")
print(myStack.get_stack())
myStack.pop()
print(myStack.get_stack())
ما متد ()get_stack را نیز ساخته ایم. که لیست items را به ما میدهد، که هسته اصلی stack ما است. سپس ما یک شی stack در خط ۱۷ به نام myStack  ساخته ایم و مقادیر A و B را به Stack در خطوط ۱۸ ۱۹ اضافه میکنیم. بعد از اینکار myStack را پرینت میکنیم که نتیجه آن لیست [‘A’,’B’] است. A به عنوان عضو پایین stack است و B عضو بالا. سپس C را در خط ۲۱ به stack اضافه میکنیم که خروجی این بار به صورت[‘A’, ‘B’, ‘C’] است که C به عنوان عضو بالا قرار میگیرد.ما هسته پایه‌ای یک stack را یادگرفتیم. چند متد دیگر را میتوانیم در این روش بگنجانیم به عنوان مثال متد is_empty. این متد بررسی میکند که آیا یک stack خالی از المان است یا خیر.
"""
Stack Data Structure.
"""
class Stack():
    def __init__(self):
        self.items = []

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

    def pop(self):
        return self.items.pop()
    
    def is_empty(self):
        return self.items == []
        
    def get_stack(self):
        return self.items

myStack = Stack()
print(myStack.is_empty()) 
در اینجا ما True را به عنوان خروجی گرفتیم که نشان میدهد stack ما در این زمان خالی است. اگر ما چیزهای دیگری را به stack اضافه و push کنیم، و متد is_empty را هم فراخوانی کنیم، باید خروجی ما False باشد. این کار را شما میتوانید امتحان کنید.
"""
Stack Data Structure.
"""
class Stack():
    def __init__(self):
        self.items = []

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

    def pop(self):
        return self.items.pop()
    
    def is_empty(self):
        return self.items == []
    
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        
    def get_stack(self):
        return self.items

myStack = Stack()
myStack.push("A")
myStack.push("B")
myStack.push("C")
myStack.push("D")
print(myStack.peek())
اکنون در خط ۱۷ عملیات peek را داریم که به ما بالاترین عضو را میدهد.اگر peek را در stack بالا صدا بزنیم باید خروجی D بدهد. peek در خط ۱۸ اول بررسی میکند که آیا stack خالی است یا نه، در صورت خالی نبودن آخرین عضو را بر میگرداند که در این مثال آخرین عضو را به ما داده است. در خط ۱۹ مقدار [۱-]self.items را به return میدهیم چراکه این عملیات اخرین عضو items بدست می‌آورد. بنابراین ما مقدار D را که پایتون به عنوان آخرین عضو stack در نظر میگیرد، دریافت میکنیم.(توجه کنید که شما میتوانید برای متدهای پیاده‌سازی شده، بررسی کنید آیا یک stack خالی است یا نه. اما برای اینکه کارها همچنان ساده باشد این مرحله را در همه متدها انجام نداده‌ایم)اکنون یک شی stack جدید بسازید. و خود را محدود به حروف و string ها نکنید، شما میتوانید اعداد را هم استفاده کنید. فقط با این ساختمان داده کارهای مختلف انجام دهید و درک کنید که این سیستم چگونه کار میکند. در درس بعد با ما همراه باشید.

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا