مفهوم – queue أو الطابور هو بنية معطيات مجردة مكونة من مجموعة تحتوي على عدد من العناصر التي يتم الحفاظ على ترتيبها وفق نظام FIFO ومعناها First In First Out.
الـ Queue أو نظام الطابور هي نفس فكرة عمل ال Stack ولكن هناك مكانين يخرج منهم البيانات وتقوم بإضافة البيانات بواسطة enqueue() وإزالة البيانات بواسطة dequeue() والترتيب الخاص به يعمل بنظام FIFO كما أوضحنا وهي تعنى العنصر الذي يدخل في البداية هو الذي يخرج أولًا First In First Out.
أقرب مثال على الطابور هو قوائم الانتظار أو الــ Waiting List حيث نجد أن أول من يدخل هو أول من يخرج و آخر من يدخل هو آخر من يخرج وهذا النوع من الترتيب يُعرف اختصاراً بــ FIFO أي First In First Out.
كما هو الحال مع Stack , فإن queue لا يملك نوع بيانات خاص به وإنما هو مجرد تركيبة يُمكن محاكاتها باستخدام المصفوفات أو القوائم (سواء كانت بسيطة أو مزدوجة) أو حتى الأشجار (Trees).
لذلك يمكن أن نقول من يأتي أولا يتم خدمته أولا لذلك تجد الإختلاف بينه وبين ال Stack هو انه في ال Stack يأتي الزبون آخر شخص ويمشي أول شخص ولكن في ال Queue يأتي الزبون أول شخص ويمشي أول شخص.
ماذا نحتاج لإنشاء طابور Queues؟
هناك شبه كبير بين Queues والـ stuck الا أنه هناك أختلاف فجميع الـ func موجودة ولكن مع تغير طفيف:
-إضافة عنصر جديد الى الطابور.
– حذف أول عنصر في الطابور.
– الاستعلام عن بداية الطابور.
– تصفية الطابور Queues (حذف جميع العناصر).
– فحص إذا ما كان الطابور خالٍ.
اقرأ ايضًا:
العمليات الأساسية في طابور البيانات 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).