تماس درباره   صفحه اصلی
  ساختمان داده > صف  
 
 

صف


صف ساختمان داده ای است که کليه عمليات اضافه از يک سر آن و کليه عمليات حذف از انتهای ديگر آن انجام می پذيرد. صف در نرم افزارهايی صف انتظار را برای دسترسی به منبعی برقرار می کنند کاربرد دارد.

تعريف
نمایش صف
صف حلقوی
کاربردهای صف


تعريف

صف لیست مرتبی است كه عناصر در انتهای آن (Rear) اضافه و از ابتدای آن(Front) حذف می شوند. به عبارت ديگر طول صف از انتهای آن افزایش و از ابتدای آن كاهش می یابد.

اولين عنصری که وارد صف می شود اولين عنصری است که از صف خارج می شود. بنابراين عناصر به همان ترتيبی که به صف اضافه می شوند از آن حذف می شوند. به همين دليل به صف لیست (first in, first out) FIFO نیز گفته می‌شود.

Queue

نمایش صف

پیاده‌سازی صف با آرایه

صف را می توان توسط يک آرايه يک بعدی پیاده سازی کرد. به دو متغیر Front و Rear برای مشخص كردن ابتدا و انتهای صف نياز است.

هر گاه عنصری به صف اضافه شود Rear یك گام به جلو حركت می كند و هر گاه كه عنصری را از صف حذف می شود Front یك واحد افزايش می يابد.

چون اندازه آرايه از قبل تعريف می شود، هنگام اضافه کردن عنصری به صف ابتدا باید اطمينان حاصل کرد که هنوز ظرفیت پذیرش داده را دارد. اگر Rear برابر با ظرفیت كل آرایه شود صف پر درنظر گرفته می شود.

اگر ابتدا و انتهای صف برابر بودند (Front=Rear) یعنی صف خالی است. عمل حذف روی صف خالی انجام نمی گيرد.

طول صف يا تعداد عناصر موجود در صف برابر با Rear-Front+1 است.


مثال. در شکل زير صف به ترتيب شامل عناصر 28، 70، 33 و 125 است. توجه کنيد که Front برابر با صفر است که انديس اولين داده صف يعنی عدد 28 است. و Rear برابر با 3 است که انديس آخرين داده صف يعنی عدد 125 است. طول صف در اين مثال برابر با 4 است (Count=4).

Queue

حذف از صف هميشه ازابتدا (Front) صورت می گيرد. بنابراين 28 از صف حذف می شود و صف به صورت زير درمی آيد.

Queue

صف اکنون از انديس 1 تا انديس 3 می باشد، يعنی شامل اعداد 70، 33 و 125 است. نيازی به پاک کردن عدد 28 از صف نيست زيرا Front مشخص کننده اولين عنصر صف يعنی 70 است.

اگر داده 64 را به صف اضافه کنيم در انتهای صف اضافه می شود.

Queue

اکنون صف پر به نظر می رسد و اگر بخواهيم عددی را اضافه کنيم درصف جائی وجود ندارد. زيرا Rear= MaxSize . MaxSize حداكثر ظرفیت آرایه است كه هنگام تعریف آرایه معین می شود.


صف حلقوی

در مثال فوق هنگام اضافه کرن عدد 99، تعداد عناصر صف كمتر از طول آرایه است ولی صف پر در نظر گرفته می‌شود. برای حل اين مشکل یك روش انتقال عناصر صف به سمت ابتدای آن است تا فضای خالی هميشه در انتهای صف قرار گیرد. که روش مناسبی نيست. روش معمول استفاده از آرایه حلقوی است. يعنی دو انتهای آرايه متصل درنظر گرفته می شود. وقتی انتهای آرايه پر می شود عنصر بعدی در ابتدای آرايه، در صورت بلااستفاده بودن، درج می شود. اين روش را صف حلقوی می نامند.


پیاده‌سازی صف حلقوی به زبان ++C


مثال. با فرض حلقوی بودن صف عنصر جديد 99 در انديس 0 اضافه می شود.

Circular Queue

وقتی Front=(Rear+1)mod MaxSize باشد صف پر درنظر گرفته می شود.

در صف حلقوی اگر Front<Rear است طول صف برابرRear-Front+1 است. درغير اينصورت برابر با MaxSize-Front+Rear+1 است.


پیاده‌سازی صف با لیست پیوندی

در يک ليست پيوندی اگر درج در انتها و حذف از ابتدای آن انجام گيرد يک صف اجرا شده است. مزيت پياده سازی صف توسط ليست پيوندی در اين است که طول صف تنها محدود به حافظه دردسترس است.


پیاده‌سازی صف با لیست پیوندی به زبان C


کاربردهای صف

صف معمولا در سيستم های عامل و نرم افزارهايی که صف انتظار برای دسترسی به منبعی را برقرار می کنند استفاده می شوند. سيستم عامل ممکن است صفی از پروسس هايی که منتظر اجرا روی CPU هستند يا صفی از کارهای که منتظر چاپ هستند را داشته باشد.


سوالات چندگزينه ای درباره صف


 


 


صفحه اصلی| PDF| درباره| تماس