مبدأ تنفيذ قائمة انتظار جافا
كلمة "قائمة الانتظار" هي ما تسميه البريطاني "قائمة الانتظار". "السقف في الخط" في المملكة المتحدة يعني الوقوف على التوالي. في علوم الكمبيوتر ، فإن قائمة الانتظار عبارة عن بنية بيانات ، تشبه إلى حد ما المكدس ، باستثناء أنه سيتم إزالة عنصر البيانات الأول الذي تم إدخاله في قائمة الانتظار أولاً ، وفي المكدس ، تتم إزالة عنصر البيانات الأخير أولاً. تعمل قائمة الانتظار مثل صفوف الأشخاص الذين يقفون أمام السينما: أول شخص يدخل الانتماء سيصل إلى رأس الفريق لشراء التذاكر. يمكن لآخر شخص يتصطف شراء التذاكر.
تستخدم قوائم الانتظار أيضًا كأدوات للمبرمجين ، مثل المكدس. يمكن استخدامه أيضًا لمحاكاة البيئات في العالم الحقيقي ، مثل محاكاة الأشخاص الذين ينتظرون في أحد البنوك أو الطائرات التي تنتظر الإقلاع أو الحزم على الإنترنت تنتظر نقلها.
في نظام تشغيل الكمبيوتر ، تعمل قوائم الانتظار المختلفة بهدوء. مهمة الطباعة تنتظر الطباعة في قائمة انتظار الطباعة. عند الكتابة على لوحة المفاتيح ، يوجد أيضًا قائمة انتظار تخزن الكتابة. وبالمثل ، إذا تم استغلال المفتاح باستخدام معالج نصوص وعليه القيام بشيء آخر مؤقتًا ، فلن يضيع المحتوى المستقر ، وسوف ينتظر في قائمة الانتظار حتى يتوفر معالج النصوص لقراءته. يتم استخدام قائمة الانتظار للتأكد من عدم تغيير ترتيب الكتابة عند معالجتها.
العمليات الأساسية لقوائم الانتظار
تقوم العمليتان الأساسيتان لقائمة الانتظار بإدخال (إدراج) عنصر بيانات ، أي وضع عنصر بيانات واحد في ذيل قائمة الانتظار ، والآخر هو إزالة (إزالة) عنصر البيانات ، أي إزالة عنصر البيانات على رأس الفريق. هذا مشابه لعشاق الأفلام في قائمة الانتظار حتى نهاية الخط عندما يصطفون في الانتظار لشراء التذاكر ، ثم الوصول إلى رأس الخط ثم ترك قائمة الانتظار.
تسمية طرق إدخال وإزالة عناصر البيانات في المكدس هي قياسية للغاية ، تسمى Push and Pop. لم يتم تسمية طريقة قائمة الانتظار الموحدة حتى الآن. يمكن استدعاء "إدراج" PUT أو ADD أو ENQUE ، في حين يمكن تسمية "Delete" Delete أو Get أو Deque. يمكن أيضًا استدعاء نهاية عنصر بيانات الإدراج مرة أخرى أو الذيل أو النهاية. يمكن أيضًا استدعاء رئيس الفريق الذي يزيل عنصر البيانات. سيتم استخدام إدراج ، وإزالته ، الأمامية والخلفية أدناه.
أدخل إدخال القيمة في ذيل قائمة الانتظار ، ويتم إضافة ذيل سهم قائمة الانتظار للإشارة إلى عنصر البيانات الجديد.
بعد إزالة عنصر البيانات ، يتم إضافة رأس الفريق بواسطة واحد. عادةً عند تطبيق قائمة انتظار ، سيتم حفظ عنصر البيانات المحذوفة في الذاكرة ، ولكن لا يمكن الوصول إليه لأنه تم نقل رأس قائمة الانتظار إلى موقعه التالي.
على عكس الحالة الواردة في المكدس ، لا تبدأ عناصر البيانات الموجودة في قائمة الانتظار دائمًا في المفرقة 0 من الصفيف. بعد إزالة بعض عناصر البيانات ، يشير مؤشر الرأس إلى موضع ترجمي أعلى.
تقوم عملية العرض بإرجاع قيمة عنصر بيانات الرأس ، لكنها لا تحذف عنصر البيانات من الفريق.
إذا كنت ترغب في إزالة عنصر بيانات من قائمة انتظار فارغة أو أدخل عنصر بيانات في قائمة انتظار كاملة ، فسيطلب التطبيق رسالة خطأ.
قائمة انتظار حلقة
عند إدراج عنصر بيانات جديد في قائمة الانتظار ، يتحرك السهم الخلفي على رأس الفريق لأعلى نحو الموضع الكبير لمرحلة الصفيف. عند إزالة عناصر البيانات ، يتحرك ذيل قائمة الانتظار أيضًا للأعلى. قد يكون هذا التصميم مخالفًا للملاحظة المباشرة للناس ، لأنه عندما يصطف الناس لتذاكر الأفلام ، يتحرك قائمة الانتظار دائمًا للأمام ، وبعد أن يشتري الشخص الذي أمامهم التذكرة ويترك قائمة الانتظار ، يتحرك الآخرون إلى الأمام. بعد حذف عنصر بيانات في قائمة الانتظار في الكمبيوتر ، يمكنك أيضًا نقل جميع عناصر البيانات الأخرى إلى الأمام ، ولكن هذا فعال للغاية. بدلاً من ذلك ، نحتفظ بجميع عناصر البيانات في موضع نفسه من خلال حركة مؤشرات قائمة الانتظار.
المشكلة في هذا التصميم هي أن مؤشر الذيل سينتقل بسرعة إلى نهاية الصفيف. على الرغم من وجود وحدة عنصر بيانات فارغة في بداية الصفيف ، وهو موقع عنصر البيانات الذي تمت إزالته ، ولكن نظرًا لأن مؤشر الذيل لم يعد قادرًا على التحرك للخلف ، فلا يمكن إدراج عناصر البيانات الجديدة. ماذا علي أن أفعل؟
علاج الاختطاف
من أجل تجنب مشكلة قائمة الانتظار غير راضية ولكن عدم القدرة على إدراج عناصر بيانات جديدة ، يمكن أن يتم لف مؤشرات الرأس والذيل إلى بداية الصفيف. هذا هو قائمة انتظار الحلقة (أحيانًا تسمى أيضًا "حلقة عازلة").
عملية تغليف المؤشر: أدخل ما يكفي من عناصر البيانات في قائمة الانتظار لجعل مؤشر الذيل يشير إلى الطرف المتأخر من الصفيف. احذف بعض عناصر البيانات الأخرى في الواجهة الأمامية للمصفوفة. أدخل الآن عنصر بيانات جديد. سترى أنه سيتم عكس مؤشر الذيل من النهاية إلى موضع البداية. سيتم إدراج عناصر بيانات جديدة في هذا الموقع.
أدخل المزيد من عناصر البيانات. يتحرك مؤشر الذيل للأعلى كما هو متوقع. لاحظ أنه بعد إعادة توزيع مؤشر الذيل ، يكون الآن أسفل مؤشر الرأس ، الذي يعكس الموضع الأولي. يمكن تسمية ذلك بـ "تسلسل مكسور": توجد عناصر البيانات في قائمة الانتظار في تسلسلتين مختلفتين في الصفيف.
بعد حذف ما يكفي من عناصر البيانات ، يلتف رئيس الفريق أيضًا. في هذا الوقت ، يعود مؤشر قائمة الانتظار إلى حالة الموضع في وقت التشغيل الأولي ، ومؤشر الرأس أسفل مؤشر الذيل. تتم استعادة عناصر البيانات أيضًا إلى تسلسل مستمر واحد.
رمز جافا لقوائم الانتظار
يقوم برنامج Queue.java بإنشاء فئة قائمة انتظار ، والتي تحتوي على إدراج () ، وإزالة () ، و PEEK () ، و ISEMPTY () و SIZE ().
حزمة كومة وقائمة الانتظار ؛
قائمة انتظار الفئة {private int maxSize ؛ خاص طويل [] Quearray ؛ الجبهة الخاصة خلفية خاصة NITEMS الخاصة ؛ قائمة الانتظار العامة (int s) {maxSize = s ؛ QuearRay = جديد طويل [maxSize] ؛ الجبهة = 0 ؛ الخلفية = -1 ؛ nitems = 0 ؛ } public void insert (long j) {if (reach == maxSize-1) rear = -1 ؛ Quearray [++ الخلفية] = j ؛ nitems ++ ؛ } public remove () {long temp = quearray [Front ++] ؛ إذا (الأمامي == maxSize) الأمامي = 0 ؛ nitems-- ؛ عودة درجة الحرارة. } pleekfront {quearray الإرجاع العام الطويل () ؛ } boolean public isempty () {return (nitems == 0) ؛ } public boolean iffull () {return (nitems == maxSize) ؛ } size int public () {return nitems ؛ }}لا تحتوي فئة قائمة الانتظار التي تنفذها البرنامج على حقول الأمامية (الرأس) والخلفية (رئيس الفريق) ، ولكن أيضًا عدد عناصر البيانات الحالية في قائمة الانتظار: NITEMS.
الشرط المسبق لتشغيل طريقة insert () هو أن قائمة الانتظار غير راضية. لا يتم عرض هذه الطريقة في Main () ، ولكن يجب عادةً استدعاء طريقة insert () أولاً ثم يجب استدعاء طريقة ISULL () بعد العودة الخاطئة. (تتمثل النهج الأكثر عمومية في إضافة حكم إلى طريقة insert () للتحقق مما إذا كانت قائمة الانتظار ممتلئة. إذا تم إدخال عنصر بيانات في قائمة الانتظار الكاملة ، فسيتم طرح استثناء.)
بشكل عام ، تتمثل عملية الإدراج في إضافة خلفية (مؤشر ذيل الفريق) وإدراج بيانات جديدة في الموضع الذي أشار إليه مؤشر الذيل. ومع ذلك ، عندما يشير المؤشر الخلفي إلى الجزء العلوي من المصفوفة ، أي موضع maxSize-1 ، يجب أن يتم العودة إلى أسفل الصفيف قبل إدخال عنصر البيانات. تعمل عملية اللف على الجزء الخلفي إلى -1 ، لذلك عندما تتم إضافة الخلفية 1 ، فإنها تساوي 0 ، وهي قيمة التراجع في الجزء السفلي من الصفيف ، وأخيراً تتم إضافة NITEM واحدة.
الشرط المسبق لتشغيل طريقة إزالة () هو أن قائمة الانتظار ليست فارغة. قبل استدعاء هذه الطريقة ، يجب عليك الاتصال بالطريقة isEmpty () للتأكد من أن قائمة الانتظار ليست فارغة ، أو إضافة آلية التحقق من الخطأ هذه إلى طريقة إزالة ().
تحصل عملية إزالة دائمًا على قيمة عنصر بيانات الرأس من المؤشر الأمامي ، ثم تضيف الجهة الأمامية. ومع ذلك ، إذا قمت بذلك ، فإن قيمة الأمام تتجاوز الجزء العلوي من الصفيف ، فيجب أن تعود المقدمة إلى الموضع الذي يكون فيه ترجمة الصفيف 0. أثناء إجراء هذا الاختبار ، يتم تخزين قيمة الإرجاع مؤقتًا. أخيرًا يتم تقليل Nitem بواسطة واحد.
طريقة PEEK () بسيطة وسهلة الفهم: إنها تُرجع قيمة عنصر البيانات المشار إليها بواسطة المؤشر الأمامي. تسمح بعض تطبيقات قائمة الانتظار أيضًا بمشاهدة قيمة عنصر بيانات نهاية قائمة الانتظار ؛ على سبيل المثال ، يمكن تسمية هذه الطرق peekfront () ، و peekrear () ، أو فقط الأمام () والخلفية ().
تعتمد جميع أساليب ISEMPTY () و ISFULL () و SIZE () على حقل NITEMS ، والذي يعيد ما إذا كانت NITEMS تساوي 0 ، سواء كانت مساوية للمادة ، أو إرجاع قيمتها الخاصة.
ستضيف NITEMs في فئة قائمة الانتظار في فئة قائمة الانتظار عملية إضافية إلى إدراج () وإزالة () الأساليب ، لأن طرق insert () وإزالتها () يجب أن تزيد وخفض قيمة هذا المتغير على التوالي. قد لا يكون هذا جزءًا إضافيًا ، ولكن إذا تعاملت مع الكثير من عمليات الإدراج وإزالة العمليات ، فقد يؤثر ذلك على الأداء.
نظرًا لأن بعض تطبيقات قائمة الانتظار لا تستخدم حقول حساب عنصر البيانات ، ولكن استخدم الأمامي والخلفي لحساب ما إذا كانت قائمة الانتظار فارغة أو كاملة وعدد عناصر البيانات. إذا قمت بذلك ، فستكون روتين isEmpty () و iffull () و size () معقدة للغاية لأنه كما ذكرنا سابقًا ، يتم إما تسلسل عناصر البيانات إلى قسمين ، أو جزء مستمر.
ونشأت مشكلة غريبة. عندما تكون قائمة الانتظار ممتلئة ، تتخذ المؤشرات الأمامية والخلفية موضعًا معينًا ، ولكن عندما تكون قائمة الانتظار فارغة ، قد تظهر علاقة الموضع نفسها أيضًا. لذلك في الوقت نفسه ، قد يبدو أن قائمة الانتظار ممتلئة أو فارغة. الحل لهذه المشكلة هو: اجعل سعة الصفيف أكثر من الحد الأقصى لعدد عناصر بيانات قائمة الانتظار.
شكرا لك على القراءة ، آمل أن تساعدك. شكرا لك على دعمك لهذا الموقع!