پشته ها و صف ها در پایتون

معرفی

ساختارهای داده ذخیره سازی را در رایانه ها سازماندهی می کنند تا بتوانیم به طور مؤثر به داده ها دسترسی داشته باشیم و آنها را تغییر دهیم. پشته ها و صف ها برخی از اولین ساختارهای داده تعریف شده در علوم کامپیوتر هستند.

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

معمولاً پشته ها و صف ها با آرایه یا لیست پیوندی پیاده سازی می شوند. ما تکیه خواهیم کرد روی را List ساختار داده برای تطبیق هر دو پشته و صف.

در این مقاله، به اصول اولیه این دو ساختار داده می پردازیم. ما تعریف می کنیم که آنها چه هستند و چگونه کار می کنند، و سپس، نگاهی به دو تا از رایج ترین روش های پیاده سازی پشته و صف در پایتون خواهیم داشت.

پشته چیست؟

پشته ها، همانطور که از نام آن پیداست، ساختار داده ای هستند که از آن پیروی می کنند Last-in-First-Out اصل (LIFO) مثل اینکه یک سکه روی هم می چینیم روی روی دیگری، آخرین سکه ای که گذاشتیم روی بالا همانی است که برای اولین بار بعداً از پشته حذف می شود.

بنابراین برای پیاده سازی یک پشته، به دو عملیات ساده نیاز داریم:

• push – یک عنصر را به بالای پشته اضافه می کند:

• pop – عنصر بالای پشته را حذف می کند:

صف چیست؟

صف ها، همانطور که از نام پیداست، به دنبال آن هستند اولین ورودی اولین خروجی اصل (FIFO). انگار در صف انتظار بلیط سینماست، اولین کسی که در صف می ایستد اولین کسی است که بلیت می خرد و از فیلم لذت می برد.

بنابراین برای اجرای یک صف، به دو عملیات ساده نیاز داریم:

• enqueue – یک عنصر را به انتهای صف اضافه می کند:

• dequeue – عنصر را در ابتدای صف حذف می کند:

پیاده سازی پشته ها و صف ها با استفاده از لیست ها

پایتون داخلی List ساختار داده با روش هایی برای شبیه سازی هر دو همراه است پشته و صف عملیات

بیایید یک پشته از حروف را در نظر بگیریم:

letters = ()


letters.append('c')
letters.append('a')
letters.append('t')
letters.append('g')


last_item = letters.pop()
print(last_item)


last_item = letters.pop()
print(last_item)


print(letters) 

ما می توانیم از همان توابع برای پیاده سازی یک صف استفاده کنیم. این pop تابع به صورت اختیاری شاخص موردی را که می خواهیم بازیابی کنیم را به عنوان آرگومان می گیرد.

بنابراین ما می توانیم استفاده کنیم pop با اولین شاخص لیست یعنی 0، برای به دست آوردن رفتاری مانند صف.

یک “صف” میوه ها را در نظر بگیرید:

fruits = ()


fruits.append('banana')
fruits.append('grapes')
fruits.append('mango')
fruits.append('orange')


first_item = fruits.pop(0)
print(first_item)


first_item = fruits.pop(0)
print(first_item)


print(fruits) 

دوباره، در اینجا ما از آن استفاده می کنیم append و pop عملیات لیست برای شبیه سازی عملیات اصلی یک صف.

پشته و صف با کتابخانه Deque

پایتون دارای یک deque کتابخانه (با تلفظ ‘عرشه’) که دنباله ای با روش های کارآمد برای کار به عنوان پشته یا صف ارائه می دهد.

deque کوتاه است برای صف دوبل پایان – یک صف تعمیم یافته که می تواند اولین یا آخرین عنصر ذخیره شده را دریافت کند:

from collections import deque


numbers = deque()


numbers.append(99)
numbers.append(15)
numbers.append(82)
numbers.append(50)
numbers.append(47)


last_item = numbers.pop()
print(last_item) 
print(numbers) 


first_item = numbers.popleft()
print(first_item) 
print(numbers) 

پیاده سازی دقیق تر در پایتون

اگر کد شما به یک پشته نیاز دارد و شما a List، هیچ چیز مانع از تماس یک برنامه نویس نمی شود insert()، remove() یا سایر روش های لیست که بر ترتیب پشته شما تأثیر می گذارد! این اساساً نقطه تعریف یک پشته را خراب می کند، زیرا دیگر آنطور که باید عمل نمی کند.

مواقعی وجود دارد که مایلیم اطمینان حاصل کنیم که فقط عملیات معتبر قابل انجام است روی داده های ما ما می‌توانیم کلاس‌هایی ایجاد کنیم که فقط روش‌های لازم برای هر ساختار داده را نشان دهند. برای انجام این کار، اجازه دهید یک فایل جدید به نام ایجاد کنیم stack_queue.py و دو کلاس تعریف کنید:

class Stack:

    def __init__(self):
        self.stack = ()

    def pop(self):
        if len(self.stack) < 1:
            return None
        return self.stack.pop()

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

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


class Queue:

    def __init__(self):
        self.queue = ()

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

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

برنامه نویسان با استفاده از ما Stack و Queue اکنون تشویق می شوند که به جای آن از روش های ارائه شده برای دستکاری داده ها استفاده کنند.

مثال ها

تصور کنید که یک توسعه دهنده هستید که کار می کنید روی یک واژه پرداز کاملاً جدید وظیفه شما ایجاد یک ویژگی واگرد است – به کاربران اجازه می دهد تا اقدامات خود را تا ابتدای جلسه پس بگیرند.

آ پشته برای این سناریو مناسب است. ما می توانیم هر اقدامی را که کاربر انجام می دهد با فشار دادن آن به پشته ضبط کنیم. هنگامی که کاربر می خواهد یک عمل را لغو کند، آن را از پشته خارج می کند. ما می توانیم به سرعت این ویژگی را شبیه سازی کنیم:

document_actions = Stack()


document_actions.push('action: enter; text_id: 1; text: This is my favorite document')

document_actions.push('action: format; text_id: 1; alignment: center')

document_actions.pop()

document_actions.push('action: format; text_id: 1; style: bold')

صف ها در برنامه نویسی نیز کاربردهای گسترده ای دارند. به بازی هایی مثل این فکر کنید مبارز خیابانی یا Super Smash Brothers. بازیکنان در آن بازی‌ها می‌توانند با فشار دادن ترکیبی از دکمه‌ها، حرکات خاصی را انجام دهند. این ترکیب دکمه ها را می توان در یک صف ذخیره کرد.

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

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

input_queue = Queue()


input_queue.enqueue('DOWN')
input_queue.enqueue('RIGHT')
input_queue.enqueue('B')


key_pressed = input_queue.dequeue() 


key_pressed = input_queue.dequeue() 


key_pressed = input_queue.dequeue() 

نتیجه

پشته ها و صف ها ساختارهای داده ساده ای هستند که به ما اجازه می دهند داده ها را به صورت متوالی ذخیره و بازیابی کنیم. در یک پشته، آخرین موردی که وارد می کنیم اولین موردی است که بیرون می آید. در یک صف، اولین موردی که وارد می‌کنیم اولین چیزی است که بیرون آمده است.

می‌توانیم با استفاده از push عملیات و بازیابی اقلام با استفاده از pop عمل. با صف ها، موارد را با استفاده از عبارت اضافه می کنیم enqueue عملیات و بازیابی اقلام با استفاده از dequeue عمل.

در پایتون، می‌توانیم پشته‌ها و صف‌ها را فقط با استفاده از توکار پیاده‌سازی کنیم List ساختار داده ها. پایتون نیز دارای deque کتابخانه ای که می تواند به طور موثر عملیات پشته و صف را در یک شی ارائه دهد. در نهایت، ما کلاس‌های پشته و صف را برای کنترل دقیق‌تر داده‌هایمان ساخته‌ایم.

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