طابور

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

في علم الحاسب الآلي[عدل]

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

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

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

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

طابور كمصفوفة ذات بعد واحد

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

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

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

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