Stacks and queues
@amir0xdevبرخی از برنامه ها هنگام کار با داده ها به عملکرد بیشتری نیاز دارند، به عنوان مثال، واژه پردازها دارای یک عملکرد بازگردانی-بازانجام¹ هستند، زمانبندهای وظیفه² به سازوکار های صف بندی³ نیاز دارند، نقشه ها باید کوتاه ترین مسیر را پیدا کنند و غیره.
در این موارد ما باید ساختارهای داده خودمان را تعریف کنیم که عملکرد مورد نیاز را ارائه دهد.
برخی از محبوب ترین ساختارهای داده عبارتند از:
- Stacks
- Queues
- Linked Lists
- Graphs
ما ساختارهای داده فوق را پیاده سازی میکنیم و از آنها برای حل مشکلات رایج استفاده میکنیم.
پانوشت:
1. Undo-Redo
2. Task Schedulers
3. Queuing
Stacks
یک استک¹ ساختار دادهای ساده است که عناصر را به ترتیب خاصی اضافه و حذف میکند.
با توجه به تصویر فوق هر بار که عنصری اضافه میشود، در "بالایِ" استک قرار میگیرد. تنها یک عنصر در بالایِ استک میتواند حذف شود، درست مانند یک دسته² از بشقابها. این رفتار ³LIFO (آخرین ورود، اولین خروج) نامیده میشود.
اصطلاح شناسی
افزودن عنصری جدید به استک ⁴push و حذفِ عنصری از استک ⁵pop نامیده میشود.
برنامه های کاربردی
استکها را میتوان برای ایجاد قابلیتهای بازگردانی-بازانجام، تجزیه⁶ عبارات (تبدیل میانوند به پسوند/پیشوند)⁷ و موارد دیگر استفاده کرد.
یک استک را میتوان با استفاده از یک لیست⁸ در پایتون⁹ پیاده سازی کرد.
پانوشت:
1. دسته
2. Stack
3. (Last In, First Out)
4. عمل حذف کردن
5. __ اضافه کردن
6. parsing
7. (infix to postfix/prefix conversion)
8. List
9. Python (زبان برنامهنویسی)
استک در پایتون
در ادامه کلاس¹ Stack را با متُدهای² مربوطه push, pop, is_empty و print_stack تعریف و پیاده سازی میکنیم.
ما از یک لیست برای ذخیره دادهها استفاده خواهیم کرد.
class Stack:
def init(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, item):
self.items.insert(0, item)
def pop(self):
return self.items.pop(0)
def print_stack(self):
print(self.items)
s = Stack()
s.push('a')
s.push('b')
s.push('c')
s.print_stack()
s.pop()
s.print_stack()
همانطور که در قطعه کد فوق میبینید، ایجاد یک استک با استفاده از یک لیست آسان است.
ما از لیستی به نام آیتمها³ برای ذخیره عناصر خود استفاده میکنیم. متُد push یک عنصر را در ابتدای لیست اضافه میکند، در حالی که متُد pop اولین عنصر لیست را حذف میکند.
پانوشت:
1. Class
یا کلاس، مفهومی بسطیافته از ساختمان است که به جای اینکه، فقط دادهها را نگهداری کند، میتواند هم دادهها و هم توابع را با هم نگهداری کند.
2. Method
یا متُد، مجموعهای از دستورات در برنامه نویسی هستند که دارای نام خاصی میباشند.
ادامه در پست بعدی مربوط به الگوریتم...
@code_crafters