صف (نوع داده انتزاعی) کیست؟ توضیح بده.
صف، یکی از انواع داده‌ساختارهاست که از آن برای "ذخیره" و "بازیابی" داده‌ها بهره می‌برند.صف لیستی است که عمل افزودن داده‌ها درون آن از انتهای لیست و عمل حذف داده‌ها از ابتدای لیست انجام می‌شودمثل یک صف نانوایی داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود، این به این معنی است که شیوهٔ عملکرد صف براساس سیاست 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: databegin result:=queue[endofqueue]; endofqueue:=endofqueue-1;end;البته این کدها به ساده‌ترین صورت ممکن نوشته شده‌اند و حالت‌های خاص را در آن‌ها در نظر نگرفته‌ایم.انواع صف.صف حلقوی.ایدهٔ صف حلقوی از آنجا شکل می‌گیرد که اگر ما 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 nif (front==rear)Cout"the queue is empty"elsequeue[rear]=x{Void Delqueue(int x )if (front==rear)Cout"the queue is empty"return 0elsefront=(front+1) mode nx=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 خواهد بود.پیاده‌سازی تابعی محض.صف‌ها همچین می‌توانند به عنوان داده ساختار تابعی محض پیاده‌سازی شوند. دو نسخه از این پیاده‌سازی وجود دارد. اولی که در زیر توضیح داده شده‌است صف بلا درنگ نام دارد. این پیاده‌سازی این امکان را به صف‌ها می‌دهد که با پیچیدگی زمانی formula_1ماندگار باشند، اما به لیست‌های کندرو با مموایز کردن نیاز دارند. پیاده‌سازی دوم به لیست‌های کندرو و مموایز کردن نیاز ندارد و در انتهای این بخش توضیح داده شده‌است. پیچیدگی زمانی سرشکن پیاده‌سازی دوم اگر ماندگاری نباشد formula_1 است، اما پیچیدگی بدترین حالتش formula_3 است و formula_4تعداد عناصر موجود در صف است.فرض کنیم برای لیستی مانند formula_5، formula_6طول لیست، formula_7نشانگر لیست خالی و formula_8 نشانگر لیستی باشد که formula_9آن formula_10و formula_11آن formula_12است.لیست بلا درنگ.داده ساختار استفاده شده برای پیاده‌سازی صف‌هایمان از سه لیست پیوندی formula_13تشکیل شده‌است که formula_14جلوی صف، formula_15عقب صف در ترتیب برعکس است. ثابت formula_16نشانگر formula_16عنصر عقب formula_14بدون formula_19عنصر پشتی آن است، formula_20. formula_11صف formula_22تقریباً formula_13است و اضافه کردن عنصری مانند formula_24به formula_13تقریباً formula_26است. به این دلیل تقریبی می‌گوییم که در جفت نتیجه‌ها formula_27است.تابع کمکی formula_28برای ثابت صدا زده شود تا در فرض مساله صدق کند و خللی به وجود نیاید. بسته به اینکه formula_16لیست خالی باشد یا نه دو حالت باید در نظر گرفته شود که اگر خالی باشد: formula_30. تعریف رسمی این گونه است formula_31و formula_32که formula_33formula_14ای است که توسط عکس formula_15 دنبال شده‌است.تابع formula_36 که خروجی آن formula_14ای دنبال شده توسط برعکس formula_15است را صدا می‌کنیم. علاوه بر آن فرض می‌کنیم formula_30، چون در حالتی است که این تابع صدا زده شده‌است. به‌طور جزئی‌تر، ما تابع کندرو formula_40را تعریف می‌کنیم که سه لیست ورودی می‌گیرد که formula_30 است و خروجی آن الحاق formula_14، برعکس formula_15و formula_44است. آنگاه formula_45. تعریف استقرایی تابع چرخش این چنین است که formula_46و formula_47. پیچیدگی زمانی آن formula_48است اما چون از ارزیابی کندرو استفاده شده‌است تا زمانی که نتیجه محاسبات ضروری نباشد محاسبات به تعویق می‌افتد.صف سرشکن‌شده.بدون بخش کندروی محاسباتِ پیاده‌سازی، صف بلا درنگ پیاده‌سازی غیر‌ماندگاری از صف در پیچیدگی زمانی سرشکن formula_49 خواهد بود. در این حالت، لیست formula_16 می‌تواند با عدد صحیح formula_51 جایگزین شود و تابع reverse زمانی صدا زده می‌شود که formula_16صفر باشد.کاربرد صف‌ها.از صف‌ها در کاربری‌هایی که در آن‌ها، اشیاء، پدیده‌ها و روی‌دادها در انتظارند تا پردازش شوند، بیش‌تر استفاده می‌شود. مدیریت پیام‌ها در سیستم‌عاملی مثل ویندوز، مدیریت فهرست کارهایی که باید به ترتیب انجام شوند، پیاده‌سازی الگوریتم جستجوی سطح اول و... از جمله مواردی است که در آن‌ها از صف‌ها استفاده می‌شود.توسعه.از ترکیب صف و پشته، داده‌ساختار جدیدی هم ایجاد شده‌است که هم امکان افزودن عنصرها را از دوسوی تودهٔ داده‌ها می‌دهد و هم امکان برداشتن آن‌ها را.