ویکی‌پدیا

صف (نوع داده انتزاعی): تفاوت میان نسخه‌ها

نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
جز ←‏رده حلقوی: مسأله --> مسئله وپ:همزه با استفاده از AWB
/* تفاوت پشته و صف/*
خط ۱:
[[پرونده:QueueStack.gif|بندانگشتی|180px|چپ|تصویر بالا، یک ردهصف (داده‌های در انتظار پردازش در CPU؛ ورود و خروج داده‌ها در جهت مشخص شده انجام می‌شود و عدد 1 ورودی و عدد 0 خروجی هستند) و تصویر پایین یک پشته (دستهٔ کاغذها روی میز؛ تنها به کاغذ رویی دست‌رسی داریم) را نشان می‌دهند]]
'''صف'''<ref name="ReferenceA">[//en.wikipedia.org/wiki/Queue_(data_structure) Queue]</ref> یکی از انواع داده‌ساختارهاست که از آن برای ''ذخیره'' و ''بازیابی'' داده‌ها بهره می‌برند.
 
خط ۶:
صف در طراحی و پیاده‌سازی سیستم‌های نرم‌افزاری و سخت‌افزاری بسیار استفاده می‌شود.
 
== تفاوت پشته و ردهصف ==
* '''دستهٔ کاغذها روی میز'''، مثالی خوب از پشته‌است. در این حالت ما تنها می‌توانیم بر '''روی''' دستهٔ کاغذها، کاغذی بگذاریم و از طرفی تنها می‌توانیم از '''روی''' دستهٔ کاغذها، کاغذی برداریم (یعنی ورود و خروج از یک سمت انجام می‌گیرد). روشن است که در این حالت آخرین کاغذی که روی دستهٔ کاغذها قرار داده شده، نخستین کاغذی است که برداشته می‌شود و اولین کاغذی که روی میز گذاشته شده، آخر از همه برداشته خواهد شد.
* '''ردهصف نانوایی'''، مثالی خوب از ردهصف است. در این حالت، برخلاف پشته، آدم‌ها به '''ته ردهصف''' اضافه می‌شوند و از '''سر ردهصف''' خارج می‌شوند (یعنی ورود و خروج از دو سمت متمایز انجام می‌گیرد). به این ترتیب روشن است که آخرین کسی که وارد ردهصف شده، آخرین کسی است که نان دریافت می‌کند و اولین کسی که وارد ردهصف شده، نخستین فردی است که نان می‌گیرد.
 
== توابع ==
درابن داده ساختار، دو عمل اصلی تعریف می‌شود، حذف کردن داده ها (Addqueue) واضافه کردن داده ها (Delqueue).برای پیاده سازی این توابع به دو [[اشاره گر]] نیازمندیم.یکی Front که همیشه به یک عنصر قبل از عنصر ابتدایی اشاره می‌کند ودیگری rear که همیشه به آخرین عنصر اشاره دارد.
[[دامنه تغییرات]] front و rear از 0 تا n است و مقادیر اولیه آنها 0 قرار داده می‌شود.شرط پر بودن ردهصف: rear=n
 
== پیاده سازی ==
{{-}}
مشابه پشته‌ها، ردهصف ها نیز می‌توانند با انواع داده‌ساختارهایی مثل آرایه یا [[لیست پیوندی]] پیاده‌سازی شوند. باز هم، صرف‌نظر از این که از کدام داده‌ساختار استفاده می‌کنیم، پیاده‌سازی دو تابع '''Enqueue''' (ردهصف افزایی، افزودن به ته ردهصف) و '''Dequeue''' (ردهصف گشایی، خروج از سر ردهصف) ضرورت دارد.
اگر فرض کنیم که ردهصف با آرایه پیاده‌سازی شده باشد، شبه‌کد تابع‌های Enqueue و Dequeue به این صورت خواهد بود:
 
<source lang="pascal">
خط ۳۷:
</source>
 
[[پرونده:Enqueue.gif|بندانگشتی|80px|چپ|شمایی از ورود یک عنصر به ردهصف (Enqueue)]]
[[پرونده:Dequeue.gif|بندانگشتی|80px|چپ|شمایی از خروج یک عنصر از ردهصف (Dequeue)]]
 
البته این کدها به ساده‌ترین صورت ممکن نوشته شده‌اند و حالت‌های خاص را در آن‌ها در نظر نگرفته‌ایم.
 
== انواع ردهصف ==
 
=== ردهصف خطی ===
(که در بالا توصیح داده شد)
 
=== ردهصف حلقوی ===
ایدهٔ ردهصف حلقوی از آنجا شکل می‌گیرد که اگر ما n عنصر را وارد ردهصف کنیم و سپس آنها را یکی یکی حذف کنیم شرط پر بودن ردهصف بر قرار می ماند و این در حالسیت که ردهصف هنوز جای خالی دارد.
 
در ردهصف حلقوی (دوار) rear و front بعد از رسیدن به آخرین مقدار خود در صورت وجود شرایط لازم مجدداً مقادیر اولیه را می‌توانند بگیرند.
 
ردهصف حلقوی n عضوی را به صورت آرایهٔ 0 تا n-1 تعریف می کنیم.
 
در این حالت وقتی rear=n-1 عنصر بعدی در [0]queue قرار می‌گیرد.در ردهصف حلقوی front=rear به معنای خالی بودن ردهصف است ولی شرط پر بودن ردهصف بدین طریق تغییر می‌یابد:
 
<source lang="c">front=(rear+1) mode n </source>
 
برای اضافه کردن به ردهصف حلقوی rear یکی اضافه می‌شود و در صورتیکه rear=n-1 باید صفر بشود.بدین منظورrear را با رابطه زیر در هر شرایطی مقدار دهی می‌کنند:
 
<source lang="c">rear=(rear+1) mode n</source>
خط ۶۶:
<source lang="c">front=(front+1) mode n </source>
 
در این نوع رده،صف، [[شبه‌کد]]<ref>[//en.wikipedia.org/wiki/Pseudocode Pseudocode]</ref> توابع اضافه و حذف به شرح زیر است:
 
<source lang="c">
خط ۹۳:
</source>
 
=== ردهصف اولویت دار ===
در ردهصف عادی از تکنیک FIFO - مخفف First In First Out استفاده می‌شوداما در ردهصف اولویتی برای هر داده اولویتی - نه لزوماً منحصر بفرد - مشخص می‌شود. ردهصف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم‌عامل کامپیوتر هم برای مدیریت پردازش‌ها از صفهای اولویت استفاده می‌کند.
 
به عنوان مثال فرض کنید پردازش‌های زیر در انتظار اختصاص CPU به خود هستند:
خط ۱۰۲:
4 5 3 1 2 4 اولویت
 
ردهصف انتظار CPU یک ردهصف اولویت دار است. در نتیجه CPU در اولین فرصت ممکن ابتدا پردازش شماره 3 را انجام می‌دهد. سپس پردازش شماره 2 و [[. . .]]
 
تذکر: روش‌های زمان بندی CPU جهت انجام پردازش‌های مختلف یکی از بحث‌های جذاب و در عین حال مهم مبحث سیستم‌عامل است. بررسی تمامی روشهای زمان بندی و مزایا و معایب آنها خارج از بحث فعلی ماست.
خط ۱۰۸:
== پیچیدگی زمانی در پیاده‌سازی آرایه‌ای ==
 
[[پیچیدگی زمانی]] <ref>[//en.wikipedia.org/wiki/Time_complexity Time Complexity]</ref> افزودن عنصری به ردهصف در پیاده‌سازی آرایه‌ای، با پیچیدگی زمانی خروج عنصری از ردهصف تفاوت دارد. در مورد افزودن یک عنصر، از (O(n است که n نشان‌دهندهٔ تعداد عنصرهای موجود در ردهصف است. علت این امر آن است که با ورود هر عنصر به ته رده،صف، همهٔ عنصرهای دیگر باید به اندازهٔ یکی جابه‌جا شوند تا جا برای این عنصر تازه باز شود. این در حالی است که خروج یک عنصر از ردهصف دارای پیچیدگی زمانی از (O(1 است.
 
می‌بینیم که در پیاده‌سازی آرایه‌ای، پیچیدگی زمانی افزودن و برداشتن عنصرها از ردهصف و به رده،صف، با هم متفاوت است. با این وجود اگر ردهصف را با لیست‌های پیوندی پیاده‌سازی کنیم، به علت ساختار خاص این لیست‌ها، هردوی این اعمال برای هم ردهصف (و به همین شکل برای [[پشته]])، دارای پیچیدگی زمانی از (O(1 خواهد بود.
 
== کاربردهاکاربصفا ==
از ردهصف ها در کاربری‌هایی که در آن‌ها، اشیاء، پدیده‌ها و روی‌دادها در انتظارند تا پردازش شوند، بیش‌تر استفاده می‌شود. مدیریت پیام‌ها در سیستم‌عاملی مثل [[ویندوز]]<ref>[//en.wikipedia.org/wiki/Windows Windows]</ref>، مدیریت فهرست کارهایی که باید به ترتیب انجام شوند، پیاده‌سازی الگوریتم [[جستجوی سطح اول]]<ref>[//en.wikipedia.org/wiki/Breadth-first_search Breadth-first Search]</ref> و... از جمله مواردی است که در آن‌ها از ردهصف ها استفاده می‌شود.
 
== توسعه ==
از ترکیب ردهصف و پشته، داده‌ساختار جدیدی<ref>[//en.wikipedia.org/wiki/Deque Deque]</ref> هم ایجاد شده‌است که هم امکان افزودن عنصرها را از دوسوی تودهٔ داده‌ها می‌دهد و هم امکان برداشتن آن‌ها را.
 
== پیوندهای بیرونی و منابع ==
* [http://zohrevand.blogfa.com/post-30.aspx ساختمان داده ها]
* [http://www.itech2.info/showthread.php?s=17d329f6ffabedb3f1922ae4b9d8eaac&t=39058 ردهصف]
* [http://hamilton.bell.ac.uk/swdev2/notes/notes_13.pdf the queue data structure]
* [http://www.barnamenevis.org/forum/showthread.php?t=116128&page=2 ردهصف]
* [http://club5.persiangig.com/PDF/SakhtemanDade1.pdf ساختمان داده ها]
* [http://www.learning-computer-programming.blogspot.com/2007/07/data-structures-introduction-to-queues.html Introduction to Queues]
برگرفته از «https://fa.wikipedia.org/wiki/صف_(نوع_داده_انتزاعی)»