رتل (بنية معطيات)

توضيح لخاصية الداخل-أولاً-يخرج-أولاً

يعرّف الرتل (أو الطابور) (Queue)‏ وينطق (‎/ˈkjuː/‏) في علوم الحاسب بأنه بنية معطيات مجردة مكونة من مجموعة تحتوي على عدد من العناصر التي يتم الحفاظ على ترتيبها وفق قانون محدد، تسمح هذه المجموعة للمستخدم بإجراء مجموعة من العمليات على العناصر بما فيها إضافة عنصر جديد إلى مؤخرة المجموعة (تسمى هذه العملية إدراج (Enqueue)‏ وحذف العنصر الموجود في مقدمة المجموعة (تسمى هذه العملية سحب (Dequeue)‏.^[1][2][3] تجعل هذه العمليات الرتل بنية معطيات يشار إليها عادةً باسم الداخل-أولاً-يخرج-أولاً (First In First Out)‏ أو اختصاراً (FIFO) ذلك أن ترتيب العناصر المدرجة يوافق تماماً ترتيب العناصر المسحوبة. يتوافق ترتيب إدراج وسحب العناصر بهذه الطريقة مع الكثير من الحالات التي يتطلب فيها إدخال عنصر جديد إخراج كافة العناصر السابقة قبل التمكن من الحصول عليه مرة أخرى. غالباً ما تضاف عمليات أخرى مثل عملية الاستراق (Peek)‏ أو المقدمة (Front)‏ التي تعيد قيمة العنصر الموجود في مقدمة الرتل دون سحبه من الرتل. يعتبر الرتل مثالاً على بنى المعطيات الخطية، أو بمعنى أكثر تجريداً مجموعةً متسلسلة.

يستخدم الرتل بكثرة في علوم الحاسب والنقل وبحوث العمليات التي عادةً ما تشتمل على وجود العديد من العناصر كالكائنات البيانية والأشخاص أو حتى الأحداث التي يتم تخزينها بغرض معالجتها لاحقاً. في هذه الحالات يستخدم الرتل كخابئ لهذه العناصر.

تستخدم الأرتال بشكل شائع في البرامج الحاسوبية حيث يتم تحقيقها كبنى معطيات مجهزة بعمليات الإدراج والسحب المشار إليها سابقاً، تشتمل التحقيقات أيضاً على الخوابئ الدائرية (Circular Buffers)‏ والقوائم المتصلة (Linked Lists)‏.

تحقيق الرتل

نظرياً يمتلك الرتل سعةً لانهائية. أي أنه بغض النظر عن عدد العناصر الموجودة ضمن الرتل يمكن دائماً إدراج عنصرٍ جديد. يمكن للرتل أن يكون فارغاً أيضاً، في هذه الحالة يصبح مستحيلاً سحب عنصر من الرتل ما لم يتم إدراجُ عنصرٍ جديد. عملياً تمتلك المصفوفات محددة الحجم سعةً محدودة ويجب مراعاة سعة المصفوفة عند استخدامها لتصميم رتل (عندما ملء المصفوفة بكافة العناصر فإن إدراج عنصر جديد سوف يسبب حدوث خطأ على سبيل المثال).

عند استخدام المصفوفة محدودة الحجم لبناء الرتل يصبح من غير الضروري نسخ العناصر إلى مقدمة الرتل عند سحب العنصر الموجود في المقدمة. يمكن القيام بذلك عن طريق تحويل المصفوفة إلى دائرة مغلقة وتمكين مؤشري رأس المصفوفة ونهاية المصفوفة من التجوال الدائم ضمن الدائرة مما يزيل الحاجة إلى نقل العناصر ضمن المصفوفة. فإذا كان للمصفوفة الحجم n عندئذ فإن حساب أدلة المصفوفة باستخدام باقي القسمة modulo n يحول المصفوفة إلى دائرة مغلقة. تعتبر هذه الطريقة من أبسط طرق بناء الرتل في لغات البرمجة علية المستوى إذا ما قارناها بالطريقة التي تقتضي التحقق في كل مرة فيما إذا تجاوز دليل المصفوفة أحد حدود المصفوفة (بعض لغات البرمجة تقوم بالتحقق من ذلك تلقائياً). يجب تحديد حجم المصفوفة قبل تعريفها عموماً، إلا أن بعض التحقيقات تقوم بمضاعفة حجم المصفوفة عند إدراج عنصر جديد إلى المصفوفة الممتلئة.

توجد العديد من التحقيقات الفعالة للأرتال، التحقيق الفعال هو الذي يتيح إجراء عمليتي الإدراج والسحب بتعقيد زمني قدره O(1)، من هذه التحقيقات:

• اللائحة المتصلة
  • اللائحة مضاعفة الاتصال تتطلب O(1) لإضافة وإزالة عنصر من مقدمة اللائحة ومؤخرتها، لهذا تعتبر اللوائح مضاعفة الاتصال الخيار الأكثر شيوعاً لتحقيق الأرتال.
  • تمتلك اللائحة المتصلة إدخالاً وإزالة فعالتين عنجد أحد حدود اللائحة فقط. على كل الأحوال فإن إضافة مؤشر إلى العقدة الأخيرة في اللائحة يحسن أداء إضافة عنصر إلى نهاية اللائحة ويحسن من أداء الرتل بشكل عام.
• الرتل مضاعف النهاية (Deque)‏ يمكن تحقيقه بشكل فعال باستخدام بنية معطيات مخصصة من المصفوفات الديناميكية.

تحقيق الرتل في لغات البرمجة

يمكن تحقيق الأرتال كبنى معطيات منفصلة أو على اعتبارها حالةً خاصة من الأرتال مضاعفة النهاية. على سبيل المثال تتيح لغتي البرمجة بيرل وروبي إمكانية دفع وإزالة عناصر من المصفوفة من كلا النهايتين بحيث يمكن هذه العمليات لمحاكاة عمليات الإدراج والسحب الخاصة بالرتل.

توفر مكتبة القوالب المعيارية الخاصة بلغة سي++ القالب queue والذي يمكن استخدامه فقط مع عمليات الإدراج والسحب. كما توفر مكتبة لغة جافا ابتداءً من الإصدار J2SE5.0 الواجهة Queue التي تعرض طرق الرتل (الإدراج والإزالة)، يحقق هذه الواجهة الصف LinkedList والصف ArrayDeque (ابتداءً من الإصدار J2SE 1.6). توفر لغة بي إتش بي الصف SplQueue لهذا الغرض.

انظر أيضاً

• نظرية الرتل
• المكدس

مراجع

موسوعات ذات صلة :

• موسوعة برمجة الحاسوب
• موسوعة خوارزميات