کالکشن ها در جاوا: معرفی و استفاده از صف (Queue) + مثال

معرفی صف (Queue)

وقتی میرید نونوایی به اولین چیزی که برخورد میکنید صف نونواییه، بهت میگن اقا دیر اومدی باید وایسی ته صف! اولین کسی که نوبتشه همونیه زود تر از بقیه اومده و به همین ترتیب تا نوبت به اخرین نفری برسه که تو صف نونه

صف (Queue) یکی از پیاده سازی های ساختار داده است؛ در صف (Queue) اولین عنصری که اضافه میشه، اولین عنصریه که میتونیم صدا بزنیم یا حذفش کنیم مثل همین قضیه ی صف نونوایی؛ صف (Queue) معروفه به first-in-first-out و یک ساختار داده ی یک طرفه است، در صف چیزی به اسم وسط صف نداریم یعنی برخلاف ArrayList که به عناصر با index به صورت تصادفی دسترسی داشتیم، در صف تنها به عنصر سر صف (یعنی اولین عنصری که وارد کردیم) دسترسی داریم و هنگامی که این عنصر حذف بشه، نوبت به عنصر وارد شده ی بعدی میرسه.

استفاده از صف (Queue)

کلاس های LinkedList و ArrayDeque در جاوا صف (Queue) رو پیاده‌سازی کردن و از این دو کلاس میتونیم یک صف (Queue) ایجاد کنیم.

اینترفیس Queue از اینترفیس Collection ارث‌بری میکنه.

در زیر نمودار UML متد های تعریف شده در صف با کاربرد هاشون آورده شده است.

در مثال زیر عناصر رو به صف اضافه می کنیم و سپس دونه دونه حذف کرده و چاپشون می کنیم.

Queue<String> queue = new LinkedList<>();

queue.offer("Tehran");
queue.offer("Arak");
queue.offer("Isfahan");
queue.offer("Tabriz");
queue.offer("Mashhad");


System.out.println("Displaying queue: ");

while(!queue.isEmpty())
   System.out.print(queue.remove() + " ");

System.out.println();
        

در مثال زیر میخوایم با استفاده از صف (Queue) اندازه ی یک پوشه رو بدست بیاریم؛ این مثال در موضوع بازگشتی (Recursion) با روش بازگشتی گفته شده و در اینجا با صف میخوایم انجامش بدیم.

public static void main(String[] args){
  
  System.out.println("Insert directory path: ");

  Scanner input = new Scanner(System.in);

  String path = input.nextLine();

  File f = new File(path);

  System.out.println("The size of directory is " + getSize(f)/(100_000) + "MB");

}

static long getSize(File file){
        Queue<File> directories = new LinkedList<>();

        long size =0;
        if (file.isDirectory()) {
            directories.offer(file);

            while (!directories.isEmpty()) {

                File directory = directories.remove();
                File[] files = directory.listFiles();

                for (int i = 0; files != null && i < files.length; i++) {
                    File f = files[i];
                    if (f.isDirectory())
                        directories.offer(f);
                    else size += f.length();
                }
            }
        }else {
            size += file.length();
        }

        return size;
    }
        

بررسی پیچیدگی زمان صف (Queue)

در جدول زیر پیچیدگی زمان (Time Complexity) متد های Queue آورده شده است.

خلاصه

• صف (Queue) یک ساختار داده first-in-first-out است.
• پیچیدگی زمان حذف کردن، صدا زدن عنصر از صف یا افزودن عنصر به صف O(1) است.
• یکی از پیاده سازی های صف (Queue) در جاوا، کلاس LinkedList است.