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

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

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

صف [1] لیستی است که عمل افزودن داده‌ها درون آن از انتهای لیست و عمل حذف داده‌ها از ابتدای لیست انجام می‌شود
مثل یک صف نانوایی داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود، این به این معنی است که شیوهٔ عمل‌کرد صف براساس سیاست 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

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

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 جهت انجام پردازش‌های مختلف یکی از بحث‌های جذاب و در عین حال مهم مبحث سیستم‌عامل است. بررسی تمامی روش‌های زمان بندی و مزایا و معایب آن‌ها خارج از بحث فعلی ماست.

پیچیدگی زمانی در پیاده‌سازی آرایه‌ای

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

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

پیاده‌سازی تابعی محض[4]

صف‌ها همچین می‌توانند به عنوان داده ساختار تابعی محض پیاده‌سازی شوند. دو نسخه از این پیاده‌سازی وجود دارد. اولی که در زیر توضیح داده شده‌است صف بلا درنگ نام دارد. این پیاده‌سازی این امکان را به صف‌ها می‌دهد که با پیچیدگی زمانی ${\displaystyle O(1)}$ماندگار باشند، اما به لیست‌های کندرو با مموایز کردن نیاز دارند. پیاده‌سازی دوم به لیست‌های کندرو و مموایز کردن نیاز ندارد و در انتهای این بخش توضیح داده شده‌است. پیچیدگی زمانی سرشکن پیاده‌سازی دوم اگر ماندگاری نباشد ${\displaystyle O(1)}$ است، اما پیچیدگی بدترین حالتش ${\displaystyle O(n)}$ است و ${\displaystyle n}$تعداد عناصر موجود در صف است.

فرض کنیم برای لیستی مانند ${\displaystyle l}$، ${\displaystyle |l|}$طول لیست، ${\displaystyle nil}$نشانگر لیست خالی و ${\displaystyle CONS(h,t)}$ نشانگر لیستی باشد که ${\displaystyle head}$آن ${\displaystyle h}$و ${\displaystyle tail}$آن ${\displaystyle t}$است.

لیست بلا درنگ

داده ساختار استفاده شده برای پیاده‌سازی صف‌هایمان از سه لیست پیوندی ${\displaystyle (f,r,s)}$تشکیل شده‌است که ${\displaystyle f}$جلوی صف، ${\displaystyle r}$عقب صف در ترتیب برعکس است. ثایت ${\displaystyle s}$نشانگر ${\displaystyle s}$عنصر عقب ${\displaystyle f}$بدون ${\displaystyle |r|}$عنصر پشتی آن است، ${\displaystyle |s|=|f|-|r|}$. ${\displaystyle tail}$صف ${\displaystyle (CONS(x,f),r,s)}$تقریباً ${\displaystyle (f,r,s)}$است و اضافه کردن عنصری مانند ${\displaystyle x}$به ${\displaystyle (f,r,s)}$تقریباً ${\displaystyle (f,CONS(x,r),s)}$است. به این دلیل تقریبی می‌گوییم که در جفت نتیجه‌ها ${\displaystyle |s|=|f|-|r|+1}$است.

تابع کمکی ${\displaystyle aux}$برای ثابت صدا زده شود تا در فرض مساله صدق کند و خللی به وجود نیاید. بسته به اینکه ${\displaystyle s}$لیست خالی باشد یا نه دو حالت باید در نظر گرفته شود که اگر خالی باشد: ${\displaystyle |r|=|f|+1}$. تعریف رسمی این گونه است ${\displaystyle aux(f,r,Cons(_{,}s))=(f,r,s)}$و ${\displaystyle aux(f,r,nil)=({\acute {f}},nil,{\acute {f}})}$که ${\displaystyle f'}$${\displaystyle f}$ای است که توسط عکس ${\displaystyle r}$ دنبال شده‌است.

تابع ${\displaystyle reverse(f,r)}$ که خروجی آن ${\displaystyle f}$ای دنبال شده توسط برعکس ${\displaystyle r}$است را صدا می‌کنیم. علاوه بر آن فرض می‌کنیم ${\displaystyle |r|=|f|+1}$، چون در حالتی است که این تابع صدا زده شده‌است. به‌طور جزئی‌تر، ما تابع کندرو ${\displaystyle rotate(f,r,a)}$را تعریف می‌کنیم که سه لیست ورودی می‌گیرد که ${\displaystyle |r|=|f|+1}$ است و خروجی آن الحاق ${\displaystyle f}$، برعکس ${\displaystyle r}$و ${\displaystyle a}$است. آنگاه ${\displaystyle reverse(f,r)=rotate(f,r,nill)}$. تعریف اسقرایی تابع چرخش این چنین است که ${\displaystyle rotate(nil,Cons(y,nil),a)=Cons(y,a)}$و ${\displaystyle rotate(Cons(x,f),Cons(y,r),a)=Cons(x,rotate,rotate(f,r,Cons(y,a)))}$. پیچیدگی زمانی آن ${\displaystyle O(r)}$است اما چون از ارزیابی کندرو استفاده شده‌است تا زمانی که نتیجه محاسبات ضروری نباشد محاسبات به تعویق می‌افتد.

صف سرشکن‌شده

بدون بخش کندروی محاسباتِ پیاده‌سازی، صف بلا درنگ پیاده‌سازی غیرماندگاری از صف در پیچیدگی زمانی سرشکن ${\displaystyle O(1)}$ خواهد بود. در این حالت، لیست ${\displaystyle s}$ می‌تواند با عدد صحیح ${\displaystyle |f|-|r|}$ جایگزین شود و تابع reverse زمانی صدا زده می‌شود که ${\displaystyle s}$صفر باشد.

کاربرد صف‌ها

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

توسعه

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

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

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

پانویس

1. Queue
2. Pseudocode
3. Time Complexity
4. Okasaki، Chris. Purely Functional Data Structures.
5. Windows
6. Breadth-first Search
7. Deque