طابور

من ويكيبيديا، الموسوعة الحرة

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

[تحرير] في علم الحاسوب

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

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

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

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

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

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

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

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