الدرس الثاني (٢)
انظر إلى الشكل: الطابور مثل طابور السيارات عند إشارة المرور؛ السيارة التي تدخل أولاً هي التي تخرج أولاً وفق قاعدة First In First Out وتُكتب اختصاراً FIFO. لاحظ الفرق بينه وبين المكدس؛ في المكدس تتم الإضافة والحذف من نفس الجانب، بينما في الطابور تتم الإضافة من جانب والحذف من الجانب الآخر. لتتبع هذا الهيكل، نستخدم عمليتين رئيسيتين: Enqueue لإضافة عنصر في آخر الطابور، وDequeue لحذف عنصر من مقدمة الطابور. ولإدارة ذلك، يعتمد الطابور على مؤشرين: المؤشر الأمامي Front Pointer الذي يشير إلى العنصر الأول، والمؤشر الخلفي Rear Pointer الذي يشير إلى العنصر الأخير. انظر إلى مصفوفة الأرقام في الأسفل، المؤشر الأمامي عند الفهرس 0 ويشير للقيمة 9، بينما المؤشر الخلفي عند الفهرس 10 ويشير للقيمة 31.
يقوم الدرس على هيكل بيانات الطابور (Queue) الذي يعتمد قاعدة المضاف أولاً يخرج أولاً (First In First Out). تتم إضافة العناصر من نهاية الطابور باستخدام عملية Enqueue وحذفها من المقدمة باستخدام Dequeue، بخلاف المكدس الذي تتم الإضافة والحذف فيه من نفس الجانب. انظر إلى طابور السيارات عند إشارة المرور: السيارة التي دخلت أولاً تخرج أولاً. في لغة بايثون، يمكنك تطبيق الطابور باستخدام القوائم عبر الأمر listName.append(x) للإضافة وlistName.pop(0) للحذف، أو باستخدام الوحدة النمطية للطابور (Queue Module) عبر الدوال put وget وqsize. من التطبيقات العملية الشهيرة طابور الطابعة الذي يعالج مهام الطباعة بالترتيب الزمني لإرسالها.
الفكرة الأساسية
هيكل بيانات الطابور (Queue) يعتمد قاعدة المضاف أولاً يخرج أولاً (First In First Out) أو اختصاراً (FIFO Rule). العنصر الأول المضاف إلى القائمة يُعالج أولاً، والعنصر الأحدث يُعالَج آخراً. انظر إلى طابور السيارات عند إشارة المرور: السيارة التي دخلت إلى الطابور أولاً هي التي تخرج أولاً.
الشرح
الفرق بين المكدس والطابور هو أن المكدس تتم فيه الإضافة وحذف العنصر من نفس الجانب، بينما في الطابور تتم الإضافة من جانب ويتم الحذف من الجانب الآخر. يحتوي الطابور على مؤشرين رئيسيين: المؤشر الأمامي (Front Pointer) ويشير إلى العنصر الأول في الطابور، والمؤشر الأخير (Rear Pointer) ويشير إلى العنصر الأخير. هناك عمليتان رئيسيتان للطابور:
- إضافة عنصر للطابور (Enqueue): تُستخدم لإضافة عنصر في آخر الطابور. تتم زيادة قيمة المؤشر الخلفي بقيمة واحد بحيث يشير إلى موضع العنصر الجديد الذي سيُضاف.
- حذف عنصر من الطابور (Dequeue): تُستخدم لحذف عنصر من مقدمة الطابور. يُحذف العنصر المشار إليه بالمؤشر الأمامي، وتتم زيادة قيمة المؤشر الأمامي بقيمة واحد بحيث يشير إلى العنصر التالي الجديد في الطابور. قبل أي إجراء حذف، عليك التحقق مما إذا كانت هناك مساحة فارغة أو توافر عنصر واحد على الأقل للتصدير، وممنوع إضافة عنصر أو حذفه من وسط الطابور. في لغة البايثون، يمكن تمثيل الطابور بطرائق متنوعة منها القوائم (Lists). لاستخدام الطابور بالقوائم، تستخدم الطريقة listName.append(x) لإضافة العنصر x إلى القائمة، وتستخدم الطريقة listName.pop(0) لحذف العنصر الأول من القائمة. أما استخدام الوحدة النمطية للطابور (Queue Module) فيتيح لك دوال جاهزة مثل queueName = queue.Queue() لإنشاء طابور جديد، وqueueName.put(x) لإضافة عنصر، وqueueName.get() لعرض وحذف العنصر الأول من الطابور والعنصر الأخير من المكدس، وqueueName.qsize() لمعرفة حجم الطابور، وqueueName.full() وqueueName.empty() للتحقق من امتلاء أو فراغ الطابور.
مثال محلول خطوة بخطوة
أنشئ طابوراً لتخزين مجموعة من الأرقام [1, 21, 32, 45].
- عرّف المتغير في البايثون: myQueue = [1, 21, 32, 45]. المؤشر الأمامي يشير إلى العنصر الأول وقيمته 1 عند الفهرس 0، والمؤشر الخلفي يشير إلى القيمة 45 عند الفهرس 3.
- استخدم عملية حذف عنصر من الطابور مرتين لحذف العنصرين الأولين. بتطبيق myQueue.pop(0) مرتين، يُحذف الرقم 1 أولاً ثم الرقم 21 ثانياً، ليصبح الطابور [32, 45].
- استخدم عملية إضافة عنصر إلى الطابور لإضافة عنصر جديد إليه. بتطبيق myQueue.append(78)، يُضاف الرقم 78 إلى نهاية الطابور ليصبح [32, 45, 78].
أخطاء شائعة
- محاولة إضافة عنصر أو حذفه من وسط الطابور، وهذا غير مسموح لأن الإضافة تكون حصراً في النهاية والحذف من المقدمة.
- محاولة حذف عنصر من طابور فارغ دون التحقق المسبق، مما ينتج عنه خطأ IndexError: pop from empty list.
سؤالان للتدريب مع الإجابة
السؤال الأول: ما الفرق الأساسي في آلية الحذف والإضافة بين المكدس والطابور؟ الإجابة: في المكدس تتم الإضافة وحذف العنصر من نفس الجانب، بينما في الطابور تتم الإضافة من جانب (النهاية) ويتم الحذف من الجانب الآخر (المقدمة).
السؤال الثاني: ما الوظيفة التي تؤديها الدالة queueName.qsize() عند استخدام الوحدة النمطية للطابور؟ الإجابة: تعود بقيمة حجم الطابور.