في علوم الكمبيوتر، قائمة الانتظار هي بنية بيانات خطية حيث يتم وضع المكونات في أحد طرفيها وإزالتها من الطرف الآخر وفقًا لمبدأ 'الوارد أولاً يخرج أولاً' (FIFO). يمكن استخدام بنية البيانات هذه للتحكم في تسلسل الإجراء أو تخزين البيانات. لغة C هي لغة كمبيوتر ذات إمكانية قائمة الانتظار مدمجة في شكل صفائف أو قوائم مرتبطة.
صفات:
- قائمة الانتظار هي نوع من بنية البيانات الخطية التي يمكن إنشاؤها باستخدام مصفوفة أو قائمة مرتبطة.
- يتم نقل العناصر إلى الجزء الخلفي من قائمة الانتظار أثناء إزالتها من المقدمة.
- Enqueue (إضافة عنصر إلى الخلف) وdequeue (إزالة عنصر من الأمام) هما عمليتان في قائمة الانتظار.
- عند إضافة العناصر وإزالتها بشكل متكرر، قد يتم إنشاء قائمة انتظار كقائمة انتظار دائرية لمنع إضاعة الذاكرة.
باستخدام المصفوفة:
لتنفيذ قائمة انتظار في لغة C باستخدام مصفوفة، قم أولاً بتحديد الحد الأقصى لحجم قائمة الانتظار وإعلان مصفوفة بهذا الحجم. تم تعيين الأعداد الصحيحة الأمامية والخلفية على التوالي على 1. يمثل المتغير الأمامي العنصر الأمامي في قائمة الانتظار، ويمثل المتغير الخلفي العنصر الخلفي.
قبل دفع العنصر الجديد إلى الموضع النهائي لقائمة الانتظار، نحتاج إلى زيادة المتغير الخلفي بمقدار 1. قائمة الانتظار ممتلئة الآن ولا يمكن إضافة أي عناصر إضافية أخرى عندما يصل الموضع الخلفي إلى الحد الأقصى لسعة قائمة الانتظار. نضيف عنصرًا إلى مقدمة قائمة الانتظار ونزيد المتغير الأمامي بمقدار واحد فقط لإزالة عنصر من قائمة الانتظار. إذا كان الوضعان الأمامي والخلفي متساويين ولا يمكن حذف المزيد من المكونات، فيمكننا القول أن قائمة الانتظار فارغة.
فيما يلي مثال لقائمة انتظار مكتوبة بلغة C والتي تستخدم مصفوفة:
jsp
لغة البرمجة ج:
خطأ في الحماية العامة
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } سيكون إخراج الكود:
انتاج:
10 20 30 Queue is empty-1
توضيح:
- أولاً، نقوم بإدراج العناصر الثلاثة 10 و20 و30 في قائمة الانتظار.
- بعد ذلك، نقوم بحذف وطباعة العنصر الأمامي من قائمة الانتظار، وهو 10.
- بعد ذلك، نقوم بحذف العنصر الأمامي من قائمة الانتظار وطباعته مرة أخرى، وهو 20.
- ثم نقوم بحذف العنصر الأمامي من قائمة الانتظار وطباعته مرة أخرى، وهو 30.
- أخيرًا، نقوم بإنشاء قائمة انتظار من قائمة انتظار فارغة لإخراج 'قائمة الانتظار فارغة' وإرجاع -1.
استخدام القائمة المرتبطة:
هناك طريقة بديلة أخرى لإنشاء قائمة انتظار في لغة البرمجة C وهي استخدام القائمة المرتبطة. يتم التعبير عن كل عقدة في قائمة الانتظار باستخدام هذه الطريقة بواسطة عقدة تحتوي على قيمة العنصر ومؤشر إلى العقدة التالية في قائمة الانتظار. من أجل تتبع العقد الأولى والأخيرة في قائمة الانتظار، على التوالي، يتم استخدام المؤشرات الأمامية والخلفية.
نقوم بإنشاء عقدة جديدة بقيمة العنصر ونضبط المؤشر التالي على NULL لإضافة عنصر إلى قائمة الانتظار. بالنسبة للعقدة الجديدة، نقوم بتعيين المؤشرات الأمامية والخلفية إذا كانت قائمة الانتظار فارغة. إذا لم يكن الأمر كذلك، فإننا نقوم بتحديث المؤشر الخلفي ونضبط المؤشر التالي للعقدة الخلفية القديمة للإشارة إلى العقدة الجديدة.
كم عدد المفاتيح الموجودة في لوحات المفاتيح؟
عند حذف عقدة من قائمة الانتظار، يتم حذف العقدة السابقة أولاً، ثم يتم تحديث المؤشر الأمامي إلى العقدة اللاحقة في قائمة الانتظار، وأخيراً يتم تحرير الذاكرة التي كانت تشغلها العقدة المحذوفة. إذا كان المؤشر الأمامي فارغًا بعد الإزالة، فإن قائمة الانتظار فارغة.
فيما يلي مثال لقائمة انتظار تم تنفيذها في لغة C باستخدام قائمة مرتبطة:
لغة البرمجة ج:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } سيكون إخراج الكود:
انتاج:
بن إلى بي سي دي
10 20 30 Queue is empty-1
توضيح:
- أولاً، نقوم بإدراج العناصر الثلاثة 10 و20 و30 في قائمة الانتظار.
- بعد ذلك، نقوم بحذف وطباعة العنصر الأمامي من قائمة الانتظار، وهو 10.
- بعد ذلك، نقوم بحذف العنصر الأمامي من قائمة الانتظار وطباعته مرة أخرى، وهو 20.
- ثم نقوم بحذف العنصر الأمامي من قائمة الانتظار وطباعته مرة أخرى، وهو 30.
- وأخيرًا، نحاول إلغاء قائمة الانتظار من قائمة الانتظار الفارغة، والتي تطبع الرسالة 'قائمة الانتظار فارغة' وترجع -1.
مزايا:
- تعتبر قوائم الانتظار مفيدة بشكل خاص لتنفيذ الخوارزميات التي تتطلب معالجة العناصر بتسلسل دقيق، مثل البحث ذي العرض الأول وجدولة المهام.
- نظرًا لأن عمليات قائمة الانتظار لها تعقيد زمني O(1)، فيمكن تنفيذها بسرعة حتى في قوائم الانتظار الضخمة.
- تتميز قوائم الانتظار بالمرونة بشكل خاص حيث يمكن تنفيذها ببساطة باستخدام مصفوفة أو قائمة مرتبطة.
سلبيات:
- لا يمكن إنشاء قائمة الانتظار، على عكس المكدس، باستخدام مؤشر واحد، مما يجعل تنفيذ قائمة الانتظار أكثر تعقيدًا قليلاً.
- إذا تم إنشاء قائمة الانتظار كمصفوفة، فقد تمتلئ قريبًا إذا تمت إضافة عدد كبير جدًا من العناصر، مما يؤدي إلى حدوث مشكلات في الأداء أو ربما حدوث عطل.
- عند استخدام قائمة مرتبطة لتنفيذ قائمة الانتظار، يمكن أن يكون الحمل الزائد للذاكرة لكل عقدة كبيرًا، خاصة بالنسبة للعناصر الصغيرة.
خاتمة:
تشمل التطبيقات التي تستخدم قوائم الانتظار، وهي بنية بيانات مهمة، أنظمة التشغيل والشبكات والألعاب، على سبيل المثال لا الحصر. إنها مثالية للخوارزميات التي يجب أن تتعامل مع العناصر بترتيب معين نظرًا لسهولة إنشائها باستخدام مصفوفة أو قائمة مرتبطة. ومع ذلك، فإن قوائم الانتظار لها عيوب يجب مراعاتها عند اختيار بنية بيانات لتطبيق معين، مثل استهلاك الذاكرة وتعقيد التنفيذ.