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

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

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

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

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

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

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