صف (ساختمان داده‌ها)

برای دیگر کاربردها، صف (ابهام‌زدایی) را ببینید.

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

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

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

تفاوت پشته و صف

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

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

توابع

درابن داده ساختار، دو عمل اصلی تعریف می‌شود، حذف کردن داده ها(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
}

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 خواهد بود.

کاربردها

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

توسعه

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

پیوندهای بیرونی و منابع

• ساختمان داده ها
• صف
• the queue data structure
• صف
• ساختمان داده ها
• Introduction to Queues
• صف اولویت دار