بسم الله الرحمن الرحيم

هذا الدرس الأول من الفصل السادس لكتاب الخوارزميات المعهود، ودرس اليوم عن نوع معطيات مجرد ADT اسمه الصف Queue، ولا تقل الطابور فهي كلمة تركية دخيلة وليست بعربية، وكان لا بد من استفتاح الفصل السادس به حتى يَسهُل عليك.
إن كنت لا تعرف ما معنى نوع معطيات مجرد فعليك أن تراجع الفصول الأولى كلها، ولا سيما هذا الدرس الذي ورد فيه ذكره:

ما الصف Queue؟

من اسمه تفهمه، الصف بنية معطيات خطية linear تضيف العناصر إليها وتزيلها بخاصية: من يدخل أولًا يخرج أولًا First In First Out، اختصارًا FIFO. مثل اصطفاف الناس أمام الصراف في الدول الأجنبية، تراهم يصطفون في صف، وأول من يأتي إلى الصف هو أول من يُخدم ثم يمضي في سبيله. فالعنصر الذي تضيفه أولًا إلى بنية المعطيات هذه (التي اسمها الصف) هو أول عنصر يخرج منه.

يشبه الكِدسة، وقد ذكرتُ في درس الكِدسة Stack أن للكِدسة خاصية (من يدخل أخيرًا يخرج أولًا LIFO) أما الصف فعلى النقيض منه، فإن أول من يدخل هو أول من يخرج، سمها خاصية (من يدخل أولًا يخرج أولًا FIFO). وللصف استعمالات منها:

١. في توقيت المهمات Task Scheduling: فالمهات لا بد من تنفيذها بالترتيب التي أتت عليه،

٢. وفي صِوان المِدخلة keyboard buffer (المِدخلة ترجمة للوحة المفاتيح keyboard): فإن الضغطات تُخزن في صف قبل أن تُعالج. إن كنت لا تعرف ما معنى الصِوان راجع هذا المقال:

لعلك لاحظت أن استعمال الصف يكون في حال يقتضي أن تُعالج الطلبات في ترتيب مجيئها، فالصف مستعمل في المعالج CPU وفي القرص الصلب حتى يعالج الطلبات بالترتيب، أي في أنظمة التشغيل والشبكات والخوارزميات.

ومثلًا أيها المبرمج عندك برمجية تنزل المرئيات VIdeos ثم ترسلها إلى منصة التلجرام، لكن حاسوبك أو خادوك ضعيف والشبكة بطيئة، فهل إذا أتى عشرة أشخاص أفانت محمل لهم كلها مرة واحدة وترسلها كلها مرة واحدة؟

الصواب أن تضع الطلبات في صف، ثم تنفذها بالترتيب، الأول بالأول كيلا تثقل على حاسوبك!

للصف وظيفتين لا بد له منها:

١. الأولى (الإضافة Enqueue): وتضيف عنصرًا إلى الصف، إلى آخره rear.

٢. الثانية (الإزالة Dequeue): وتحذف أول عنصر من الصف، تحذفه من أوله front.

أنواع الصف

الصف المذكور في كتابنا، كتاب (استيعاب الخوارزميات Grokking Algorithms) هو الصف العادي simple queue، وما تقدم شرحه كان عنه، وهو نوع واحد من أربعة أنواع، ولم يزد عليه صاحب الكتاب، لكني أزيدك بلا تفصيل مخل ولا تطويل ممل.

النوع الثاني الصف الدائري Circular Queue: آخر عنصر في هذا الصف يشير إلى أول عنصر، فيتكون رابط يربط بين أوله وآخره كأنه حلقة، وهذا النوع جاء مُعالجًا علةً كانت في الصف العادي، ففي الصف العادي بعد إضافة وإزالة متكررة تبقى بعض الخانات خالية، فالعناصر لا تنتقل إلى البداية وتبقى هذه الخانات خالية، وإن برمجته بيدك ستواجه العلة فلا ينبئك مثل خبير.

النوع الثالث صف حسب الأولويات Priority Queue: كل عنصر في هذا الصف مقترن بأولوية، مثلًا هذه مهمة عاجلة وهذه عاجلة وهامة وهذه هامة وغير عاجلة وعلى هذا فسِر (سر من السير). والعناصر صاحبة نفس الأولوية تنفذ بالترتيب الذي دخلت فيه إلى الصف.

النوع الرابع الصف ذو النهايتين Double Ended Queue، اختصارًا Deque: في هذا النوع الإضافة والإزالة تكون من الطرفين، من مقدمة الصف front ومن مؤخرته rear، وما دام هذا حاله فهو لا يتبع مبدأ (من يدخل أولًا يخرج أولًا FIFO).

لعلك تقول تلك الأنواع ليست إلا بعض تعديلات وإضافات على الصف العادي، فما بك يا مبعسس تصرعنا بهذا التقسيم، أنا لن أحفظها وقد فهمت فمحوى الصف وبرمجته عليّ بإذن الله سهلة يسيرة. وأنا أقول لك لا تحفظها إن شئت، والحمد لله قد فهمتَها.

هيا ارتد رداء المبرمج ولنبرمجه!

برمجة الصف في بايثون

للمبرمج الكسول قد ضمنت لغة بايثون الصف جاهزًا فلا تخف فلن تبرمجه، ومراعاةً لك سأبدأ بالمكتبة ثم نبرمجه في النهاية إن شاء الله. المكتبة اسمها الصف queue، وفيها أصناف class مهمة لنا هي:

الصنف Queue: الصف بخاصية من يدخل أولًا يخرج أولًا FIFO.

الصنف LifoQueue: الصف لكن بخاصية من يدخل أخيرًا يخرج أولًا LIFO، وهو الكِدسة Stack.

الصنف PriorityQueue: وهو الصف من النوع الثالث، صف حسب الأولويات.

الصنف deque: وهو الصف من النوع الرابع، ذو النهايتين.

غرضنا اليوم الصنف الأول Queue. لتهيئة نسخة من الصنف نستدعه من المكتبة ثم نسنده إلى متغيرٍ:

from queue import Queue
My_Queue = Queue()

قلنا لبايثون هاتي الصنف Queue من المكتبة queue ثم استنسخي هذا الصنف بإسناده إلى متغير اسمه My_Queue. الآن المتغير My_Queue صار صفًّا وعنده وظائف يؤديها وسنستعملها.

وظائف Methods هذا الصنف عدة:

وظيفة الإضافة put(item): تضيف عنصرًا إلى الصف.

وظيفة الإزالة ()get: تُرجع العنصر، أي تطبعه ثم تحذفه من الصف.

هاتان ما نحتاج أما باقي الوظائف فلا، باقي الوظائف: وظيفة ترجع لك حجم الصف ()qsize، ووظيفة تخبرك هل امتلأ الصف أم لا ()full، ووظيفة تخبرك إن كان فارغًا ()empty، وأخرى في تعدد المهمات ليس هذا موضع ذكرها.

سنضيف الآن ثلاثة عناصر إلى الصف، ثم نطبع حجم الصف ونحذف العنصر الأول والثاني الذي يليه:

from queue import Queue
My_Queue = Queue()
My_Queue.put(1) # Add 1 to queue
My_Queue.put(2)
My_Queue.put(3)
print(My_Queue.qsize()) # Prints 3
print(My_Queue.get()) # Prints 1
print(My_Queue.get()) # Prints 2

وقد فرغنا من استعمال الصف جاهزًا فسنبرمج الآن نسخة منه ونستعملها!

عليك أن تكون قد درست البرمجة الشيئية OOP في بايثون حتى تفهم أيها القارئ الكريم.

سننشئ صِنفًا class اسمه SimpleQueue، ثم نهيّئ الصنف هذا بلائحة فارغة باستعمال __init__

ثم سننشئ وظيفتين، الأولى تضيف عنصرًا enqueue وأخرى تحذفه dequeue.

class SimpleQueue:
    def __init__(self):
        self.items = []  # Initialize an empty list to store queue items

أنشأنا الصف وهيّأنا الصنف بلائحة فارغة اسمها العناصر items، فيها نخزن عناصر الصف.

الآن سنكتب وظيفة تأخذ العنصر وتضيفه إلى هذه اللائحة، وهذا سهل يسير:

def enqueue(self, item):
        """Add an item to the end of the queue."""
        self.items.append(item)

الوظيفة اسمها enqueue تستقبل عنصرًا، هذا العنصر تأخذه وتُلحِقه باللائحة appending.
وقبل كتابة الوظيفة الثانية سنكتب وظيفة تخبرنا هل الصف فارغ أم لا. وهذا سهل، سنرى هل اللائحة السابقة فارغة من العناصر أم لا باستعمال الوظيفة len التي ترجع عدد العناصر في اللائحة، إن كان عدد العناصر يساوي الصفر فهي فارغة وإلا ففيها عنصر أو عناصر.

    def is_empty(self):
        """Check if the queue is empty."""
        return len(self.items) == 0

هنا شرط، وضعنا علامة المساواة، إن كان عدد العناصر يساوي الصفر فإن النتيجة المُرجعة هي الصواب True، وإلا أرجع الخطأ False.

وهذه وظيفة تحذف عنصرًا من الصف بعد أن تستعمل الوظيفة التي تخبرنا أفارغ الصف أم لا:

    def dequeue(self):
        """Remove and return the item from the front of the queue."""
        if self.is_empty():
            raise IndexError("Dequeue from an empty queue")
        return self.items.pop(0)  # Remove the first item

الوظيفة تنظر أفارغ الصف أم لا؟
ولِمَ تفعل ذلك يا مبعسس؟

لأن الصف إذا كان فارغًا فليس فيه شيء للحذف، فلا بد من النظر فيه قبل محاولة حذف شيء، ثم استعملنا الكلمة raise وقلنا ارمِ خطأ إن كان الصف فارغًا. سأضيف بعض الوظائف وأترك لك استكشافها فهي سهلة لمن قد درس بايثون:

class SimpleQueue:
    def __init__(self):
        self.items = []  # Initialize an empty list to store queue items

    def is_empty(self):
        """Check if the queue is empty."""
        return len(self.items) == 0

    def enqueue(self, item):
        """Add an item to the end of the queue."""
        self.items.append(item)

    def dequeue(self):
        """Remove and return the item from the front of the queue."""
        if self.is_empty():
            raise IndexError("Dequeue from an empty queue")
        return self.items.pop(0)  # Remove the first item

    def size(self):
        """Return the number of items in the queue."""
        return len(self.items)

    def peek(self):
        """Return the item at the front of the queue without removing it."""
        if self.is_empty():
            raise IndexError("Peek from an empty queue")
        return self.items[0]

# Example usage
if __name__ == "__main__":
    queue = SimpleQueue()
    
    # Enqueue items
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    
    print("Queue size:", queue.size())  # Output: Queue size: 3
    print("Front item:", queue.peek())   # Output: Front item: 1
    
    # Dequeue items
    print("Dequeued item:", queue.dequeue())  # Output: Dequeued item: 1
    print("Queue size after dequeue:", queue.size())  # Output: Queue size after dequeue: 2
    
    # Check if the queue is empty
    print("Is the queue empty?", queue.is_empty())  # Output: Is the queue empty? False
    
    # Dequeue remaining items
    print("Dequeued item:", queue.dequeue())  # Output: Dequeued item: 2
    print("Dequeued item:", queue.dequeue())  # Output: Dequeued item: 3
    
    # Check if the queue is empty
    print("Is the queue empty?", queue.is_empty())  # Output: Is the queue empty? True

الخاتمة

ها قد وصلنا إلى نهاية المقال، وها أنا أخط بقلمي الخطوط الأخيرة لهذا المقال الشائق، وأرجو إني قد وفِّقت في الشرح.

وفي نهاية الأمر لا يسعني سوى أن أشكرك على حسن قراءتك لهذا المقال، وأني لبشر أصيب وأخطِئ، فإن وفِّقت في طرح الموضوع فمن اللّٰه عز وجل وإن أخفقت فمن نفسي والشيطان.

أرجو منك تقييم كفاءة المعلومات من أجل تزويدي بالملاحظات والنقد البناء في خانة التعليقات أو عبر حساب الموقع، والسلام عليكم ورحمة اللّٰه تعالى وبركاته.