books queue realization
If you do not find what you're looking for, you can use more accurate words.
تحقيق الرتل (Info)
نظرياً يمتلك الرتل سعةً لانهائية. أي أنه بغض النظر عن عدد العناصر الموجودة ضمن الرتل يمكن دائماً إدراج عنصرٍ جديد. يمكن للرتل أن يكون فارغاً أيضاً، في هذه الحالة يصبح مستحيلاً سحب عنصر من الرتل ما لم يتم إدراجُ عنصرٍ جديد. عملياً تمتلك المصفوفات محددة الحجم سعةً محدودة ويجب مراعاة سعة المصفوفة عند استخدامها لتصميم رتل (عندما ملء المصفوفة بكافة العناصر فإن إدراج عنصر جديد سوف يسبب حدوث خطأ على سبيل المثال).
عند استخدام المصفوفة محدودة الحجم لبناء الرتل يصبح من غير الضروري نسخ العناصر إلى مقدمة الرتل عند سحب العنصر الموجود في المقدمة. يمكن القيام بذلك عن طريق تحويل المصفوفة إلى دائرة مغلقة وتمكين مؤشري رأس المصفوفة ونهاية المصفوفة من التجوال الدائم ضمن الدائرة مما يزيل الحاجة إلى نقل العناصر ضمن المصفوفة. فإذا كان للمصفوفة الحجم n عندئذ فإن حساب أدلة المصفوفة باستخدام باقي القسمة modulo n يحول المصفوفة إلى دائرة مغلقة. تعتبر هذه الطريقة من أبسط طرق بناء الرتل في لغات البرمجة علية المستوى إذا ما قارناها بالطريقة التي تقتضي التحقق في كل مرة فيما إذا تجاوز دليل المصفوفة أحد حدود المصفوفة (بعض لغات البرمجة تقوم بالتحقق من ذلك تلقائياً). يجب تحديد حجم المصفوفة قبل تعريفها عموماً، إلا أن بعض التحقيقات تقوم بمضاعفة حجم المصفوفة عند إدراج عنصر جديد إلى المصفوفة الممتلئة.
توجد العديد من التحقيقات الفعالة للأرتال، التحقيق الفعال هو الذي يتيح إجراء عمليتي الإدراج والسحب بتعقيد زمني قدره O(1)، من هذه التحقيقات:
- اللائحة المتصلة
- اللائحة مضاعفة الاتصال تتطلب O(1) لإضافة وإزالة عنصر من مقدمة اللائحة ومؤخرتها، لهذا تعتبر اللوائح مضاعفة الاتصال الخيار الأكثر شيوعاً لتحقيق الأرتال.
- تمتلك اللائحة المتصلة إدخالاً وإزالة فعالتين عنجد أحد حدود اللائحة فقط. على كل الأحوال فإن إضافة مؤشر إلى العقدة الأخيرة في اللائحة يحسن أداء إضافة عنصر إلى نهاية اللائحة ويحسن من أداء الرتل بشكل عام.
- الرتل مضاعف النهاية (بالإنجليزية: Deque) يمكن تحقيقه بشكل فعال باستخدام بنية معطيات مخصصة من المصفوفات الديناميكية.
تحقيق الرتل في لغات البرمجة
يمكن تحقيق الأرتال كبنى معطيات منفصلة أو على اعتبارها حالةً خاصة من الأرتال مضاعفة النهاية. على سبيل المثال تتيح لغتي البرمجة بيرل وروبي إمكانية دفع وإزالة عناصر من المصفوفة من كلا النهايتين بحيث يمكن هذه العمليات لمحاكاة عمليات الإدراج والسحب الخاصة بالرتل.
توفر مكتبة القوالب المعيارية الخاصة بلغة سي++ القالب queue والذي يمكن استخدامه فقط مع عمليات الإدراج والسحب. كما توفر مكتبة لغة جافا ابتداءً من الإصدار J2SE5.0 الواجهة Queue التي تعرض طرق الرتل (الإدراج والإزالة)، يحقق هذه الواجهة الصف LinkedList والصف ArrayDeque (ابتداءً من الإصدار J2SE 1.6). توفر لغة بي إتش بي الصف SplQueue لهذا الغرض.
