المخزن المؤقت الدائري أو قائمة الانتظار الدائرية هو الإصدار المتقدم من قائمة الانتظار العادية حيث يتم توصيل الفهرس الأخير وفهرس الذيل في بنية دائرية. يتبع المخزن المؤقت الدائري في لغة C++ طريقتين: enqueue() وdequeue(). نقوم بتنفيذ عملية المخزن المؤقت الدائري أو قائمة الانتظار الدائرية بناءً على هذه الطرق.
- تتحقق طريقة enqueue() لمعرفة ما إذا كان المخزن المؤقت ممتلئًا أم لا. بخلاف ذلك، تحقق من أن فهرس النهاية هو الأخير. إذا كان الأمر كذلك، فقم بتعيين قيمة الذيل إلى 0. وإذا لم يكن الأمر كذلك، فقم بزيادة قيمة الذيل بمقدار القيمة الموجودة في هذا الفهرس.
- تأخذ الدالة dequeue() القيمة من الفهرس الأمامي في قائمة الانتظار الدائرية. إذا كانت قائمة الانتظار فارغة، فستعرض رسالة قائمة الانتظار الفارغة تلك. وإلا فإنه يحصل على القيمة الأخيرة ويحذفها من قائمة الانتظار.
برنامج لتنفيذ المخزن المؤقت الدائري في C++
باتباع الطريقتين المذكورتين، نقوم بتنفيذ المخزن المؤقت الدائري في لغة C++. دعونا نفكر في جميع خطوات تنفيذ قائمة الانتظار الدائرية في لغة C++.
#تتضمن
استخدام اسم للمحطة؛
بناء MyQueue
{
كثافة العمليات رأس , ذيل ;
كثافة العمليات Qsize.
كثافة العمليات * NewArr;
MyQueue ( كثافة العمليات لا ) {
رأس = ذيل = -1 ;
Qsize = الحجم؛
NewArr = new int [ س ] ;
}
قائمة انتظار فارغة ( كثافة العمليات فال ) ;
int deQueue ( ) ;
قائمة انتظار العرض باطلة ( ) ;
} ;
بدءًا من الكود، نقوم أولاً بإنشاء بنية 'MyQueue' لتهيئة متغيرات الرأس والذيل. يمثل متغير الرأس المؤشرات الأمامية ويمثل الذيل المؤشرات الخلفية الخلفية للمصفوفة. بعد ذلك يتم تحديد حجم قائمة الانتظار الدائرية، والمشار إليها بالمتغير “Qsize”.
بعد ذلك، نحدد المصفوفة المخصصة ديناميكيًا لـ 'NewArr' والتي تخزن قيم قائمة الانتظار الدائرية. بعد ذلك، نستدعي MyQueue() وهو منشئ ونمرر المعلمة 'sz' لحجم قائمة الانتظار الدائرية. داخل مُنشئ MyQueue()، نقوم بتعيين القيمة '-1' لمؤشرات الرأس والذيل. تشير هذه القيمة السالبة إلى أن قائمة الانتظار فارغة الآن. للمضي قدمًا، نقوم بتعيين القيمة 'sz' التي تمثل حجم قائمة الانتظار الدائرية. يتم تعيين قائمة الانتظار الدائرية 'NewArr' بكلمة رئيسية جديدة لإنشاء مجموعة من الأعداد الصحيحة ضمن الحجم 'sz' المحدد.
بعد ذلك، نقوم بتعريف الدالتين enQueue() وdequeue(). يقوم enqueue() بإدراج القيم في قائمة الانتظار الدائرية المحددة من الذيل. ومع ذلك، يتم حذف العناصر الموجودة في رأس قائمة الانتظار الدائرية بواسطة الدالة dequeue(). تعرض دالة العضو showQueue() قيم قائمة الانتظار الدائرية.
الخطوة 1: إنشاء دالة لإدراج العناصر في مخزن مؤقت دائري
في الخطوة السابقة، قمنا بتعيين فئة حيث تتم تهيئة الأعضاء الخاصين وتعيين وظائف الأعضاء الخاصة لتنفيذ قائمة الانتظار الدائرية. الآن، قمنا بتعيين الوظيفة لإنشاء قائمة الانتظار الدائرية وإدراج القيم داخل قائمة الانتظار الدائرية باستخدام الخوارزمية.
باطلة MyQueue::enQueue ( كثافة العمليات فال ){
لو ( ( رأس == 0 && ذيل == مقاس كيو - 1 ) || ( ذيل == ( رأس - 1 ) % ( كيو سايز - 1 ) ) )
{
cout << ' \ن قائمة الانتظار ممتلئة' ;
يعود ;
}
آخر لو ( رأس == - 1 )
{
رأس = ذيل = 0 ;
NewArr [ ذيل ] = فال؛
}
آخر لو ( ذيل == مقاس كيو - 1 && رأس ! = 0 )
{
ذيل = 0 ;
NewArr [ ذيل ] = فال؛
}
آخر {
ذيل ++;
NewArr [ ذيل ] = فال؛
}
}
هنا، نستدعي الدالة 'enqueue()' من فئة 'MyQueue' لإدراج العنصر في قائمة الانتظار الدائرية إذا كانت قائمة الانتظار فارغة أو تحت التدفق. يتم تمرير الدالة 'enqueue()' باستخدام المعلمة 'val' وإدراج القيمة من ذيل قائمة الانتظار الدائرية. قمنا بتعيين شرط 'if-else' لإدراج القيم في قائمة الانتظار الدائرية لهذا الغرض. العبارة 'if' الأولى وهي 'if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))' تتحقق من شرطين سواء كان الرأس يكون في موضع البداية والذيل في موضع نهاية قائمة الانتظار الدائرية. ثم يتحقق ما إذا كان الذيل في موضع واحد في الجزء الخلفي من موضع الرأس. إذا تم استيفاء أي من هذه الشروط، فلن تكون قائمة الانتظار فارغة وستقوم المطالبة بإنشاء الرسالة.
بعد ذلك، لدينا شرط 'else-if' الذي يحدد ما إذا كانت قائمة الانتظار فارغة أم لا. إذا كان الأمر كذلك، يتم إدراج القيمة في قائمة الانتظار. نظرًا لأن الرأس يظل مساويًا لـ -1، فهذا يوضح أن قائمة الانتظار فارغة وأن القيمة مطلوبة لإدراجها في قائمة الانتظار الدائرية. لهذا، قمنا بتعيين الرأس والذيل يساوي 0. ثم نقوم بإدخال القيمة من موضع الذيل في قائمة الانتظار الدائرية 'NewArr'.
بعد ذلك، لدينا شرط 'else-if' الثالث الذي يتحقق مما إذا كان الذيل في الموضع الأخير من قائمة الانتظار وأن الرأس ليس هو موضع البداية لقائمة الانتظار. ينطبق هذا الشرط عندما يصل الذيل إلى النهاية ولا يزال هناك مساحة في موضع البداية. لهذا، نحن بحاجة إلى ضبط الرأس على 0، ويتم إضافة العنصر من موضع الذيل. وأخيرًا، إذا لم يتم استيفاء جميع الشروط المحددة، فلن تكون قائمة الانتظار فارغة أو ممتلئة. في هذه الحالة، نقوم بزيادة الذيل بمقدار 1 وتتم إضافة القيمة من موضع الذيل الجديد.
الخطوة 2: إنشاء وظيفة لحذف العناصر من المخزن المؤقت الدائري
قمنا بتعيين الكود السابق لإنشاء وإدراج العناصر في قائمة الانتظار الدائرية باستخدام وظيفة enqueue(). الآن، نحدد تنفيذ إزالة العناصر من المخزن المؤقت الدائري إذا فاض.
int MyQueue::deQueue ( ){
لو ( رأس == - 1 )
{
cout << ' \ن قائمة الانتظار مجانية' ;
يعود INT_MIN;
}
int MyData = NewArr [ رأس ] ;
NewArr [ رأس ] = -1 ;
لو ( رأس == ذيل )
{
رأس = -1 ;
ذيل = -1 ;
}
آخر لو ( رأس == مقاس كيو - 1 )
رأس = 0 ;
آخر
رأس ++;
يعود بياناتي؛
}
في الكود المعطى، نستدعي الدالة dequeue() من فئة 'Myqueue' لإزالة العنصر من فهرس الرأس. لذلك، لدينا عبارة 'if' التي تتحقق مما إذا كانت قائمة الانتظار فارغة. يتم تعيين الرأس بالقيمة '-1' التي تمثل قائمة الانتظار الفارغة. يتم إنشاء رسالة مفادها أن قائمة الانتظار فارغة ثم يتم إرجاع INT_MIN وهو الحد الأدنى الثابت لقيمة int. تحدد عبارة 'if' ما إذا كانت قائمة الانتظار غير مشغولة أم لا. لهذا، نحدد المتغير 'MyData' ونضع قيمة العنصر في رأس قائمة الانتظار. بعد ذلك، قمنا بتعيين الرأس في الموضع -1 مما يشير إلى إزالة هذه القيمة من قائمة الانتظار. بعد ذلك نتحقق مما إذا كان الرأس والذيل متساويين أم لا. إذا كان كلاهما متساويًا، فإننا نخصص القيمة '-1' لكليهما، مما يمثل قائمة الانتظار الدائرية الفارغة. أخيرًا، نتحقق مما إذا كانت الدالة dequeue() تعمل إذا كان الرأس في الفهرس الأخير لقائمة الانتظار. لهذا، قمنا بتعيينها بقيمة '0' التي تتكرر في بداية المصفوفة. إذا لم يكن أي من الشروط المحددة صحيحا، تتم زيادة قيمة الرأس ويتم إرجاع العنصر المدرج في قائمة الانتظار.
الخطوة 3: إنشاء دالة لإظهار عناصر المخزن المؤقت الدائري
في هذا القسم، نستدعي الدالة showQueue() لعرض عناصر قائمة الانتظار الدائرية 'NewArr'.
باطلة MyQueue::showQueue ( ){
لو ( رأس == - 1 )
{
cout << ' \ن قائمة الانتظار مجانية' ;
يعود ;
}
cout << ' \ن عناصر قائمة الانتظار الدائرية: ' ;
لو ( ذيل > = رأس )
{
ل ( إنت ط = رأس ; أنا < = ذيل ; أنا++ )
cout << NewArr [ أنا ] << ' ' ;
}
آخر
{
ل ( إنت ط = رأس ; أنا < كيو سايز؛ أنا++ )
cout << NewArr [ أنا ] << ' ' ;
ل ( إنت ط = 0 ; أنا < = ذيل ; أنا++ )
cout << NewArr [ أنا ] << ' ' ;
}
}
يتم التحقق أولاً من حالة قائمة الانتظار الفارغة. يتم عرض إشارة إلى أن قائمة الانتظار الدائرية مجانية إذا كانت قائمة الانتظار مجانية. وبخلاف ذلك، ستعرض الوظيفة عناصر قائمة الانتظار الدائرية. لهذا، نحدد عبارة 'if' حيث يكون لدينا ذيل أكبر من أو يساوي الرأس. تم تعيين هذا الشرط للتعامل مع الحالة عند عدم اكتمال قائمة الانتظار الدائرية.
في هذه الحالة، نستخدم حلقة 'for' للتكرار من الرأس إلى الذيل وطباعة قيم قائمة الانتظار الدائرية. الحالة التالية هي اكتمال قائمة الانتظار الدائرية. لهذا، نتحقق باستخدام شرط 'if' حيث يكون الذيل أقل من الرأس. ثم نحتاج إلى استخدام حلقتين حيث تتكرر الأولى من الرأس إلى نهاية قائمة الانتظار والثانية تتكرر من بداية الذيل.
الخطوة 4: إنشاء الوظيفة الرئيسية () لبرنامج قائمة الانتظار الدائرية
وأخيرًا، قمنا بإنشاء وظيفة main() الخاصة بالبرنامج حيث نقوم بإدخال خمسة أعداد صحيحة في قائمة الانتظار الدائرية وعرض الأعداد الصحيحة لقائمة الانتظار. بعد ذلك، نعرض الأعداد الصحيحة المحذوفة من قائمة الانتظار الدائرية عن طريق استدعاء الدالة dequeue(). بعد إزالة بعض العناصر من قائمة الانتظار، نقوم بملء قائمة الانتظار مرة أخرى عن طريق إدراج العناصر الجديدة باستخدام وظيفة enqueue().
انت مين ( ){
MyQueue ذلك ( 5 ) ;
// إدراج العناصر في قائمة الانتظار الدائرية
que.enQueue ( أحد عشر ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( خمسة عشر ) ;
// عناصر العرض موجودة في قائمة الانتظار الدائرية
que.showQueue ( ) ;
// حذف العناصر من قائمة الانتظار الدائرية
cout << ' \ن العنصر المحذوف = ' << que.deQueue ( ) ;
cout << ' \ن العنصر المحذوف = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
يعود 0 ;
}
انتاج:
يتم عرض نتائج تنفيذ قائمة الانتظار الدائرية على شاشة مطالبة C++.
خاتمة
في الختام، تم شرح موضوع المخزن المؤقت الدائري بعمق في هذه المقالة. لقد أنشأنا المخزن المؤقت الدائري أولاً، ثم شرحنا كيفية الحذف من قائمة الانتظار الدائرية، ثم عرضنا عناصر التعميم في لغة C++.