LIFO (Last In, First Out)
كيف يعمل المكدس؟
تخيل كومة من الصحون. يمكنك فقط إضافة صحن جديد في الأعلى (Top)، ويمكنك فقط سحب الصحن الموجود في الأعلى.
push(x): إضافة عنصر للقمة.pop(): إزالة العنصر من القمة.peek()/top(): رؤية القمة دون إزالة.
Top of Stack ↑
Implementation Strategies
Array Implementation
نستخدم مصفوفة ومتغير topOfStack يشير لآخر عنصر.
array[++top] = x;
// Pop
return array[top--];
مشكلة: الحجم ثابت (قد يمتلئ Stack Overflow).
Linked List Implementation
الإضافة والحذف تتم دائماً من رأس القائمة (Head).
newNode.next = head;
head = newNode;
// Pop (Delete First)
head = head.next;
ميزة: حجم ديناميكي (لا يمتلئ إلا بامتلاء الذاكرة).
Applications of Stack
1. Balancing Symbols (موازنة الأقواس)
للتأكد من صحة الكود: ( ( ) [ ] ).
عند فتح قوس (، نعمـل Push.
عند إغلاق قوس )، نعمل Pop ونتأكد من التطابق.
في النهاية يجب أن يكون المكدس فارغاً.
2. Postfix Expression Evaluation
لحساب:
6 5 2 3 + 8 * + 3 + *
الأرقام: Push. العمليات (+، *): Pop رقمين، احسب، ثم Push النتيجة.
هذا أسهل للكمبيوتر من التدوين العادي (Infix) لأنه لا يحتاج أقواس أو أولويات.
3. Method Calls (استدعاء الدوال)
عند استدعاء دالة، يتم تخزين متغيراتها المحلية وعنوان العودة في المكدس.
عند الانتهاء (return)، يتم إزالتها (Pop) للعودة للدالة السابقة.
هذا يفسر خطأ StackOverflowError عند التكرار اللانهائي (Recursion).
Pop on Empty Stack
ماذا يحدث إذا استدعينا pop() والمكدس فارغ؟
يحدث خطأ Underflow (أو يرمي Exception).
يجب دائماً التحقق بـ isEmpty() قبل الحذف.
Postfix Tracing
Exp: 1 2 + 3 *
1. Push 1, Push 2 [Stack: 1, 2]
2. Op +: Pop 2, Pop 1 -> 1+2=3 -> Push 3 [Stack: 3]
3. Push 3 [Stack: 3, 3]
4. Op *: Pop 3, Pop 3 -> 3*3=9 -> Push 9
Result: 9