صف (Queue) در برنامه نویسی

بررسی صف (Queue)

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

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

صف (Queue) یک ساختار داده ی یک طرفه است، در صف چیزی به اسم وسط صف نداریم یعنی برخلاف آرایه های دینامیکی (list) که به عناصر با index به صورت تصادفی دسترسی داشتیم، در صف تنها به عنصر سر صف (یعنی اولین عنصری که وارد کردیم) دسترسی داریم و هنگامی که این عنصر حذف بشه، نوبت به عنصر وارد شده ی بعدی میرسه.

صف (Queue) رو میتونیم به دو روش پیاده سازی کنیم، اولین روش پیاده سازی صف با استفاده از آرایه است که در این حالت اندازه ی صف ثابته؛ دومین روش پیاده سازی صف، پیاده سازی آن با لیست پیوندی دو طرفه (LinkedList) است.

میتونیم با رابطه ی aggregation یا inheritance صف رو پیاده سازی کنیم.

در این مطلب با استفاده از لیست پیوندی و رابطه ی aggregation به پیاده سازی صف (Queue) می پردازیم.

افزودن عنصر به صف (Queue)

به طور عمومی با تابع enqueue(e: E) یک عنصر رو به صف (Queue) اضافه میکنن اما در زبان های مختلف ممکنه اسم این تابع فرق کنه، مثلا در جاوا از تابع offer(e: E) استفاده میشه.

پیچیدگی زمان هنگام افزودن یک عنصر به صف (Queue) برابر با O(1) است.

function enqueue(e: E){
  linkedList.addLast(e);
}
        

حذف یک عنصر از صف (Queue)

به طور عمومی از تابع dequeue(): E برای حذف یک عنصر از صف استفاده میشه اما این تابع ممکنه در زبان های مختلف اسم متفاوتی داشته باشه، مثلا در زبان جاوا از poll(): E استفاده میشه.

اولین عنصری که به صف اضافه میکنیم اولین عنصری خواهد بود که حذف میکنیم و تا زمانی که عنصر اول حذف نشه به عنصر بعد دسترسی نداریم؛‍ پیچیدگی زمان هنگام حذف یک عنصر از صف O(1) است.

function dequeue(): E{
   return linkedList.removeFirst();
}
        

صدا زدن عنصر از صف (Queue)

به طور عمومی با تابعی به نام peek(): E میتونیم اولین عنصر در صف رو صدا بزنیم و تا زمانی که این عنصر حذف نشده باشه به عنصر بعد دسترسی نداریم؛ پیچیدگی زمان هنگام صدا زدن یک عنصر از صف O(1) است.

function peek(): E{
  return linkedList.getFirst();
}
        

پیاده سازی صف (Queue) در زبان های برنامه نویسی

میخوایم با استفاده از رابطه ی aggregation یک صف رو با لیست پیوندی که در مطلب قبل پیاده کردیم، پیاده سازی کنیم.

در زیر نمودار uml پیاده سازی صف (Queue) اورده شده است.

public class MyQueue<E> {

    private final MyLinkedList<E> list = new MyLinkedList<>();

    public MyQueue(E[] elements){
        for (int i=0; i<elements.length; i++)
            enqueue(elements[i]);
    }
    
    public MyQueue(){
        
    }

    public void enqueue(E e){
        list.addLast(e);
    }

    public E dequeue(){
       
       if(isEmpty()) return null

       return list.removeFirst();
    }
    
    public E peek(){
        if(isEmpty()) return null

        return list.getFirst();
    }
    
    public int getSize(){
        return list.getSize();
    }
    
    public boolean isEmpty(){
        return list.isEmpty();
    }
}
        

class MyQueue<E>() {
    private val list: MyLinkedList<E> = MyLinkedList()
    
    val size: Int
        get() = list.size

    val empty: Boolean
        get() = list.empty

    constructor(elements: Array<E>): this(){
        for (i in elements.indices)
            enqueue(elements[i])
    }

    fun enqueue(e: E) {
        list.addLast(e)
    }

    fun dequeue(): E? {

       if(empty) return null

       return list.removeFirst()
    }

    fun peek(): E? {
        if(empty) return null
        return list.getFirst()
    }
}
        

استفاده از صف (Queue) در زبان های برنامه نویسی

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

میخوایم با استفاده از صف (Queue) یک برنامه بنویسیم که اندازه ی کل یک پوشه (پوشه با فایل و پوشه های داخلش) رو حساب کرده و نشون بده.

این برنامه رو با استفاده از بازگشتی نوشتیم و حالا میخوایم با استفاده از صف (Queue) بدون روش بازگشتی انجام بدیم.

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;
    }
        

fun getSize(file: File): Long {
    val directories: Queue<File> = LinkedList()

    var size: Long = 0
    if (file.isDirectory()) {
        
        directories.offer(file)

        while (!directories.isEmpty()) {
            val directory = directories.remove()
            val files = directory.listFiles()

            var i = 0
            while (files != null && i < files.size) {
                val f = files[i]
                if (f.isDirectory()) directories.offer(f)
                else size += f.length()
                i++
            }
        }
    } else {
        size += file.length()
    }

    return size
}
        

خلاصه

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