The Queue ADT

الفصل الخامس: الطابور (FIFO)

الهدف: فهم مبدأ "ما يدخل أولاً يخرج أولاً" وتنفيذه باستخدام المصفوفة الدائرية.
1

FIFO (First In, First Out)

كيف يعمل الطابور؟

تماما مثل طابور الدفع في السوبرماركت. الإضافة تكون من الخلف (Rear)، والخدمة (الحذف) تكون من الأمام (Front).

العمليات الأساسية ($O(1)$):
  • enqueue(x): إضافة عنصر في النهاية .
  • dequeue(): إزالة وإرجاع العنصر من البداية .
  • getFront(): رؤية من عليه الدور دون حذفه.
Out (Front) ← ← In (Rear)
Client 1
Client 2
Client 3
2

The Circular Array Problem

مشكلة المصفوفة العادية

عند حذف عنصر من البداية، تبقى خانة فارغة. إذا استمرينا في الإضافة والحذف، سيصل الـ Rear لنهاية المصفوفة بينما توجد مساحة فارغة في البداية!

[ _ , _ , Data , Data , Data ] (End!)

الحل: المصفوفة الدائرية (Circular)

عندما يصل المؤشر للنهاية، نجعله يلتف (Wrap Around) ويعود للبداية باستخدام باقي القسمة (Modulo).

back = (back + 1) % array.length;
array[back] = x;
currentSize++;

3

Applications of Queue

1. Printer Spooling (طابور الطباعة)

عندما يرسل عدة مستخدمين ملفات للطابعة، يتم وضعها في طابور لطباعتها بالترتيب.

2. Operating Systems (أنظمة التشغيل)

جدولة العمليات (Process Scheduling) تعتمد على طوابير لخدمة البرامج بشكل عادل.

3. Generating Binary Numbers

خوارزمية ذكية لتوليد الأرقام الثنائية (1, 10, 11, 100...):
ابدأ بـ "1". في كل خطوة، اسحب العنصر، اطبعه، ثم ضف إليه "0" وأعد إدخاله، وضف إليه "1" وأعد إدخاله.

🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / فخ

Circular Array: Empty or Full؟

في المصفوفة الدائرية، حالة "الامتلاء" وحالة "الفراغ" قد تبدو متشابهة (المؤشرات في نفس المكان).
الحل: نحتفظ بمتغير منفصل اسمه currentSize لتتبع عدد العناصر بدقة.

CALCULATION / حساب

Back Index Calculation

إذا كان طول المصفوفة 10، والـ front عند 8، والحجم الحالي 4. أين يقع الـ back (آخر عنصر)؟
القانون: (front + currentSize - 1) % length
الحساب: $(8 + 4 - 1) \% 10 = 11 \% 10 = 1$.

→ السابق (Ch 4) الفصل التالي (Ch 6) ←