TechCodeview

العمليات على قائمة الانتظار الدائرية

فيما يلي العمليات التي يمكن تنفيذها في قائمة الانتظار الدائرية:

أمام:يتم استخدامه للحصول على العنصر الأمامي من قائمة الانتظار.مؤخرة:يتم استخدامه للحصول على العنصر الخلفي من قائمة الانتظار.قائمة الانتظار (القيمة):يتم استخدام هذه الوظيفة لإدراج القيمة الجديدة في قائمة الانتظار. يتم دائمًا إدخال العنصر الجديد من الطرف الخلفي.قائمة الانتظار ():تقوم هذه الوظيفة بحذف عنصر من قائمة الانتظار. يتم الحذف في قائمة الانتظار دائمًا من الواجهة الأمامية.

تطبيقات قائمة الانتظار الدائرية

يمكن استخدام قائمة الانتظار الدائرية في السيناريوهات التالية:

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

عملية قائمة الانتظار

خطوات تشغيل قائمة الانتظار مذكورة أدناه:

• أولاً، سوف نتحقق مما إذا كانت قائمة الانتظار ممتلئة أم لا.
• في البداية تم ضبط الجزء الأمامي والخلفي على -1. عندما نقوم بإدراج العنصر الأول في قائمة الانتظار، يتم تعيين كل من الأمام والخلف على 0.
• عندما نقوم بإدخال عنصر جديد، يتم زيادة الجزء الخلفي، أي: خلفي=خلفي+1 .

سيناريوهات لإدراج عنصر

هناك سيناريوهين لا تكون قائمة الانتظار ممتلئة فيهما:

إذا كان خلفي! = الحد الأقصى - 1، ثم سيتم زيادة الخلفية إلى وزارة الدفاع (الحجم الأقصى) وسيتم إدراج القيمة الجديدة في النهاية الخلفية لقائمة الانتظار.إذا كان الأمامي! = 0 والخلفي = الحد الأقصى - 1، فهذا يعني أن قائمة الانتظار ليست ممتلئة، ثم اضبط قيمة الخلفية على 0 وأدخل العنصر الجديد هناك.

هناك حالتان لا يمكن إدراج العنصر فيهما:

• متى الجبهة ==0 && الخلفي = الحد الأقصى -1 ، مما يعني أن الجزء الأمامي في الموضع الأول من قائمة الانتظار والخلف في الموضع الأخير من قائمة الانتظار.
• أمامي == خلفي + 1؛

خوارزمية لإدراج عنصر في قائمة انتظار دائرية

الخطوة 1: إذا (خلفي + 1)٪ ماكس = أمامي
اكتب 'تجاوز'
انتقل إلى الخطوة 4
[نهاية إذا]

الخطوة 2: إذا كان الأمامي = -1 والخلفي = -1
ضبط أمامي = خلفي = 0
آخر إذا كان الخلف = الحد الأقصى - 1 والأمام! = 0
تعيين الخلفي = 0
آخر
ضبط خلفي = (خلفي + 1) % كحد أقصى
[نهاية إذا]

الخطوه 3: تعيين قائمة الانتظار [خلفي] = VAL

الخطوة 4: مخرج

عملية Dequeue

خطوات عملية dequeue موضحة أدناه:

• أولاً، نتحقق مما إذا كانت قائمة الانتظار فارغة أم لا. إذا كانت قائمة الانتظار فارغة، فلن نتمكن من إجراء عملية إلغاء الانتظار.
• عند حذف العنصر، يتم تقليل قيمة الواجهة بمقدار 1.
• إذا كان هناك عنصر واحد فقط متبقي ليتم حذفه، فسيتم إعادة ضبط الجزء الأمامي والخلفي على -1.

خوارزمية لحذف عنصر من قائمة الانتظار الدائرية

الخطوة 1: إذا كانت الجبهة = -1
اكتب 'التدفق السفلي'
انتقل إلى الخطوة 4
[نهاية إذا]

الخطوة 2: تعيين VAL = قائمة الانتظار [الأمامية]

الخطوه 3: إذا كان الأمامي = الخلفي
ضبط أمامي = خلفي = -1
آخر
إذا كان الأمام = الحد الأقصى -1
الجبهة = 0
آخر
ضبط الجبهة = الجبهة + 1
[نهاية إذا]
[نهاية إذا]

الخطوة 4: مخرج

دعونا نفهم عملية enqueue وdequeue من خلال التمثيل التخطيطي.

تنفيذ قائمة الانتظار الدائرية باستخدام المصفوفة

 #include # define max 6 int queue[max]; // array declaration int front=-1; int rear=-1; // function to insert an element in a circular queue void enqueue(int element) { if(front==-1 && rear==-1) // condition to check queue is empty { front=0; rear=0; queue[rear]=element; } else if((rear+1)%max==front) // condition to check queue is full { printf('Queue is overflow..'); } else { rear=(rear+1)%max; // rear is incremented queue[rear]=element; // assigning a value to the queue at the rear position. } } // function to delete the element from the queue int dequeue() { if((front==-1) && (rear==-1)) // condition to check queue is empty { printf('
Queue is underflow..'); } else if(front==rear) { printf('
The dequeued element is %d', queue[front]); front=-1; rear=-1; } else { printf('
The dequeued element is %d', queue[front]); front=(front+1)%max; } } // function to display the elements of a queue void display() { int i=front; if(front==-1 && rear==-1) { printf('
 Queue is empty..'); } else { printf('
Elements in a Queue are :&apos;); while(i<=rear) { printf('%d,', queue[i]); i="(i+1)%max;" } int main() choice="1,x;" variables declaration while(choice<4 && choice!="0)" while loop printf('
 press 1: insert an element'); printf('
press 2: delete 3: display the printf('
enter your choice'); scanf('%d', &choice); switch(choice) case printf('enter element which is to be inserted'); &x); enqueue(x); break; dequeue(); display(); }} return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/14/circular-queue-10.webp" alt="Circular Queue"> <h3>Implementation of circular queue using linked list</h3> <p>As we know that linked list is a linear data structure that stores two parts, i.e., data part and the address part where address part contains the address of the next node. Here, linked list is used to implement the circular queue; therefore, the linked list follows the properties of the Queue. When we are implementing the circular queue using linked list then both the <strong> <em>enqueue and dequeue</em> </strong> operations take <strong> <em>O(1)</em> </strong> time.</p> <pre> #include // Declaration of struct type node struct node { int data; struct node *next; }; struct node *front=-1; struct node *rear=-1; // function to insert the element in the Queue void enqueue(int x) { struct node *newnode; // declaration of pointer of struct node type. newnode=(struct node *)malloc(sizeof(struct node)); // allocating the memory to the newnode newnode-&gt;data=x; newnode-&gt;next=0; if(rear==-1) // checking whether the Queue is empty or not. { front=rear=newnode; rear-&gt;next=front; } else { rear-&gt;next=newnode; rear=newnode; rear-&gt;next=front; } } // function to delete the element from the queue void dequeue() { struct node *temp; // declaration of pointer of node type temp=front; if((front==-1)&amp;&amp;(rear==-1)) // checking whether the queue is empty or not { printf(&apos;
Queue is empty&apos;); } else if(front==rear) // checking whether the single element is left in the queue { front=rear=-1; free(temp); } else { front=front-&gt;next; rear-&gt;next=front; free(temp); } } // function to get the front of the queue int peek() { if((front==-1) &amp;&amp;(rear==-1)) { printf(&apos;
Queue is empty&apos;); } else { printf(&apos;
The front element is %d&apos;, front-&gt;data); } } // function to display all the elements of the queue void display() { struct node *temp; temp=front; printf(&apos;
 The elements in a Queue are : &apos;); if((front==-1) &amp;&amp; (rear==-1)) { printf(&apos;Queue is empty&apos;); } else { while(temp-&gt;next!=front) { printf(&apos;%d,&apos;, temp-&gt;data); temp=temp-&gt;next; } printf(&apos;%d&apos;, temp-&gt;data); } } void main() { enqueue(34); enqueue(10); enqueue(23); display(); dequeue(); peek(); } </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/14/circular-queue-11.webp" alt="Circular Queue"> <hr></=rear)>

انتاج: