Queue

Queue یکی از interface های مهم در Collection Framework جاواست که برای تعریف مفهوم صفاز آن استفاده می‌شود، صف ساختمان داده ای است که بتوان اشیایی را با ترتیبی خاص به آن وارد کرد و با الگوریتم مشخصی از آن استخراج یا حذف نمود، الگوریتم‌ها و پیاده سازی های مختلفی از انواع صف وجود دارند که در مباحث بسیار پیشرفته ای همچون تئوری صف‌ها (Queueing Theory) مطرح می‌شوند، سه پیاده سازی ساده و مهم صف در جاوا عبارت‌اند از:

  • LinkedList: صفی با ساختار FIFO را پیاده سازی می‌کند که از لیست پیوندی استفاده می‌کند.
  • ArrayDeque: صفی با ساختار FIFO است که نحوه پیاده سازی آن با LinkedList متفاوت است.
  • PriorityQueue: صف اولویت را پیاده سازی می‌کند.

کلمه FIFO مخفف عبارت First In First Out است، صف FIFO صفی است که در آن عنصری که ابتدا وارد شود اولین عنصری خواهد بود که خارج می‌شود، مشابه صف نانوایی و بسیاری از صف‌های دیگر که در زندگی روزمره تجربه می‌کنیم. در کنار ساختمان داده‌های ساده و معمولی فوق کلاس‌های پیشرفته تری برای کار در مباحثی همچون شبکه، چند نخی (multithreading)، مسائل همزمانی (concurrency) مانند DelayQueue، SynchronosQueue، LinkedTransferQueue، ConcurrentLinkedDeque و … نیز وجود دارند. به صورت کلی یک صف صرف نظر از ساختمان داده داخلی آن و الگوریتم ورود یا خروج اعضا باید دارای ویژگی‌های کلی زیر باشد:

  • صف دارای بخشی به نام سر (head) باشد.
  • بتوان مواردی را به آن اضافه یا حذف کرد.
  • بتوان عنصر سر را بدون حذف استخراج کرد (برای تست)

Queue از طریق مسیر java.util.Queue قابل دسترسی است و متدهای زیر را تعریف می‌کند. کلاس‌هایی که از این کلاس ارث بری داشته باشند موظف هستند این متدها را پیاده سازی کنند: متدهای مربوط به مفهوم صف:

متد کاربرد
add(Object o) یک عنصر جدید به صف اضافه می‌کند. اگر قادر به این کار نباشد یک خطا پرتاب می‌کند.
element() عنصر سر (head) را بر می‌گرداند ولی آن را از صف حذف نمی‌کند.
offer(Object o) یک عنصر جدید به صف اضافه می‌کند اگر قادر به این کار نباشد تنها false بر می‌گرداند.
peek() عنصر سر را بر می‌گرداند، اگر صف خالی شده باشد null بر می‌گرداند.
poll() عنصر سر را بر می‌گرداند و آن را از صف حذف می‌کند، اگر صف خالی باشد null بر می‌گرداند.
remove() عنصر سر را حذف می‌کند.

متدهایی که از Collection به ارث رفته‌اند:

متد کاربرد
addAll(Collection c) تمام اعضای یک کالکشن دیگر را به صف اضافه می‌کند.
clear() تمام اعضای داخل صف را حذف می‌کند.
contains(Object o) وجود یک عنصر در صف را بررسی می‌کند.
containsAll(Collection c) اگر تمام اعضای کالکشن c در صف فعلی وجود داشته باشند true بر می‌گرداند.
equals(Ojbect o) صف فعلی را با صف دیگری مقایسه می‌کند.
hashCode() HashCode کل صف را محاسبه می‌کند.
isEmpty() بررسی می‌کند که صف خالی است یا خیر؟
iterator() یک iterator برای پیمایش صف بر می‌گرداند.
remove(Object o) یک عنصر را از صف حذف می‌کند.
removeAll(Collection c) تمام عناصر یک کالکشن دیگر را از صف فعلی حذف می‌کند.
retainAll(Collection c) اشتراک صففعلی را با کالکشن دیگر محاسبه می‌کند و سایر اعضا را حذف می‌کند.
size() تعداد عناصر داخل صف را بر می‌گرداند.
toArray() عناصر را در داخل یک آرایه در اختیار ما قرار می‌دهد.

در مثال زیر یک صف ساده ایجاد می‌کنیم، عناصری به آن اضافه می‌شوند و سپس تک تک عناصر را از صف خارج می‌کنیم.

import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo 
{
    public static void main(String[] args) 
    {
        Queue q = new LinkedList();

        q.add(1);
        q.add(8);
        q.add(3);

        System.out.println(q);

        System.out.println(q.poll());
        System.out.println(q);

        System.out.println(q.poll());
        System.out.println(q);

        System.out.println(q.poll());
        System.out.println(q);
    }
}
[1, 8, 3]
1
[8, 3]
8
[3]
3
[]

در کد بالا یک Queue ایجاد کردیم، چون Queue تنها یک interface است برای ساختشی جدید باید از یکی از زیر کلاس‌های پیاده سازی شده آن استفاده کنیم، در این مثال از LinkedList استفاده کردیم، با استفاده از متد ()add عناصر 1، 8 و 3 را به صف اضافه کرده و سپس کل صف را چاپ نمودیم. در ادامه با استفاده متد ()poll عنصر سر صف را حذف و چاپ کرده و پس از آن صف باقی مانده را نیز چاپ می‌کنیم، مشاهده می‌کنیم عناصر با همین ترتیبی که وارد صف شده‌اند از صف نیز خارج می‌شود زیرا LinkedList صفی با ساختار FIFO است.