Queue (صف) یک ساختمان داده خطی است که از قانون FIFO پیروی میکند.
FIFO (First In, First Out) یعنی:
اولین عنصری که وارد صف میشود، اولین عنصری است که خارج میشود.
صف معمولاً شامل دو اندیس اصلی است:
- Front → اولین عنصر صف
- Rear → آخرین عنصر صف
- Simple Queue (صف ساده)
- Circular Queue (صف حلقوی)
- Priority Queue (صف اولویتدار)
- Deque (صف دوطرفه)
در این درس، تمرکز روی صف ساده با آرایه است.
عملیات پایهای که هر صف باید داشته باشد:
- Create Queue → ایجاد صف
- Enqueue → افزودن عنصر به انتهای صف
- Dequeue → حذف عنصر از ابتدای صف
- IsEmpty → بررسی خالی بودن صف
- IsFull → بررسی پر بودن صف
- Display → نمایش عناصر صف
Front --> [ 10 | 20 | 30 | 40 ] <-- Rear
- Enqueue(50):
Front --> [ 10 | 20 | 30 | 40 | 50 ] <-- Rear
- Dequeue():
Front --> [ 20 | 30 | 40 | 50 ] <-- Rear
- صف با استفاده از آرایه پیادهسازی میشود.
- ابتدا صف ایجاد میشود و اندازه آن مشخص است.
- عناصر فقط از Rear اضافه میشوند.
- عناصر فقط از Front حذف میشوند.
- اگر Front از Rear جلو بزند، صف خالی است.
-
نام انگلیسی درس: Queue Creation & Basic Operations
-
صف برخلاف پشته، LIFO نیست.
-
صف کاربرد زیادی در:
- سیستمعاملها
- صف پردازشها
- صف چاپ
- BFS در گراف
-
پیچیدگی زمانی:
- Enqueue → O(1)
- Dequeue → O(1)
./02_queue_ops 5 10 20 30خروجی:
Queue elements:
10 20 30
After Dequeue:
20 30