یک صف یک مدل بسیار ساده برای نگهداری دادههاست. دقیقاً مثل صف نانوایی یا بانک:
اولین کسی که وارد صف میشود، اولین نفر است که سرویس میگیرد.
این نوع رفتار را FIFO میگویند:
First In, First Out
یعنی "اولین واردشده، اولین خارجشده"
در صف فقط از دو سمت با دادهها کار میکنیم:
عملیات توضیح ساده مثل این است که... اضافه کردن (enqueue) یک نفر را به انتهای صف اضافه کنیم کسی ته صف ایستاده حذف کردن (dequeue) نفر اول را از صف خارج کنیم کسی نوبتش شده نگاه کردن به نفر اول بدون حذف، فقط ببینیم اول کی ایستاده ببینیم چه کسی نوبتش است شمردن تعداد اعضا چند نفر توی صف هستند شمارش صف
🧪 مثال واقعی:
فرض کن صفی داریم و به ترتیب اعداد 5، 8، و 2 را وارد میکنیم:
Queue: 5 -> 8 -> 2 ↑ ↑ front back
حالا اگر بخواهیم یکی را خارج کنیم (dequeue) عدد 5 از صف حذف میشود:
Queue: 8 -> 2 ↑ ↑ front back
فرض کن یک لیست (یا آرایه) داریم.
ما یک متغیر داریم به اسم front که نشان میدهد نفر اول صف کجاست.
و یک متغیر دیگر به اسم back که نشان میدهد نفر آخر صف کجاست.
وقتی یک عنصر اضافه میکنی، میگذاری در queue[back] و back را یکی زیاد میکنی.
وقتی یک عنصر حذف میکنی، فقط front را یکی زیاد میکنی (چون حذف یعنی دیگر سراغ آن نمیرویم).
اگر زیاد عنصر حذف کنیم، فضای زیادی در ابتدای آرایه بیاستفاده میماند!
برای حل مشکل بالا، صف را دایرهای میکنیم.
یعنی اگر back یا front به انتهای آرایه رسید، به جای آنکه جلوتر برود، برمیگردد به ابتدای آرایه.
مثل یک دایره که وقتی به آخر رسیدی، دوباره به اولش برمیگردی.
مثال:
Array size: 5 Indexes: 0 1 2 3 4 Queue: [10] [20] [30] [40] [50] ↑ ↑ front back
اگر back یکی دیگر زیاد شود، میشود 0! یعنی ته صف به اول آرایه برمیگردد.
🎯 نکتههای مهم:
صف فقط از جلو حذف میکند و فقط از عقب اضافه میکند.
در صف معمولی، دسترسی مستقیم به وسط صف نداریم.
اگر بخواهیم عنصر iام صف را سریع (در O(1)) پیدا کنیم، باید حواسمان به front باشد.
اندازه صف با فرمول ساده:
اگر صف ساده است: size = back - front
اگر صف دوری است: باید باقیماندهی تقسیم (mod) را هم لحاظ کنیم.
💡 خلاصه ساده:
صف یعنی نوبت گرفتن!
اول وارد شوی، اول خارج میشوی.
در صف، از ته اضافه میکنی، از سر حذف میکنی.
اگر تعداد عملیات زیاد باشد، صف دوری بهتر است چون از حافظه بهینهتر استفاده میکند.
