موضوع مقاله: صف (نوع داده انتزاعی) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # صف (نوع داده انتزاعی) | مقدمه: صف لیستی است که عمل افزودن داده‌ها درون آن از انتهای لیست و عمل حذف داده‌ها از ابتدای لیست انجام می‌شودمثل یک صف نانوایی داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. | ## بخش 1: صف (نوع داده انتزاعی) | بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود، این به این معنی است که شیوهٔ عملکرد صف براساس سیاست FIFO است. صف در طراحی و پیاده‌سازی سیستم‌های نرم‌افزاری و سخت‌افزاری بسیار استفاده می‌شود. در این حالت ما تنها می‌توانیم بر روی دستهٔ کاغذها، کاغذی بگذاریم و از طرفی تنها می‌توانیم از روی دستهٔ کاغذها، کاغذی برداریم (یعنی ورود و خروج از یک سمت انجام می‌گیرد). روشن است که در این حالت آخرین کاغذی که روی دستهٔ کاغذها قرار داده شده، نخستین کاغذی است که برداشته می‌شود و اولین کاغذی که روی میز گذاشته شده، آخر از همه برداشته خواهد شد. در این حالت، برخلاف پشته، آدم‌ها به ته صف اضافه می‌شوند و از سر صف خارج می‌شوند (یعنی ورود و خروج از دو سمت متمایز انجام می‌گیرد). به این ترتیب روشن است که آخرین کسی که وارد صف شده، آخرین کسی است که نان دریافت می‌کند و اولین کسی که وارد صف شده، نخستین فردی است که نان می‌گیرد. دامنه تغییرات front و rear از 0 تا n است و مقادیر اولیه آن‌ها 0 قرار داده می‌شود.شرط پر بودن صف: rear=n پیاده‌سازی مشابه پشته‌ها، صف‌ها نیز می‌توانند با انواع ساختار داده هایی مثل آرایه یا لیست پیوندی پیاده‌سازی شوند. انواع صف صف خطی (که در بالا توصیح داده شد) صف حلقوی ایدهٔ صف حلقوی از آنجا شکل می‌گیرد که اگر ما n عنصر را وارد صف کنیم و سپس آن‌ها را یکی یکی حذف کنیم شرط پر بودن صف بر قرار می‌ماند و این در حالی است که که صف هنوز جای خالی دارد. در صف حلقوی (دوار) rear و front بعد از رسیدن به آخرین مقدار خود در صورت وجود شرایط لازم مجدداً مقادیر اولیه را می‌توانند بگیرند. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. | ## بخش 2: صف (نوع داده انتزاعی) | به عنوان مثال فرض کنید پردازش‌های زیر در انتظار اختصاص CPU به خود هستند: 6 5 4 3 2 1 شماره پردازش 4 5 3 1 2 4 اولویت صف انتظار CPU یک صف اولویت دار است. تذکر: روش‌های زمان بندی CPU جهت انجام پردازش‌های مختلف یکی از بحث‌های جذاب و در عین حال مهم مبحث سیستم‌عامل است. در مورد افزودن یک عنصر، از (O(n است که n نشان‌دهندهٔ تعداد عنصرهای موجود در صف است. علت این امر آن است که با ورود هر عنصر به ته صف، همهٔ عنصرهای دیگر باید به اندازهٔ یکی جابه‌جا شوند تا جا برای این عنصر تازه باز شود. می‌بینیم که در پیاده‌سازی آرایه‌ای، پیچیدگی زمانی افزودن و برداشتن عنصرها از صف و به صف، با هم متفاوت است. با این وجود اگر صف را با لیست‌های پیوندی پیاده‌سازی کنیم، به علت ساختار خاص این لیست‌ها، هردوی این اعمال برای هم صف (و به همین شکل برای پشته)، دارای پیچیدگی زمانی از (O(1 خواهد بود. پیاده‌سازی تابعی محض صف‌ها همچین می‌توانند به عنوان داده ساختار تابعی محض پیاده‌سازی شوند. این پیاده‌سازی این امکان را به صف‌ها می‌دهد که با پیچیدگی زمانی ماندگار باشند، اما به لیست‌های کندرو با مموایز کردن نیاز دارند. پیاده‌سازی دوم به لیست‌های کندرو و مموایز کردن نیاز ندارد و در انتهای این بخش توضیح داده شده‌است. پیچیدگی زمانی سرشکن پیاده‌سازی دوم اگر ماندگاری نباشد است، اما پیچیدگی بدترین حالتش است و تعداد عناصر موجود در صف است. | ## بخش 3: صف (نوع داده انتزاعی) | فرض کنیم برای لیستی مانند ، طول لیست، نشانگر لیست خالی و نشانگر لیستی باشد که آن و آن است. لیست بلا درنگ داده ساختار استفاده شده برای پیاده‌سازی صف‌هایمان از سه لیست پیوندی تشکیل شده‌است که جلوی صف، عقب صف در ترتیب برعکس است. بسته به اینکه لیست خالی باشد یا نه دو حالت باید در نظر گرفته شود که اگر خالی باشد: . به‌طور جزئی‌تر، ما تابع کندرو را تعریف می‌کنیم که سه لیست ورودی می‌گیرد که است و خروجی آن الحاق ، برعکس و است. پیچیدگی زمانی آن است اما چون از ارزیابی کندرو استفاده شده‌است تا زمانی که نتیجه محاسبات ضروری نباشد محاسبات به تعویق می‌افتد. صف سرشکن‌شده بدون بخش کندروی محاسباتِ پیاده‌سازی، صف بلا درنگ پیاده‌سازی غیر‌ماندگاری از صف در پیچیدگی زمانی سرشکن خواهد بود. در این حالت، لیست می‌تواند با عدد صحیح جایگزین شود و تابع reverse زمانی صدا زده می‌شود که صفر باشد. کاربرد صف‌ها از صف‌ها در کاربری‌هایی که در آن‌ها، اشیاء، پدیده‌ها و روی‌دادها در انتظارند تا پردازش شوند، بیش‌تر استفاده می‌شود. | ## جمع‌بندی | توسعه از ترکیب صف و پشته، داده‌ساختار جدیدیDeque هم ایجاد شده‌است که هم امکان افزودن عنصرها را از دوسوی تودهٔ داده‌ها می‌دهد و هم امکان برداشتن آن‌ها را.