المكدسات والطوابير - دليل دراسة شامل

🔥 المكدسات - LIFO (آخر من يدخل، أول من يخرج)

وش هو المكدس؟

المكدس (Stack) هو نوع بيانات مجرد (ADT) يخزن كائنات عشوائية ويشتغل بمبدأ آخر من يدخل هو أول من يخرج (LIFO). زي صينية الأطباق في المطاعم - آخر طبق تحطه فوق هو أول واحد تاخذه!

تصوير المكدس

د (القمة)

↓

أ (القاع)

LIFO: العنصر 'د' دخل آخر شي، فراح يطلع أول شي.

                    🔑 الخصائص الأساسية:
                    ترتيب LIFO: آخر عنصر تنزله هو أول عنصر تشيله.
وصول محدود: تقدر توصل بس للعنصر اللي في القمة.
حجم ديناميكي: يكبر ويصغر مع عمليات push/pop.

                

⚙️ عمليات المكدس

العمليات الرئيسية

1. push(object) - إدخال عنصر

يضيف عنصر في قمة المكدس.

void push(E element);
// يحط العنصر في القمة
// يحدّث الحجم
                    

2. pop() - يشيل ويرجع العنصر

يحذف ويرجع العنصر اللي في قمة المكدس.

E pop();
// يشيل العنصر اللي في القمة
// يرجع العنصر المحذوف
// يرجع null لو المكدس فاضي
// يقلل الحجم
                    

العمليات المساعدة

3. top() - يشوف القمة

يرجع العنصر اللي في القمة بدون ما يشيله.

E top();
// يرجع العنصر اللي في القمة بدون حذف
// يرجع null لو كان فاضي
                    

4. size() - حجم المكدس

يرجع عدد العناصر في المكدس.

int size();
// يرجع عدد العناصر
                    

5. isEmpty() - يفحص إذا كان فاضي

يتأكد إذا المكدس فيه عناصر أو لا.

boolean isEmpty();
// يرجع true لو المكدس فاضي
                    

واجهة المكدس في جافا

public interface Stack<E> {
    int size();
    boolean isEmpty();
    E top();
    void push(E element);
    E pop();
}
                

📊 مثال تطبيقي للعمليات

العملية	القيمة المُرجعة	محتويات المكدس	الحجم
push(5)	—	(5)	1
push(3)	—	(5, 3)	2
size()	2	(5, 3)	2
pop()	3	(5)	1
isEmpty()	false	(5)	1
pop()	5	()	0
isEmpty()	true	()	0
pop()	null	()	0
push(7)	—	(7)	1
push(9)	—	(7, 9)	2
top()	9	(7, 9)	2
push(4)	—	(7, 9, 4)	3
pop()	4	(7, 9)	2

💻 تنفيذ المكدس

تنفيذ المكدس باستخدام مصفوفة

الفكرة

طريقة بسيطة باستخدام مصفوفة بحيث:

العناصر تضاف من اليسار لليمين (في التخزين الفعلي).
متغير t يتبع فهرس القمة.
في البداية t = -1 (مافيه عناصر).

هيكل المكدس بالمصفوفة

t = 2 (مشير لـ 'ج' اللي في القمة)

الخوارزميات الرئيسية

خوارزمية size()

Algorithm size()
    return t + 1
// نضيف 1 لأن الفهرسة تبدأ من 0
                    

خوارزمية pop()

Algorithm pop()
    if isEmpty() then
        return null
    else
        t ← t − 1
        return S[t + 1]
// ننقص مؤشر القمة أولاً
// نرجع العنصر اللي كان في القمة
                    

خوارزمية push(o)

Algorithm push(o)
    if t = S.length − 1 then
        throw IllegalStateException
    else
        t ← t + 1
        S[t] ← o
// نتأكد إذا المصفوفة ممتلئة
// نزيد مؤشر القمة
// نخزن العنصر في القمة الجديدة
                    

التنفيذ بجافا

public class ArrayStack<E> implements Stack<E> {
    // متغيرات الكلاس
    private E[] S;                  // المصفوفة اللي تخزن البيانات
    private int top = -1;         // فهرس العنصر اللي في القمة
    
    // المُنشئ
    public ArrayStack(int capacity) {
        S = (E[]) new Object[capacity];
    }
    
    public E pop() {
        if (isEmpty())
            return null;
        E temp = S[top];
        S[top] = null;           // نساعد Garbage Collector
        top = top - 1;
        return temp;
    }
}
                

⚠️ حدود المكدس بالمصفوفة

حجم ثابت: لازم تحدّد السعة القصوى من بدري.
مساحة مهدرة: يمكن تخصص مساحة أكثر من اللي تحتاجها.
FullStackException: تطلع استثناء لو حاولت تضيف على مكدس ممتلئ.

🎯 تطبيقات المكدس

تطبيقات مباشرة

🌐 سجل متصفح الويب

زر الرجوع في المتصفح يستخدم مكدس لتتبع الصفحات اللي زرتها. آخر صفحة تكون في القمة!

↩️ عمليات التراجع (Undo)

برامج تحرير النصوص تستخدم مكدس عشان تطبق التراجع. كل تعديل ندفعه للمكدس، والتراجع يسوي pop لآخر تعديل.

☕ مكدس استدعاءات JVM

الجافا فيرتشوال ماشين تستخدم مكدس عشان تدير استدعاءات الدوال والرجوع منها.

🔄 تقييم التعابير الرياضية

تقييم التعابير الحسابية والتعامل مع أسبقية العمليات.

مثال: التحقق من تطابق الأقواس

المسألة: نفحص إذا الأقواس متزنة

كل قوس فتح "(", "{", "[" لازم يقابله قوس غلق ")", "}", "]"

التعبير	صحيح؟
( )(( )){([( )])}	✅ صحيح
((( )(( )){([( )])})	✅ صحيح
)(( )){([( )])}	❌ خطأ (يبدأ بقفل)
({[ ])}	❌ خطأ (غير متطابق)
(	❌ خطأ (ما انغلق)

// الخوارزمية: ندفع الأقواس المفتوحة، ونطبع مع قوس الغلق ونطابقه
public static boolean isMatched(String expression) {
    Stack<Character> buffer = new LinkedStack<>();
    
    for (char c : expression.toCharArray()) {
        if (opening.indexOf(c) != -1)    // قوس فتح
            buffer.push(c);
        else if (closing.indexOf(c) != -1) { // قوس غلق
            if (buffer.isEmpty())
                return false;           // مافيه شيء يطابقه
            if (closing.indexOf(c) != opening.indexOf(buffer.pop()))
                return false;           // غير متطابق
        }
    }
    return buffer.isEmpty();        // كل الأقواس تطابقت؟
}
                

تقييم التعبير الحسابي

مثال: 14 - 3 * 2 + 7

باستخدام أسبقية العمليات (الضرب قبل الجمع والطرح) والتقييم من اليسار لليمين:

نحسب: 3 * 2 = 6
نحسب: 14 - 6 = 8
نحسب: 8 + 7 = 15

النتيجة: 15

استخدام مكدسين:

opStk: يخزن العمليات (+ , - , * , /)
valStk: يخزن قيم المعاملات

الاستراتيجية: ندفع العملية، لكن أول شيء نطلع و ننفذ العمليات اللي لها أسبقية أعلى أو مساوية.

🚶 الطوابير - FIFO (أول من يدخل، أول من يخرج)

وش هو الطابور؟

الطابور (Queue) هو نوع بيانات مجرد (ADT) يخزن كائنات عشوائية ويشتغل بمبدأ أول من يدخل هو أول من يخرج (FIFO). زي صف الانتظار - أول واحد يجي هو أول واحد يخدم!

تصوير الطابور

→

الأمام (أ) ← → الخلف (د)

العنصر 'أ' دخل أول شي، فهو اللي يطلع أول شي.

                    🔑 الخصائص الأساسية:
                    ترتيب FIFO: أول عنصر تنزله هو أول عنصر تشيله.
وصول بنهايتين: الإدخال من الخلف، والحذف من الأمام.
معالجة عادلة: العناصر تُعالج حسب ترتيب وصولها.

                

⚙️ عمليات الطابور

العمليات الرئيسية

1. enqueue(object) - إضافة من الخلف

يضيف عنصر في آخر (خلف) الطابور.

void enqueue(E element);
// يحط العنصر في المؤخرة
// يحدّث الحجم
                    

2. dequeue() - حذف من الأمام

يحذف ويرجع العنصر اللي في مقدمة الطابور.

E dequeue();
// يشيل العنصر من المقدمة
// يرجع العنصر المحذوف
// يرجع null لو الطابور فاضي
                    

العمليات المساعدة

3. first() - يشوف المقدمة

يرجع العنصر اللي في المقدمة بدون ما يشيله.

E first();
// يرجع العنصر الأمامي بدون حذف
// يرجع null لو كان فاضي
                    

4. size() - حجم الطابور

int size();
// يرجع عدد العناصر
                    

5. isEmpty() - يفحص إذا كان فاضي

boolean isEmpty();
// يرجع true لو الطابور فاضي
                    

واجهة الطابور في جافا

public interface Queue<E> {
    int size();
    boolean isEmpty();
    E first();
    void enqueue(E element);
    E dequeue();
}
                

📊 مثال تطبيقي للعمليات

العملية	القيمة المُرجعة	محتويات الطابور	الحجم
enqueue(5)	—	(5)	1
enqueue(3)	—	(5, 3)	2
dequeue()	5	(3)	1
enqueue(7)	—	(3, 7)	2
dequeue()	3	(7)	1
first()	7	(7)	1
dequeue()	7	()	0
dequeue()	null	()	0
isEmpty()	true	()	0
enqueue(9)	—	(9)	1
enqueue(7)	—	(9, 7)	2
size()	2	(9, 7)	2
enqueue(3)	—	(9, 7, 3)	3
enqueue(5)	—	(9, 7, 3, 5)	4
dequeue()	9	(7, 3, 5)	3

💻 تنفيذ الطابور

طابور دائري باستخدام مصفوفة

الفكرة

يستخدم مصفوفة بحجم N بشكل دائري:

f = فهرس العنصر الأمامي.
sz = عدد العناصر المخزنة.
r = (f + sz) mod N = أول خانة فاضية بعد المؤخرة.

الوضع الطبيعي

الوضع بعد الالتفاف

الطابور يلف باستخدام حساب الموديولو.

الخوارزميات الرئيسية

خوارزمية enqueue(o)

Algorithm enqueue(o)
    if size() = N − 1 then
        throw IllegalStateException
    else
        r ← (f + sz) mod N
        Q[r] ← o
        sz ← sz + 1
// نحسب موقع المؤخرة باستخدام الموديولو
// نضيف في المؤخرة
// نزيد الحجم
                    

خوارزمية dequeue()

Algorithm dequeue()
    if isEmpty() then
        return null
    else
        o ← Q[f]
        f ← (f + 1) mod N
        sz ← sz − 1
        return o
// ناخذ العنصر الأمامي
// نحرك مؤشر الأمام (بشكل دائري)
// ننقص الحجم
                    

التنفيذ بجافا

public class ArrayQueue<E> implements Queue<E> {
    private E[] data;
    private int f = 0;              // فهرس المقدمة
    private int sz = 0;             // الحجم الحالي
    
    public ArrayQueue(int capacity) {
        data = (E[]) new Object[capacity];
    }
    
    public void enqueue(E e) throws IllegalStateException {
        if (sz == data.length)
            throw new IllegalStateException("الطابور ممتلئ");
        int avail = (f + sz) % data.length;
        data[avail] = e;
        sz++;
    }
    
    public E dequeue() {
        if (isEmpty())
            return null;
        E answer = data[f];
        data[f] = null;                // نساعد Garbage Collector
        f = (f + 1) % data.length;
        sz--;
        return answer;
    }
}
                

تطبيقات الطابور

📋 قوائم الانتظار

طوابير خدمة العملاء، طابور مهام الطباعة، جدولة المهام.

🖨️ مشاركة الموارد

طابور الطابعة، جدولة المعالج، الوصول المشترك للموارد.

🔄 جدولة Round Robin

أنظمة مشاركة الوقت العادلة، جدولة العمليات.

🌐 خوارزمية BFS

البحث أولاً بالعرض في الرسوم البيانية والأشجار.

جدولة Round Robin

توزيع عادل للموارد بالتكرير:

e = Q.dequeue() - نجيبي المهمة التالية.
خدمة العنصر e - ننفذ المهمة.
Q.enqueue(e) - نرجعه لآخر الطابور.

⚡ تحليل الأداء والتعقيد

أداء المكدس

العملية	بالمصفوفة	بالقائمة المترابطة
push()	O(1)	O(1)
pop()	O(1)	O(1)
top()	O(1)	O(1)
size()	O(1)	O(1)
isEmpty()	O(1)	O(1)
المساحة	O(N) - ثابتة	O(n) - ديناميكية

أداء الطابور

العملية	بالمصفوفة	بالقائمة المترابطة
enqueue()	O(1)	O(1)
dequeue()	O(1)	O(1)
first()	O(1)	O(1)
size()	O(1)	O(1)
isEmpty()	O(1)	O(1)
المساحة	O(N) - ثابتة	O(n) - ديناميكية

                    ✅ أهم النقاط:
                    كل العمليات الأساسية تشتغل ب وقت ثابت O(1).
بالمصفوفة: حجم ثابت، ممكن تهدر مساحة، وتطلع استثناء إذا امتلأت.
بالقائمة المترابطة: حجم ديناميكي، لكن تستهلك مساحة إضافية لكل عنصر.
تعقيد المساحة O(n) حيث n عدد العناصر.

                

مقارنة: المكدس vs الطابور

المكدس (LIFO)

الترتيب: آخر من يدخل أول من يخرج
الوصول: نهاية واحدة (القمة فقط)
العمليات: push, pop, top
الاستخدامات: تراجع، العودية، تحليل النصوص
تشبيه: رزمة أطباق

الطابور (FIFO)

الترتيب: أول من يدخل أول من يخرج
الوصول: نهايتين (أمام و خلف)
العمليات: enqueue, dequeue, first
الاستخدامات: جدولة، BFS، تخزين مؤقت
تشبيه: طابور الانتظار

📝 ملخص الدراسة

مفاهيم أساسية لازم تتذكرها

أساسيات المكدس:

مبدأ LIFO - آخر واحد يدخل هو أول واحد يخرج.
العمليات الرئيسية: push (إضافة), pop (حذف), top (اطلاع).
كل العمليات وقتها ثابت O(1).
التنفيذ بالمصفوفة يستخدم متغير فهرس للقمة.
يستخدم في: عمليات التراجع، تقييم التعابير، الخوارزميات العودية.

أساسيات الطابور:

مبدأ FIFO - أول واحد يدخل هو أول واحد يخرج.
العمليات الرئيسية: enqueue (إضافة من الخلف), dequeue (حذف من الأمام), first (اطلاع).
كل العمليات وقتها ثابت O(1).
التنفيذ بالمصفوفة يستخدم مخزن دائري مع حساب الموديولو.
يستخدم في: الجدولة، BFS، مشاركة الموارد، التخزين المؤقت.

🎓 نصائح للاختبار

افهم الفرق بين LIFO و FIFO زين.
تدرّب على تتبع عمليات push/pop و enqueue/dequeue.
احفظ تعقيد الوقت لجميع العمليات (O(1)).
افهم فكرة الطابور الدائري بالمصفوفة وكيف نستخدم modulo.
كن ملم بالتطبيقات العملية لكل هيكل.
تمرن على مسائل الأقواس المتطابقة وتقييم التعابير.
اعرف متى تستخدم المكدس ومتى تستخدم الطابور.