تبلیغات
فناوری اطلاعات و ارتباطات - صف
به وبلاگ آموزشی فناوری اطلاعات و ارتباطات خوش آمدید ....... امید است که از مطالب آموزشی نهایت استفاده را برده باشید با نظرات پر بارتان من را در اداره و سر و سامان دادن به وبلاگ یاری نمایید .......... با تشکر ...... مدیریت بلاگ

تبلیغات پیامکی


بازدید : مرتبه
تاریخ : یکشنبه 28 فروردین 1390

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

 

جهت مشاهده ادامه به ادامه مطلب مراجعه نمایید ...

تعریف

صف لیست مرتبی است كه عناصر در انتهای آن (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 هستند یا صفی از کارهای که منتظر چاپ هستند را داشته باشد.


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




طبقه بندی: ساختمان داده ها، 
ارسال توسط عباس غلامی
آرشیو مطالب
نظر سنجی
نظرتون در مورد وبلاگ چیه ....





پیوند های روزانه
امکانات جانبی

قالب وبلاگ

پیامک عاشقانه