الطوابير (Queues)
الطابور FIFO
- الطابور هو أول يدخل، أول يخرج (FIFO).
- أول عنصر تضيفه هو الأول الذي يغادر.
- فكر في طابور من الناس: الشخص في الأمام يتم خدمته أولاً.
enqueue و dequeue مع قائمة
- يمكننا بناء طابور من قائمة بايثون.
- enqueue =
queue.append(x)— أضف إلى الخلف. - dequeue =
queue.pop(0)— أزل وأعد القيمة الأمامية.
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
front و empty
- انظر إلى الأمام دون إزالته:
queue[0]. - يكون الطابور فارغًا عندما
len(queue) == 0. - تحقق من أنه ليس فارغًا قبل dequeue.
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
ملاحظة حول السرعة
- يجب على
pop(0)تحريك كل عنصر آخر للأمام بمكان واحد. - بالنسبة لطابور كبير، يكون بطيئًا، لذا فإنه يستهلك المزيد من الوقت.
- الأنظمة الحقيقية تستخدم مُخبّر دائري مع مؤشرات أمامية وخلفية بدلاً من ذلك.
في الرمز الوهمي لكامبريدج
- يبني الامتحان طابورًا من مصفوفة مع مؤشر
frontومؤشرrear.
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
أخطاء شائعة
- الطابور first-in, first-out: join the back, leave from the front.
- تحقق من أنه ليس فارغًا قبل dequeue.
الآن جرب بنفسك
- استخدم قائمة كطابور (
appendلـ enqueue،pop(0)لـ dequeue). - اضغط على تحقق من الإجابة لاختبار الكود الخاص بك.
الطابور يعمل بنظام FIFO
يضيف الطابور في الخلف ويزيل من الأمام — أول يدخل، أول يخرج.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
ابدأ بطابور فارغ. أضف "a"، ثم "b"، ثم "c". ثم أخرج مرة واحدة، واحفظ القيمة المحذوفة في first. (يجب أن يكون first هو "a" والطابور يجب أن يكون ["b", "c"].)
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أضف 1، 2، 3 إلى طابور، ثم أخرجهم جميعاً إلى result. على عكس المكدس، يحافظ الطابور على نفس الترتيب. (يجب أن يكون result هو [1, 2, 3].)
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب serve(queue) التي تخرج العنصر الأمامي: أزلها من القائمة و ارجع إياها. يجب أن تصبح قائمة المُدْعى أقصر.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب front(queue) التي ترجع العنصر الأمامي دون إزالته، بحيث يبقى الطابور كما هو. إذا كان الطابور فارغاً، ارجع None.
اضغط تشغيل لرؤية المخرجات هنا.