صف (نوع داده انتزاعی)

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از صف (ساختمان داده‌ها))
پرش به: ناوبری، جستجو
تصویر بالا، یک رده (داده‌های در انتظار پردازش در CPU؛ ورود و خروج داده‌ها در جهت مشخص شده انجام می‌شود و عدد 1 ورودی و عدد 0 خروجی هستند) و تصویر پایین یک پشته (دستهٔ کاغذها روی میز؛ تنها به کاغذ رویی دست‌رسی داریم) را نشان می‌دهند

صف[۱] یکی از انواع داده‌ساختارهاست که از آن برای ذخیره و بازیابی داده‌ها بهره می‌برند.

صف [۲] لیستی است که عمل افزودن داده‌ها درون آن از انتهای لیست و عمل حذف داده‌ها از ابتدای لیست انجام می‌شود
مثل یک صف نانوایی داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود، این به این معنی است که شیوهٔ عمل‌کرد صف براساس سیاست FIFO است.

صف در طراحی و پیاده‌سازی سیستم‌های نرم‌افزاری و سخت‌افزاری بسیار استفاده می‌شود.

تفاوت پشته و رده[ویرایش]

  • دستهٔ کاغذها روی میز، مثالی خوب از پشته‌است. در این حالت ما تنها می‌توانیم بر روی دستهٔ کاغذها، کاغذی بگذاریم و از طرفی تنها می‌توانیم از روی دستهٔ کاغذها، کاغذی برداریم (یعنی ورود و خروج از یک سمت انجام می‌گیرد). روشن است که در این حالت آخرین کاغذی که روی دستهٔ کاغذها قرار داده شده، نخستین کاغذی است که برداشته می‌شود و اولین کاغذی که روی میز گذاشته شده، آخر از همه برداشته خواهد شد.
  • رده نانوایی، مثالی خوب از رده است. در این حالت، برخلاف پشته، آدم‌ها به ته رده اضافه می‌شوند و از سر رده خارج می‌شوند (یعنی ورود و خروج از دو سمت متمایز انجام می‌گیرد). به این ترتیب روشن است که آخرین کسی که وارد رده شده، آخرین کسی است که نان دریافت می‌کند و اولین کسی که وارد رده شده، نخستین فردی است که نان می‌گیرد.

توابع[ویرایش]

درابن داده ساختار، دو عمل اصلی تعریف می‌شود، حذف کردن داده ها (Addqueue) واضافه کردن داده ها (Delqueue).برای پیاده سازی این توابع به دو اشاره گر نیازمندیم.یکی Front که همیشه به یک عنصر قبل از عنصر ابتدایی اشاره می‌کند ودیگری rear که همیشه به آخرین عنصر اشاره دارد. دامنه تغییرات front و rear از 0 تا n است و مقادیر اولیه آنها 0 قرار داده می‌شود.شرط پر بودن رده: rear=n

پیاده سازی[ویرایش]


مشابه پشته‌ها، رده ها نیز می‌توانند با انواع داده‌ساختارهایی مثل آرایه یا لیست پیوندی پیاده‌سازی شوند. باز هم، صرف‌نظر از این که از کدام داده‌ساختار استفاده می‌کنیم، پیاده‌سازی دو تابع Enqueue (رده افزایی، افزودن به ته رده) و Dequeue (رده گشایی، خروج از سر رده) ضرورت دارد. اگر فرض کنیم که رده با آرایه پیاده‌سازی شده باشد، شبه‌کد تابع‌های Enqueue و Dequeue به این صورت خواهد بود:

procedure Enqueue(data d)
begin
   endofqueue:=endofqueue+1; //"endofqueue" indicates the number of queue elements
   for i:=2 to endofqueue do
   begin
      queue[i]:=queue[i-1]; //shifting; here "queue" is the array that stores data
   end;
   queue[1]:=d;
end;
 
function Dequeue: data
begin
   result:=queue[endofqueue];
   endofqueue:=endofqueue-1;
end;
شمایی از ورود یک عنصر به رده (Enqueue)
شمایی از خروج یک عنصر از رده (Dequeue)

البته این کدها به ساده‌ترین صورت ممکن نوشته شده‌اند و حالت‌های خاص را در آن‌ها در نظر نگرفته‌ایم.

انواع رده[ویرایش]

رده خطی[ویرایش]

(که در بالا توصیح داده شد)

رده حلقوی[ویرایش]

ایدهٔ رده حلقوی از آنجا شکل می‌گیرد که اگر ما n عنصر را وارد رده کنیم و سپس آنها را یکی یکی حذف کنیم شرط پر بودن رده بر قرار می ماند و این در حالسیت که رده هنوز جای خالی دارد.

در رده حلقوی (دوار) rear و front بعد از رسیدن به آخرین مقدار خود در صورت وجود شرایط لازم مجدداً مقادیر اولیه را می‌توانند بگیرند.

رده حلقوی n عضوی را به صورت آرایهٔ 0 تا n-1 تعریف می کنیم.

در این حالت وقتی rear=n-1 عنصر بعدی در [0]queue قرار می‌گیرد.در رده حلقوی front=rear به معنای خالی بودن رده است ولی شرط پر بودن رده بدین طریق تغییر می‌یابد:

front=(rear+1) mode n

برای اضافه کردن به رده حلقوی rear یکی اضافه می‌شود و در صورتیکه rear=n-1 باید صفر بشود.بدین منظورrear را با رابطه زیر در هر شرایطی مقدار دهی می‌کنند:

rear=(rear+1) mode n

این مساله برای front هم بر قرار است:

front=(front+1) mode n

در این نوع رده، شبه‌کد[۳] توابع اضافه و حذف به شرح زیر است:

Void Addqueue(int x )
{ 
rear=(rear+1) mode n
if (front==rear)
Cout"the queue is empty"
else
queue[rear]=x{
}
 
{{Lr footer}}
{{Lr header}}
Void Delqueue(int x )
{ 
if (front==rear)
{
Cout"the queue is empty"
return 0
}
else
front=(front+1) mode n
x=queue[front]
}

رده اولویت دار[ویرایش]

در رده عادی از تکنیک FIFO - مخفف First In First Out استفاده می‌شوداما در رده اولویتی برای هر داده اولویتی - نه لزوماً منحصر بفرد - مشخص می‌شود. رده اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم‌عامل کامپیوتر هم برای مدیریت پردازش‌ها از صفهای اولویت استفاده می‌کند.

به عنوان مثال فرض کنید پردازش‌های زیر در انتظار اختصاص CPU به خود هستند:

  6   5    4   3   2   1     شماره پردازش
  4   5    3   1   2   4    اولویت  

رده انتظار CPU یک رده اولویت دار است. در نتیجه CPU در اولین فرصت ممکن ابتدا پردازش شماره 3 را انجام می‌دهد. سپس پردازش شماره 2 و . . .

تذکر: روش‌های زمان بندی CPU جهت انجام پردازش‌های مختلف یکی از بحث‌های جذاب و در عین حال مهم مبحث سیستم‌عامل است. بررسی تمامی روشهای زمان بندی و مزایا و معایب آنها خارج از بحث فعلی ماست.

پیچیدگی زمانی در پیاده‌سازی آرایه‌ای[ویرایش]

پیچیدگی زمانی [۴] افزودن عنصری به رده در پیاده‌سازی آرایه‌ای، با پیچیدگی زمانی خروج عنصری از رده تفاوت دارد. در مورد افزودن یک عنصر، از (O(n است که n نشان‌دهندهٔ تعداد عنصرهای موجود در رده است. علت این امر آن است که با ورود هر عنصر به ته رده، همهٔ عنصرهای دیگر باید به اندازهٔ یکی جابه‌جا شوند تا جا برای این عنصر تازه باز شود. این در حالی است که خروج یک عنصر از رده دارای پیچیدگی زمانی از (O(1 است.

می‌بینیم که در پیاده‌سازی آرایه‌ای، پیچیدگی زمانی افزودن و برداشتن عنصرها از رده و به رده، با هم متفاوت است. با این وجود اگر رده را با لیست‌های پیوندی پیاده‌سازی کنیم، به علت ساختار خاص این لیست‌ها، هردوی این اعمال برای هم رده (و به همین شکل برای پشته)، دارای پیچیدگی زمانی از (O(1 خواهد بود.

کاربردها[ویرایش]

از رده ها در کاربری‌هایی که در آن‌ها، اشیاء، پدیده‌ها و روی‌دادها در انتظارند تا پردازش شوند، بیش‌تر استفاده می‌شود. مدیریت پیام‌ها در سیستم‌عاملی مثل ویندوز[۵]، مدیریت فهرست کارهایی که باید به ترتیب انجام شوند، پیاده‌سازی الگوریتم جستجوی سطح اول[۶] و... از جمله مواردی است که در آن‌ها از رده ها استفاده می‌شود.

توسعه[ویرایش]

از ترکیب رده و پشته، داده‌ساختار جدیدی[۷] هم ایجاد شده‌است که هم امکان افزودن عنصرها را از دوسوی تودهٔ داده‌ها می‌دهد و هم امکان برداشتن آن‌ها را.

پیوندهای بیرونی و منابع[ویرایش]

پانویس[ویرایش]