آموزش جامع صف (Queue) در پایتون

سطح مقدماتی (Beginner Level)

در علوم کامپیوتر، صف (Queue) یک ساختار داده خطی است که از قانون FIFO (اولین ورودی، اولین خروجی - First In, First Out) پیروی می‌کند. دقیقاً مانند صف نانوایی: کسی که زودتر آمده، زودتر نان می‌گیرد و خارج می‌شود.

در پایتون، روش‌های مختلفی برای پیاده‌سازی صف وجود دارد، اما همه آن‌ها دو عملیات اصلی دارند:

1. Enqueue: اضافه کردن آیتم به انتهای صف.
2. Dequeue: حذف کردن آیتم از ابتدای صف.

۱. استفاده از لیست (List) به عنوان صف

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

مثال ۱: پیاده‌سازی ساده با متد pop(0)

در اینجا با استفاده از متد append آیتم را اضافه و با pop(0) اولین آیتم را حذف می‌کنیم.

مثال ۲: بررسی خالی بودن صف

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

# Static Code: Logic snippet for checking empty list
def safe_dequeue(current_queue):
    if len(current_queue) > 0:
        return current_queue.pop(0)
    else:
        return None

۲. استفاده از collections.deque (روش استاندارد)

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

مثال ۱: ساخت صف با deque

برای حذف از ابتدای صف در deque از متد popleft() استفاده می‌کنیم.

مثال ۲: محدود کردن اندازه صف

می‌توانید برای صف یک ظرفیت مشخص (maxlen) تعیین کنید. اگر صف پر شود و آیتم جدیدی اضافه کنید، قدیمی‌ترین آیتم خودکار حذف می‌شود.

سطح پیشرفته (Professional Level)

در سطح حرفه‌ای، بحث کارایی (Performance) و امنیت در محیط‌های چندنخی (Multi-threading) مطرح می‌شود.

۱. چرا لیست‌ها برای صف کند هستند؟ (Big O)

استفاده از list برای صف ایده بدی است زیرا:

• عملیات insert(0) یا pop(0) در لیست‌ها دارای پیچیدگی زمانی O(n) است. یعنی تمام عناصر باقی‌مانده باید در حافظه یک خانه جابه‌جا شوند.
• در مقابل، deque بر پایه "لیست پیوندی دوطرفه" (Doubly Linked List) است و عملیات حذف و اضافه در دو سر آن دارای پیچیدگی O(1) است (زمان ثابت).

۲. ماژول queue.Queue (Thread-Safe)

زمانی که با Multi-threading کار می‌کنید (مثلاً یک نخ دانلود می‌کند و نخ دیگر پردازش می‌کند)، استفاده از deque یا list امن نیست و ممکن است باعث Race Condition شود. پایتون ماژول queue را برای این منظور ارائه کرده است. این کلاس‌ها به صورت داخلی قفل (Lock) گذاری شده‌اند.

مثال ۱: الگوی Producer-Consumer (تولیدکننده-مصرف‌کننده)

این متداول‌ترین سناریوی استفاده از صف‌های حرفه‌ای است.

۳. صف اولویت (Priority Queue)

گاهی اوقات نمی‌خواهید آیتم‌ها به ترتیب ورود خارج شوند، بلکه می‌خواهید بر اساس "اهمیت" یا "اولویت" خارج شوند. کلاس queue.PriorityQueue آیتم‌ها را مرتب نگه می‌دارد (معمولاً کوچکترین عدد = بالاترین اولویت).

مثال ۱: اولویت‌بندی بر اساس اعداد

مثال ۲: ساختار داخلی PriorityQueue

این کلاس از ساختار داده Heap استفاده می‌کند. در اینجا فقط ساختار را می‌بینیم و اجرا نمی‌کنیم.

# Static Code: Concept of Priority Storage
# PriorityQueue در پس‌زمینه از heapq استفاده می‌کند
import heapq

# وقتی put می‌کنید معادل این است:
# heapq.heappush(self.queue, item)
# و وقتی get می‌کنید:
# heapq.heappop(self.queue)

۴. صف LIFO (پشته در قالب صف)

اگرچه Stack (پشته) مفهوم برعکس صف است، اما ماژول queue کلاسی به نام LifoQueue دارد که دقیقا رفتار پشته (Last In, First Out) را شبیه‌سازی می‌کند اما با ویژگی‌های Thread-Safe.