صف Queue

صف یا Queue چیست؟

صف (Queue) عنوان ساختمان داده‌ای است که مجموعه‌ای از المان‌ها (عناصر) را بر اساس اصل FIFO (خروج به ترتیب ورود) در خود نگه‌داری می‌کند.

برای Queue دو عمل اصلی تعریف می‌شود. عمل Enqueue که عنصر جدیدی را به انتهای آن (که rear نامیده می‌شود) اضافه می‌کند و عمل Dequeue که عنصری را از ابتدای آن (که front نامیده می‌شود) حذف می‌کند. به این ترتیب اولین عنصری که به یک Queue افزوده می‌شود اولین عنصری خواهد بود که از آن حذف خواهد شد. از این رو، صف‌ها را نوعی ساختمان داده‌ی FIFO به شمار می‌آورند. در برخی از پیاده‌سازی‌ها، عملی به نام Front یا Peek نیز تعریف می‌شود که مقدار المان اول را بدون حذف آن برمی‌گرداند.

هنگامی که می‌خواهیم داده یا المانی را برای مدتی نگه‌داری و در آینده مورد پردازش قرار دهیم به کاربردن صف از جمله بهترین راهکارهایی به شمار می‌رود که برای این منظور استفاده می‌شود. در چنین حالتی صف، نقش یک بافر را ایفا می‌کند. یکی از مهم‌ترین کاربردهای این ساختمان داده در الگوریتم‌های زمان بندی می‌باشد.

پیاده‌سازی صف

هرچند از نظر تئوری می‌توان صف‌ها را به صورت نامتناهی و بدون محدودیت در ظرفیت تجسم نمود اما در صورتی که صف را توسط آرایه‌ای با طول ثابت پیاده سازی کنیم ظرفیت آن ثابت خواهد بود. با درنظر گرفتن این آرایه به صورت یک دایره می‌توان یک صف حلقوی ایجاد نمود. در این نوع Queue لزوما انتهای آرایه، انتهای صف نیست بلکه می‌توان از فضای خالی به وجود آمده در ابتدای آرایه (به دلیل اعمال Dequeue)، برای افزودن عناصر جدید استفاده نمود. در صورتی که Queue پر باشد و بخواهیم عنصر جدیدی به آن اضافه کنیم حالتی به نام سرریز (Overflow) رخ می‌دهد. به طور مشابه در صورتی که بخواهیم روی یک Queue خالی، عمل Dequeue را انجام دهیم حالت زیرریز (Underflow) رخ خواهد داد.

استفاده از لیست‌های پیوندی (Linked List) برای پیاده‌سازی صف می‌تواند محدودیت تعداد عناصر قابل نگه‌داری در این ساختمان داده را از میان بردارد. به عبارت بهتر در این نوع پیاده سازی برخلاف حالتی که از آرایه برای انجام این کار استفاده می‌شود نیازی به مشخص نمودن ظرفیت صف هنگام ایجاد آن وجود ندارد.

اعمال حذف و اضافه روی یک صف
اعمال حذف و اضافه روی یک Queue

پیوندهای پیشنهادی تک دیک

لینک واژه در ویکیپدیا

واژه‌های مرتبط

بازیابی داده Data Recovery بازیابی داده یا Data Recovery چیست؟ بازیابی داده (Data Recovery) به فرایندی اطلاق می‌شود که طی آن داده‌های از دست رفته، غیرقابل دسترسی، آسیب دیده یا ...
سیستم مدیریت پایگاه داده Database Management Syste... سیستم مدیریت پایگاه داده یا Database Management System-DBMS چیست؟ سیستم مدیریت پایگاه داده یا DBMS، یک نرم افزار رایانه‌ای است که با پایگاه داده، کار...
نوع داده بولی Boolean Data Type نوع داده بولی یا Boolean Data Type چیست؟ بولی (بولین یا Boolean) در علوم رایانه نوع داده‌ای است که تنها می‌تواند یکی از دو مقدار ممکن را داشته باشد؛ ...
لیست پیوندی Linked List لیست پیوندی یا Linked List چیست؟ لیست پیوندی (Linked List) مجموعه‌ای از عناصر داده‌ای است که در آن هر عنصر به عنصر بعدی خود اشاره می‌کند. این عناصر ک...
پایگاه داده رابطه ای Relational Database... پایگاه داده رابطه ای یا Relational Database چیست؟ پایگاه داده رابطه ای (Relational Database) نوعی پایگاه داده براساس مدل رابطه ای (Relational Model) ...
پایگاه داده Database پایگاه داده یا Database چیست؟ پایگاه داده (Database یا به اختصار DB)، به مجموعه‌ای سازمان‌یافته از داده‌ها گفته می‌شود که عناصری نظیر شِماها (Schema)...

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *