استفاده از صف (Queue) در پایتون: مفاهیم متوسط

در این مقاله، به بررسی مفهوم صف (Queue) در پایتون و نحوه پیاده‌سازی و استفاده از آن می‌پردازیم. صف‌ها یکی از ساختارهای داده‌ای اساسی هستند که در بسیاری از الگوریتم‌ها و برنامه‌ها کاربرد دارند. این مقاله برای افرادی که با مفاهیم اولیه پایتون آشنا هستند و به دنبال یادگیری مفاهیم متوسط در این زبان هستند، مناسب است.

مقدمه‌ای بر صف (Queue)

صف (Queue) یک ساختار داده‌ای خطی است که بر اساس اصل “اول ورودی، اول خروجی” (FIFO – First-In, First-Out) عمل می‌کند. به این معنی که اولین عنصری که به صف اضافه می‌شود، اولین عنصری است که از آن خارج می‌شود. تصور کنید در یک صف نانوایی، شخصی که زودتر می‌آید، زودتر نان خود را دریافت می‌کند. صف‌ها برای مدیریت وظایف، پردازش درخواست‌ها و مدل‌سازی سیستم‌های واقعی بسیار مفید هستند.

عملیات اصلی روی صف

چندین عملیات اصلی وجود دارد که می‌توان روی یک صف انجام داد:

• Enqueue (اضافه کردن): اضافه کردن یک عنصر جدید به انتهای صف.
• Dequeue (حذف کردن): حذف کردن عنصر اول از صف.
• Peek (نگاه کردن): مشاهده عنصر اول صف بدون حذف آن.
• IsEmpty (خالی بودن): بررسی اینکه آیا صف خالی است یا خیر.
• Size (اندازه): برگرداندن تعداد عناصر موجود در صف.

پیاده‌سازی صف در پایتون

در پایتون، می‌توان صف‌ها را به روش‌های مختلف پیاده‌سازی کرد. یکی از رایج‌ترین روش‌ها استفاده از ماژول collections و کلاس deque (Double-Ended Queue) است. deque یک صف دوطرفه است که امکان اضافه کردن و حذف کردن عناصر از هر دو طرف را فراهم می‌کند. با این حال، برای پیاده‌سازی یک صف استاندارد، معمولاً فقط از انتهای صف برای اضافه کردن و از ابتدای صف برای حذف کردن استفاده می‌کنیم.

استفاده از collections.deque

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

from collections import deque

class Queue:
    def __init__(self):
        self.elements = deque()

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

    def dequeue(self):
        if not self.is_empty():
            return self.elements.popleft()
        else:
            return None  # یا raise Exception("Queue is empty")

    def peek(self):
        if not self.is_empty():
            return self.elements[0]
        else:
            return None

    def is_empty(self):
        return len(self.elements) == 0

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

# مثال استفاده
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)

print("اندازه صف:", q.size())  # خروجی: 3
print("اولین عنصر:", q.peek())  # خروجی: 10

print("حذف شده:", q.dequeue())  # خروجی: 10
print("حذف شده:", q.dequeue())  # خروجی: 20

print("آیا صف خالی است؟", q.is_empty())  # خروجی: False
print("حذف شده:", q.dequeue())  # خروجی: 30
print("آیا صف خالی است؟", q.is_empty())  # خروجی: True

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

اگرچه deque کارآمدتر است، می‌توان صف را با استفاده از لیست‌های پایتون نیز پیاده‌سازی کرد. با این حال، حذف عنصر اول از یک لیست (با استفاده از pop(0)) می‌تواند زمان‌بر باشد، زیرا نیاز به جابجایی تمام عناصر بعدی دارد. در اینجا یک مثال از پیاده‌سازی صف با استفاده از لیست آورده شده است:

class Queue:
    def __init__(self):
        self.elements = []

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

    def dequeue(self):
        if not self.is_empty():
            return self.elements.pop(0)
        else:
            return None  # یا raise Exception("Queue is empty")

    def peek(self):
        if not self.is_empty():
            return self.elements[0]
        else:
            return None

    def is_empty(self):
        return len(self.elements) == 0

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

کاربردهای صف در پایتون

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

• مدیریت وظایف (Task Scheduling): صف‌ها می‌توانند برای مدیریت وظایفی که باید به ترتیب اجرا شوند، استفاده شوند.
• پردازش درخواست‌ها (Request Processing): در سیستم‌های تحت وب و سرور، صف‌ها می‌توانند برای مدیریت درخواست‌های ورودی و پردازش آن‌ها به ترتیب استفاده شوند.
• جستجوی سطح اول (Breadth-First Search – BFS): BFS یک الگوریتم جستجو در گراف است که از صف برای ذخیره گره‌هایی که باید بازدید شوند، استفاده می‌کند.
• بافر (Buffering): صف‌ها می‌توانند به عنوان بافر برای ذخیره داده‌ها بین دو فرآیند با سرعت‌های متفاوت استفاده شوند.
• شبیه‌سازی (Simulation): صف‌ها می‌توانند برای مدل‌سازی سیستم‌های واقعی مانند صف‌های انتظار در بانک‌ها یا سوپرمارکت‌ها استفاده شوند.

صف‌های اولویت‌دار (Priority Queues)

در برخی موارد، ممکن است نیاز به یک صف داشته باشیم که در آن عناصر بر اساس اولویت مرتب شوند. به این نوع صف‌ها، صف‌های اولویت‌دار گفته می‌شود. در یک صف اولویت‌دار، عنصری با اولویت بالاتر زودتر از عناصر با اولویت پایین‌تر حذف می‌شود. در پایتون، می‌توان از ماژول heapq برای پیاده‌سازی صف‌های اولویت‌دار استفاده کرد. heapq یک پیاده‌سازی از ساختار داده‌ای هیپ (Heap) است که برای پیاده‌سازی صف‌های اولویت‌دار بسیار کارآمد است.

استفاده از heapq برای پیاده‌سازی صف اولویت‌دار

heapq به طور پیش‌فرض یک هیپ کوچک (Min Heap) ایجاد می‌کند، به این معنی که کوچکترین عنصر همیشه در ریشه هیپ قرار دارد. برای پیاده‌سازی یک صف اولویت‌دار، می‌توان از heappush برای اضافه کردن عناصر و از heappop برای حذف کردن عنصر با کمترین مقدار استفاده کرد.

import heapq

class PriorityQueue:
    def __init__(self):
        self.elements = []

    def enqueue(self, item, priority):
        heapq.heappush(self.elements, (priority, item))

    def dequeue(self):
        if not self.is_empty():
            return heapq.heappop(self.elements)[1]
        else:
            return None

    def is_empty(self):
        return len(self.elements) == 0

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

# مثال استفاده
pq = PriorityQueue()
pq.enqueue("وظیفه 1", 3)
pq.enqueue("وظیفه 2", 1)
pq.enqueue("وظیفه 3", 2)

print("حذف شده:", pq.dequeue())  # خروجی: وظیفه 2
print("حذف شده:", pq.dequeue())  # خروجی: وظیفه 3
print("حذف شده:", pq.dequeue())  # خروجی: وظیفه 1

نتیجه‌گیری

صف‌ها یک ساختار داده‌ای مهم و پرکاربرد در پایتون هستند. در این مقاله، با مفهوم صف، عملیات اصلی روی آن، نحوه پیاده‌سازی آن با استفاده از collections.deque و لیست، و کاربردهای آن در پایتون آشنا شدیم. همچنین، به معرفی صف‌های اولویت‌دار و نحوه پیاده‌سازی آن‌ها با استفاده از ماژول heapq پرداختیم. با درک این مفاهیم، می‌توانید از صف‌ها برای حل مسائل مختلف در برنامه‌نویسی پایتون استفاده کنید.