صف (Queue)
صف با اصل FIFO: عملیات enqueue و dequeue، صف دوری، صف اولویت‌دار و کاربردهای واقعی
صف چیست؟
صف (Queue) ساختاری است که از یک انته ورود (rear) و از انته دیگر خروج (front) دارد؛ اصل FIFO (First In, First Out — اولین وارد، اولین خارج).
مثل صف نانوایی: اولین نفری که در صف ایستاده، اولین نفری است که نان می‌گیرد.
عملیات اصلی
| عملیات | پیچیدگی | توضیح |
|---|---|---|
| enqueue | O(1) | افزودن به انته صف |
| dequeue | O(1) | برداشتن از جلوی صف |
| front/peek | O(1) | دیدن اول صف بدون حذف |
| is_empty | O(1) | خالی بودن |
هشدار پیاده‌سازی در پایتون!
با list معمولی، pop(0) برای dequeue O(n) است (همه عناصر جابه‌جا می‌شوند)! راه درست:
from collections import deque
q = deque()
q.append(10) # enqueue: O(1)
q.popleft() # dequeue: O(1)انواع صف
- صف ساده: FIFO خالص
- صف دوری (Circular): آخر صف به اول وصل است؛ حافظه را بازیافت می‌کند
- صف اولویت‌دار (Priority Queue): عنصر با اولویت بالاتر اول خارج می‌شود (با هیپ پیاده‌سازی می‌شود — مبحث هیپ)
- دوصفی (Deque): از هر دو انتها ورود/خروج مجاز
کاربردهای واقعی
- پردازش چاپگر: اسناد به ترتیب ارسال چاپ می‌شوند
- صف پیام (Message Queue): در سیستم‌های توزیع‌شده مثل RabbitMQ و Kafka
- زمان‌بند CPU: پردازش‌ها در صف اجرا
- الگوریتم BFS در گراف (مبحث آینده)
- بافر جریان: پخش ویدیو، صف درخواست‌های سرور
صف دوری — چرا؟
در صف آرایه‌ای ساده، بعد از چند dequeue، خانه‌های ابتدایی بلااستفاده می‌مانند. صف دوری با ماژولو انته آرایه را به ابتدا وصل می‌کند:
next_rear = (rear + 1) % capacityنکته: قانون سرانگشتی — پشته برای «برگردادن به عقب» (Undo/Back) و صف برای «پردازش منصفانه به ترتیب» (نوبت‌بندی). BFS از صف و DFS از پشته استفاده می‌کند!
جمع‌بندی
- صف = FIFO؛ ورود از انتها، خروج از جلو
- در پایتون از deque استفاده کنید نه pop(0)
- صف اولویت‌دار = اولویت به‌جای ترتیب ورود
- کاربردها: نوبت‌بندی، BFS، صف پیام، زمان‌بندی
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.