یکی از انواع داده‌ساختارهاست که از آن برای و داده‌ها بهره می‌برند.
 لیستی است که عمل افزودن داده‌ها درون آن از انتهای لیست و عمل حذف داده‌ها از ابتدای لیست انجام می‌شود مثل یک صف نانوایی داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود، این به این معنی است که شیوهٔ عمل‌کرد صف براساس سیاست است.
 صف در طراحی و پیاده‌سازی سیستم‌های نرم‌افزاری و سخت‌افزاری بسیار استفاده می‌شود.
 
 در این داده ساختار، دو عمل اصلی تعریف می‌شود، حذف کردن داده‌ها (Addqueue) واضافه کردن داده‌ها (Delqueue).برای پیاده‌سازی این توابع به دو نیازمندیم.یکی Front که همیشه به یک عنصر قبل از عنصر ابتدایی اشاره می‌کند ودیگری rear که همیشه به آخرین عنصر اشاره دارد.
 front و rear از 0 تا n است و مقادیر اولیه آن‌ها 0 قرار داده می‌شود.شرط پر بودن صف: rear=n
 مشابه پشته‌ها، صف‌ها نیز می‌توانند با انواع ساختارداده هایی مثل آرایه یا پیاده‌سازی شوند. باز هم، صرف‌نظر از این که از کدام ساختارداده استفاده می‌کنیم، پیاده‌سازی دو تابع (صف افزایی، افزودن به ته صف) و (صف گشایی، خروج از سر صف) ضرورت دارد. 
اگر فرض کنیم که صف با آرایه پیاده‌سازی شده باشد، شبه‌کد تابع‌های Enqueue و Dequeue به این صورت خواهد بود:
 البته این کدها به ساده‌ترین صورت ممکن نوشته شده‌اند و حالت‌های خاص را در آن‌ها در نظر نگرفته‌ایم.
 (که در بالا توصیح داده شد)
 ایدهٔ صف حلقوی از آنجا شکل می‌گیرد که اگر ما n عنصر را وارد صف کنیم و سپس آن‌ها را یکی یکی حذف کنیم شرط پر بودن صف بر قرار می‌ماند و این در حالی است که که صف هنوز جای خالی دارد.
 در صف حلقوی (دوار) rear و front بعد از رسیدن به آخرین مقدار خود در صورت وجود شرایط لازم مجدداً مقادیر اولیه را می‌توانند بگیرند.
 صف حلقوی n عضوی را به صورت آرایهٔ 0 تا n-1 تعریف می کنیم.
 در این حالت وقتی rear=n-1 عنصر بعدی در [0]queue قرار می‌گیرد.در صف حلقوی front=rear به معنای خالی بودن صف است ولی شرط پر بودن صف بدین طریق تغییر می‌یابد:
 برای اضافه کردن به صف حلقوی rear یکی اضافه می‌شود و در صورتی‌که rear=n-1 باید صفر بشود.بدین منظورrear را با رابطه زیر در هر شرایطی مقدار دهی می‌کنند:
 این مسئله برای 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 خواهد بود.
 صف‌ها همچین می‌توانند به عنوان پیاده‌سازی شوند. دو نسخه از این پیاده‌سازی وجود دارد. اولی که در زیر توضیح داده شده‌است صف بلا درنگ نام دارد. این پیاده‌سازی این امکان را به صف‌ها می‌دهد که با پیچیدگی زمانی باشند، اما به لیست‌های کندرو با نیاز دارند. پیاده‌سازی دوم به لیست‌های کندرو و مموایز کردن نیاز ندارد و در انتهای این بخش توضیح داده شده‌است. سرشکن پیاده‌سازی دوم اگر ماندگاری نباشد است، اما پیچیدگی بدترین حالتش است و تعداد عناصر موجود در صف است.
 فرض کنیم برای لیستی مانند ، طول لیست، نشانگر لیست خالی و نشانگر لیستی باشد که آن و آن است.
 داده ساختار استفاده شده برای پیاده‌سازی صف‌هایمان از سه تشکیل شده‌است که جلوی صف، عقب صف در ترتیب برعکس است. ثایت نشانگر عنصر عقب بدون عنصر پشتی آن است، . صف تقریباً است و اضافه کردن عنصری مانند به تقریباً است. به این دلیل تقریبی می‌گوییم که در جفت نتیجه‌ها است.
 تابع کمکی برای ثابت صدا زده شود تا در فرض مساله صدق کند و خللی به وجود نیاید. بسته به اینکه لیست خالی باشد یا نه دو حالت باید در نظر گرفته شود که اگر خالی باشد: . تعریف رسمی این گونه است و که ای است که توسط عکس دنبال شده‌است.
 تابع که خروجی آن ای دنبال شده توسط برعکس است را صدا می‌کنیم. علاوه بر آن فرض می‌کنیم ، چون در حالتی است که این تابع صدا زده شده‌است. به‌طور جزئی‌تر، ما تابع کندرو را تعریف می‌کنیم که سه لیست ورودی می‌گیرد که است و خروجی آن الحاق ، برعکس و است. آنگاه . تعریف اسقرایی تابع چرخش این چنین است که و . پیچیدگی زمانی آن است اما چون از ارزیابی کندرو استفاده شده‌است تا زمانی که نتیجه محاسبات ضروری نباشد محاسبات به تعویق می‌افتد.
 بدون بخش کندروی محاسباتِ پیاده‌سازی، صف بلا درنگ پیاده‌سازی غیرماندگاری از صف در پیچیدگی زمانی سرشکن خواهد بود. در این حالت، لیست می‌تواند با عدد صحیح جایگزین شود و تابع reverse زمانی صدا زده می‌شود که صفر باشد.
 از صف‌ها در کاربری‌هایی که در آن‌ها، اشیاء، پدیده‌ها و روی‌دادها در انتظارند تا پردازش شوند، بیش‌تر استفاده می‌شود. مدیریت پیام‌ها در سیستم‌عاملی مثل ، مدیریت فهرست کارهایی که باید به ترتیب انجام شوند، پیاده‌سازی الگوریتم و... از جمله مواردی است که در آن‌ها از صف‌ها استفاده می‌شود.
 از ترکیب صف و پشته، داده‌ساختار جدیدی هم ایجاد شده‌است که هم امکان افزودن عنصرها را از دوسوی تودهٔ داده‌ها می‌دهد و هم امکان برداشتن آن‌ها را.
{"title": "صف (نوع داده انتزاعی)", "link": "https://fa.wikipedia.org//w/index.php?title=%D8%B5%D9%81_(%D9%86%D9%88%D8%B9_%D8%AF%D8%A7%D8%AF%D9%87_%D8%A7%D9%86%D8%AA%D8%B2%D8%A7%D8%B9%DB%8C)&oldid=28824483", "language": "fa"}