ویکی‌پدیا

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

نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
بدون خلاصۀ ویرایش
برچسب: پیوند بیش از حد به ویکی‌های دیگر (AF)
بدون خلاصۀ ویرایش
خط ۱۲:
 
== توابع ==
درابن داده ساختار، دو عمل اصلی تعریف می‌شود، حذف کردن داده ها (Addqueue) واضافه کردن داده ها (Delqueue).برای پیاده سازی این توابع به دو اشاره گر نیازمندیم.یکی Front که همیشه به یک عنصر قبل از عنصر ابتدایی اشاره می‌کند ودیگری rear که همیشه به آخرین عنصر اشاره دارد.
دامنه تغییرات front و rear از 0 تا n است و مقادیر اولیه آنها 0 قرار داده می‌شود.شرط پر بودن رده: rear=n
 
== پیاده سازی ==
}{{سخ-}}▼
مشابه پشته‌ها، رده ها نیز می‌توانند با انواع داده‌ساختارهایی مثل آرایه یا لیست پیوندی پیاده‌سازی شوند. باز هم، صرف‌نظر از این که از کدام داده‌ساختار استفاده می‌کنیم، پیاده‌سازی دو تابع '''Enqueue''' (رده افزایی، افزودن به ته رده) و '''Dequeue''' (رده گشایی، خروج از سر رده) ضرورت دارد.
اگر فرض کنیم که رده با آرایه پیاده‌سازی شده باشد، شبه‌کد تابع‌های Enqueue و Dequeue به این صورت خواهد بود:
 
<source lang="pascal">
procedure Enqueue(data d)
begin
endofqueue:=endofqueue+1; //"endofqueue" indicates the number of queue elements
سطر ۳۳ ⟵ ۳۵:
result:=queue[endofqueue];
endofqueue:=endofqueue-1;
end;
</source>
 
[[پرونده:Enqueue.gif|بندانگشتی|80px|چپ|شمایی از ورود یک عنصر به رده (Enqueue)]]
سطر ۴۴ ⟵ ۴۷:
=== رده خطی ===
(که در بالا توصیح داده شد)
 
=== رده حلقوی ===
ایدهٔ رده حلقوی از آنجا شکل می‌گیرد که اگر ما n عنصر را وارد رده کنیم و سپس آنها را یکی یکی حذف کنیم شرط پر بودن رده بر قرار می ماند و این در حالسیت که رده هنوز جای خالی دارد.
 
در رده حلقوی (دوار) rear وfrontو front بعد از رسیدن به آخرین مقدار خود در صورت وجود شرایط لازم مجددامقادیرمجددا مقادیر اولیه را می‌توانند بگیرند.
 
رده حلقوی n عضوی را به صورت آرایهٔ 0 تا n-1 تعریف می کنیم.
سطر ۵۳ ⟵ ۵۷:
در این حالت وقتی rear=n-1 عنصر بعدی در [0]queue قرار می‌گیرد.در رده حلقوی front=rear به معنای خالی بودن رده است ولی شرط پر بودن رده بدین طریق تغییر می‌یابد:
 
<centersource lang="c">front=(rear+1) mode n </centersource>
 
برای اضافه کردن به رده حلقوی rear یکی اضافه می‌شود و در صورتیکه rear=n-1 باید صفر بشود.بدین منظورrear را با رابطه زیر در هر شرایطی مقدار دهی می‌کنند:
 
<centersource lang="c">rear=(rear+1) mode n{{سخ}}</centersource>
 
این مساله برای front هم بر قرار است:
 
<centersource lang="c">front=(front+1) mode n </centersource>
 
در این نوع رده، [[شبه‌کد]]<ref>[http://en.wikipedia.org/wiki/Pseudocode Pseudocode]</ref> توابع اضافه و حذف به شرح زیر است:
 
{{Lr header}}
<source lang="c">
 
Void Addqueue(int x )
{{سخ}}
rear=(rear+1) mode n{{سخ}}▼
{ {{سخ}}
if (front==rear){{سخ}}▼
▲rear=(rear+1) mode n{{سخ}}
Cout"the queue is empty"{{سخ}}▼
▲if (front==rear){{سخ}}
else
▲Cout"the queue is empty"{{سخ}}
queue[rear]=x{{سخ}}▼
else{{سخ}}
}
▲queue[rear]=x{{سخ}}
▲}{{سخ}}
 
{{Lr footer}}
{{Lr header}}
Void Delqueue(int x )
{{سخ}}
if (front==rear){{سخ}}▼
{ {{سخ}}
{
▲if (front==rear){{سخ}}
Cout"the queue is empty"{{سخ}}▼
{{{سخ}}
return 0{{سخ}}▼
▲Cout"the queue is empty"{{سخ}}
}
▲return 0{{سخ}}
else
}{{سخ}}
front=(front+1) mode n{{سخ}}▼
else{{سخ}}
x=queue[front]{{سخ}}▼
▲front=(front+1) mode n{{سخ}}
}
▲x=queue[front]{{سخ}}
}{{سخ}}
{{Lr footer}}
</source>
 
=== رده اولویت دار ===
در رده عادی از تکنیک FIFO - مخفف First In First Out - استفاده می‌شوداما در رده اولویتی برای هر داده اولویتی - نه لزوما منحصر بفرد - مشخص می‌شود. رده اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم‌عامل کامپیوتر هم برای مدیریت پردازش‌ها از صفهای اولویت استفاده می‌کند.
 
به عنوان مثال فرض کنید پردازش‌های زیر در انتظار اختصاص CPU به خود هستند:
 
6 5 4 3 2 1 شماره پردازش
 
4 5 3 1 2 4 اولویت
 
رده انتظار CPU یک رده اولویت دار است. در نتیجه CPU در اولین فرصت ممکن ابتدا پردازش شماره 3 را انجام می‌دهد. سپس پردازش شماره 2 و . . .
سطر ۱۱۱ ⟵ ۱۱۶:
 
== کاربردها ==
 
از رده ها در کاربری‌هایی که در آن‌ها، اشیاء، پدیده‌ها و روی‌دادها در انتظارند تا پردازش شوند، بیش‌تر استفاده می‌شود. مدیریت پیام‌ها در سیستم‌عاملی مثل [[ویندوز]]<ref>[http://en.wikipedia.org/wiki/Windows Windows]</ref>، مدیریت فهرست کارهایی که باید به ترتیب انجام شوند، پیاده‌سازی الگوریتم [[جستجوی سطح اول|جست‌وجوی سطح اول]]<ref>[http://en.wikipedia.org/wiki/Breadth-first_search Breadth-first Search]</ref> و... از جمله مواردی است که در آن‌ها از رده ها استفاده می‌شود.
 
== توسعه ==
از ترکیب رده و پشته، داده‌ساختار جدیدی<ref>[http://en.wikipedia.org/wiki/Deque Deque]</ref> هم ایجاد شده‌است که هم امکان افزودن عنصرها را از دوسوی تودهٔ داده‌ها می‌دهد و هم امکان برداشتن آن‌ها را.
 
{{ساختمان داده‌ها}}▼
== پیوندهای بیرونی و منابع ==
* [http://zohrevand.blogfa.com/post-30.aspx ساختمان داده ها]
سطر ۱۲۷ ⟵ ۱۳۱:
 
== پانویس ==
 
{{پانویس}}
 
▲{{ساختمان داده‌ها}}
 
[[رده:ساختمان داده]]
برگرفته از «https://fa.wikipedia.org/wiki/صف_(نوع_داده_انتزاعی)»