صف یا Queue چیست؟
صف (Queue) عنوان ساختمان دادهای است که مجموعهای از المانها (عناصر) را بر اساس اصل FIFO (خروج به ترتیب ورود) در خود نگهداری میکند.
برای Queue دو عمل اصلی تعریف میشود. عمل Enqueue که عنصر جدیدی را به انتهای آن (که rear نامیده میشود) اضافه میکند و عمل Dequeue که عنصری را از ابتدای آن (که front نامیده میشود) حذف میکند. به این ترتیب اولین عنصری که به یک Queue افزوده میشود اولین عنصری خواهد بود که از آن حذف خواهد شد. از این رو، صفها را نوعی ساختمان دادهی FIFO به شمار میآورند. در برخی از پیادهسازیها، عملی به نام Front یا Peek نیز تعریف میشود که مقدار المان اول را بدون حذف آن برمیگرداند.
هنگامی که میخواهیم داده یا المانی را برای مدتی نگهداری و در آینده مورد پردازش قرار دهیم به کاربردن صف از جمله بهترین راهکارهایی به شمار میرود که برای این منظور استفاده میشود. در چنین حالتی صف، نقش یک بافر را ایفا میکند. یکی از مهمترین کاربردهای این ساختمان داده در الگوریتمهای زمان بندی میباشد.
پیادهسازی صف
هرچند از نظر تئوری میتوان صفها را به صورت نامتناهی و بدون محدودیت در ظرفیت تجسم نمود اما در صورتی که صف را توسط آرایهای با طول ثابت پیاده سازی کنیم ظرفیت آن ثابت خواهد بود. با درنظر گرفتن این آرایه به صورت یک دایره میتوان یک صف حلقوی ایجاد نمود. در این نوع Queue لزوما انتهای آرایه، انتهای صف نیست بلکه میتوان از فضای خالی به وجود آمده در ابتدای آرایه (به دلیل اعمال Dequeue)، برای افزودن عناصر جدید استفاده نمود. در صورتی که Queue پر باشد و بخواهیم عنصر جدیدی به آن اضافه کنیم حالتی به نام سرریز (Overflow) رخ میدهد. به طور مشابه در صورتی که بخواهیم روی یک Queue خالی، عمل Dequeue را انجام دهیم حالت زیرریز (Underflow) رخ خواهد داد.
استفاده از لیستهای پیوندی (Linked List) برای پیادهسازی صف میتواند محدودیت تعداد عناصر قابل نگهداری در این ساختمان داده را از میان بردارد. به عبارت بهتر در این نوع پیاده سازی برخلاف حالتی که از آرایه برای انجام این کار استفاده میشود نیازی به مشخص نمودن ظرفیت صف هنگام ایجاد آن وجود ندارد.
پیوندهای پیشنهادی تک دیک
