طابور

في علوم الحاسوب، الطابور هو ترتيب لأشياء بحيث تتوالي، ويكون أول شيء يدخل الطابور هو أول ما يخرج منه ، وآخر ما يدخله هو آخر ما يخرج منه.

في علم الحاسوب

تستخدم بنية بيانات الطابور في علم الحاسوب بشكل مكثف وتسمى بالإنجليزية Queue. وتعرّف بأنها مجموعة لها مبدأ في الترتيب هو إما FIFO ، أي First In First Out بمعنى الداخل أولا هو الخارج أولا ، والآخر LIFO أي Last In First Out بمعنى الداخل أخيرا هو الخارج أولا وهذا النوع مشهور بإسم الرصّة أو التكديس ، وبالإنجليزية يسمى Stack ، ويمكن تخيله بمجموعة صحون مرتبة فوق بعضها البعض ، فأول صحن يوضع سيكون آخر صحن يمكن أخذه إذا كنت تأخذ الصحون من الأعلى ، وآخر صحن وضع في الأعلى سيكون أول صحن يمكن آخذه. للمزيد من المعلومات عن النوع الثاني ، إقرا مقال ال[المكدس].

بالنسبة للطابور فإن بناءه يمكن أن يتم بعدّة طرق ، منها جدول أو صفيف بسيط ، أو كسلسلة مترابطة يتم زيادة العناصر إليها ، فتكون كأنها جدول يتم تغيير حجمه بحسب الحاجة.

الطابور كبناء بياناتيّ

في حال تم بناء الطابور كجدول Array ، فإن بناءه يكون بحيث يكون بداية الطابور يساوي نهايته في حال كان الطابور فارغا ، فلو أن الجدول فيه عشرة عناصر ، فإن الفرق بين العنصر الأول والأخير سيكون صفرا عندما يكون الطابور فارغا .

في الرسم السابق F تمثل العنصر الأول في الطابور بينما R تمثل العنصر الأخير،

وفي الرسم السابق نلاحظ أن الحد الأقصى لعدد عناصر الطابور هو n.

عند إدراج عنصر ما في الطابور فإنه يحتل المؤخرة ، فهو آخر عنصر في الطابور ، وبالتالي ، فإن نهاية الطابور ستتقدم بمقدار وحدة ، وعند إخراج عنصر من الطابور ، فإن المقدمة ستنتقل للعنصر التالي ، وسيزداد عداد بداية الطابور وحدة واحدة .

عندما يصبح الطابور ممتلأ فإن نهاية الطابور ستساوي الحجم الأكبر للطابور ، ولو كان بناء الطابور دورانيا ، أي أنه عندما يخرج عنصر من الطابور فإن الطابور لا يتقدم بالكامل ، ولكن فقط مؤشر البداية ينتقل للعنصر التالي ، فإن الطابور يمتليء عندما يصبح زيادة عنصر على بداية الطابور سيؤدي إلى الكتابة فوق مقدمته ، اي ان باقي قسمة نهاية الطابور +1 على حجم الطابور سيساوي قيمة المؤشر على الخانة الأولى.