هيكلة البيانات بواسطة طابور البيانات Queue

مفهوم طابور البيانات Queue:

تعني قائمة الانتظار، وتُصنف ضمن هياكل البيانات الخطية و المجردة (abstract)، على عكس الـ (stack)، فإن الـ (queue) مفتوحة من كلا الطرفين، حيث يتم إدخال العنصر الأول من على طرف النهاية (tail)، ويتم حذف العنصر الموجود من طرف الأمامي (head). ويطلق على ال(queue) أنها بنية “FIFO” أي “First In First Out” وتعني أن العناصر التي تم وضعها في ال(queue) في البداية ستظهر أولاً، والعناصر التي تم وضعها في الـ (queue) في النهاية ستظهر أخيرًا.

مثال على قائمة الانتظار (queue) هي طوابير الانتظار، حيث أن أول شخص في الطابور يذهب أولاً، وآخر شخص في الطابور يذهب أخيرًا. وتسمى عملية إضافة عنصر إلى قائمة الانتظار “enqueuing” وعملية إزالة عنصر من قائمة انتظار تسمى “dequeuing”.

العمليات الأساسية في طابور البيانات Queue:

• ()push() or Enqueue: إضافة عنصر إلى نهاية (queue)، لكن إذا كانت (queue) ممتلئة فإنه يقوم بطباعة “Queue overflow”.

• ()pop() or Dequeue: إزالة عنصر من مقدمة (queue)، لكن إذا كانت (queue) فارغة فإنه يقوم بطباعة “Queue underflow”.

• ()IsEmpty: تحقق ممّا إذا كانت (queue) فارغة. إذا كانت فارغة فإنه يقوم بإرجاع (true) وإلا فإنه يُرجع (false).

• ()IsFull: تحقق ممّا إذا كانت (queue) ممتلئة. إذا كانت ممتلئة فإنه يقوم بارحاع (true) والا فإنه يُرجع (false).

•  ()Peek() or front: احصل على قيمة مقدمة (queue) دون إزالتها

ما هو تعقيد الوقت Complexity time لعمليات Queue؟

التعقيد الزمني (time complexity) للإدخال (enqueuing) هو (O(1، ويكون الحذف (dequeuing) هو (O(1 (لكن هذا يعتمد على كيفية تنفيذك لهذه العملية).

أنواع طابور البيانات في هياكل البيانات:

• Simple Queue: في قائمة انتظار البسيطة، يتم الإدخال في الخلف ويحدث الإزالة في المقدمة، ويتبع بدقة قاعدة (FIFO).

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

• Priority Queue: قائمة انتظار الأولوية هي نوع خاص من قائمة الانتظار حيث يرتبط كل عنصر بأولوية ويتم تقديمه وفقًا لأولويته. في حالة حدوث عناصر لها نفس الأولوية، يتم تقديمها وفقًا لترتيبها في قائمة الانتظار.

• (Dequeue (Double Ended Queue: في قائمة الانتظار ذات النهايتين، يمكن إدخال العناصر وإزالتها إما من الأمام أو الخلف. وبالتالي، فإنه لا يتبع قاعدة (First In First Out).