آموزش کامل پیاده‌سازی صف (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) اورده شده است.

برای راحتی یک دسترسی سریع به پیاده‌سازی ها با زبان های مختلف قرار دادیم.

پیاده‌سازی صف (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();
    }
}

پیاده‌سازی صف (Queue) با کاتلین

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

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) با جاوا اسکریپت

زبان جاوااسکریپت یک زبان type-free است یعنی نوع متغیر هنگام مقداردهی متغیر مشخص میشه، در زیر یک صف (Queue) رو با جاوااسکریپت پیاده کرده ایم.

class MyQueue {
    constructor(elements = null) {
        this.list = new MyLinkedList();
        
        if (elements !== null) {
            for (let i = 0; i < elements.length; i++) {
                this.enqueue(elements[i]);
            }
        }
    }

    enqueue(e) {
        this.list.addLast(e);
    }

    dequeue() {
        if (this.isEmpty()) return null;
        return this.list.removeFirst();
    }

    peek() {
        if (this.isEmpty()) return null;
        return this.list.getFirst();
    }

    getSize() {
        return this.list.getSize();
    }

    isEmpty() {
        return this.list.isEmpty();
    }
}

پیاده‌سازی صف (Queue) با پایتون

پایتون یک زبان type-free است یعنی نوع متغیر هنگام مقداردهی متغیر مشخص میشه، در زیر یک صف (Queue) با پایتون پیاده کرده ایم.

import MyLinkedList

class MyQueue:

    def __init__(self, elements=None):
        self.list = MyLinkedList()
        
        if elements is not None:
            for i in range(len(elements)):
                self.enqueue(elements[i])

    def enqueue(self, e):
        self.list.add_last(e)

    def dequeue(self):
        if self.is_empty(): 
            return None
        return self.list.remove_first()

    def peek(self):
        if self.is_empty(): 
            return None
        return self.list.get_first()

    def get_size(self):
        return self.list._size

    def is_empty(self):
        return self.list.is_empty()

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

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

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

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

مثال زیر به چهار زبان جاوا، کاتلین، جاوااسکریپت و پایتون زده شده است.

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

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

            while (!directories.isEmpty()) {

                File directory = directories.dequeue();
                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: MyQueue<File> = MyQueue()

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

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

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

    return size
}

const fs = require('fs');
const path = require('path');

function getSize(file) {
    let directories = new MyQueue();
    let size = 0;

    // Get file/directory stats
    let stats = fs.statSync(file);

    if (stats.isDirectory()) {
        directories.enqueue(file);

        while (!directories.isEmpty()) {
            let directory = directories.dequeue();
            let files = null;

            try {
                // Read all contents inside the directory
                files = fs.readdirSync(directory);
            } catch (err) {
                // Handle restricted/permission-denied folders safely
                files = null;
            }

            for (let i = 0; files !== null && i < files.length; i++) {
                let fullPath = path.join(directory, files[i]);
                let fStats = fs.statSync(fullPath);

                if (fStats.isDirectory()) {
                    directories.enqueue(fullPath);
                } else {
                    size += fStats.size;
                }
            }
        }
    } else {
        size += stats.size;
    }

    return size;
}

import os

def getSize(file_path):
    directories = MyQueue()
    size = 0

    if os.path.isdir(file_path):
        directories.enqueue(file_path)

        while not directories.is_empty():
            directory = directories.dequeue()
            files = None

            try:
                # List items inside directory
                files = os.listdir(directory)
            } catch OSError:
                files = None

            for i in range(0, len(files) if files is not None else 0):
                full_path = os.path.join(directory, files[i])
                
                if os.path.isdir(full_path):
                    directories.enqueue(full_path)
                else:
                    size += os.path.getsize(full_path)
    else:
        size += os.path.getsize(file_path)

    return size

خلاصه

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