مبادئ عمل المكدس
يعمل المكدس وفقًا لمبدأ LIFO. تصور كومة من الأطباق؛ أنت تضيف طبقًا فوق الآخر، وعندما تريد إزالة طبق، فإنك تزيل الطبق الموجود في الأعلى أولاً. هذا السلوك هو جوهر عمل المكدس في علوم الحاسوب.
هناك عمليتان أساسيتان يتم إجراؤهما على المكدس:
- الإضافة (Push): لإضافة عنصر جديد إلى أعلى المكدس.
- الحذف (Pop): لإزالة العنصر الموجود في أعلى المكدس.
بالإضافة إلى ذلك، هناك عمليات أخرى مفيدة، مثل:
- النظر (Peek): لعرض العنصر الموجود في أعلى المكدس دون إزالته.
- التحقق من الفراغ (IsEmpty): للتحقق مما إذا كان المكدس فارغًا.
- التحقق من الامتلاء (IsFull): للتحقق مما إذا كان المكدس ممتلئًا (اعتمادًا على التنفيذ).
تمثيلات المكدس
يمكن تنفيذ المكدس بعدة طرق، وأكثرها شيوعًا:
- باستخدام المصفوفات (Arrays): في هذا التنفيذ، يتم استخدام مصفوفة لتخزين عناصر المكدس. يتطلب هذا التنفيذ تخصيص مساحة تخزين ثابتة مسبقًا.
- باستخدام القوائم المترابطة (Linked Lists): في هذا التنفيذ، يتم استخدام قائمة مترابطة لتخزين عناصر المكدس. يسمح هذا التنفيذ بمكدسات ذات حجم ديناميكي، حيث يمكن للمكدس أن ينمو أو يتقلص حسب الحاجة.
استخدامات المكدس
للمكدس تطبيقات واسعة في علوم الحاسوب، بما في ذلك:
- إدارة الذاكرة: يستخدم المكدس في إدارة الذاكرة الخاصة بالبرامج، خاصة لتخزين متغيرات الدوال، وعناوين العودة، والمعلومات الأخرى المتعلقة باستدعاءات الدوال.
- تقييم التعبيرات (Expression Evaluation): يستخدم المكدس في تقييم التعبيرات الحسابية، وتحويل التعبيرات من الصورة الداخلية إلى الصورة اللاحقة (postfix).
- تراجع/إعادة (Undo/Redo): يمكن استخدام المكدس لتنفيذ وظائف التراجع والإعادة في التطبيقات، حيث يتم تخزين الحالات السابقة للعمليات في المكدس.
- خوارزميات البحث (Search Algorithms): تستخدم بعض خوارزميات البحث، مثل البحث بعرض الصفحة (Breadth-First Search – BFS) والبحث بالعمق أولاً (Depth-First Search – DFS)، هياكل بيانات المكدس أو قائمة الانتظار (Queue) لتحقيق وظائفها.
- معالجة اللغات (Language Processing): تستخدم المكدسات في معالجة اللغات، مثل تحليل بناء الجملة (syntax analysis) في المترجمات (compilers) والمفسرات (interpreters).
- الملاحة في المتصفحات (Browser Navigation): في متصفحات الويب، يتم استخدام المكدس لتتبع الصفحات التي تمت زيارتها، حيث يتم إرجاع المستخدم إلى الصفحات السابقة عن طريق النقر على زر “الرجوع”.
مثال على التنفيذ (بشكل عام)
لنأخذ مثالًا مبسطًا لتوضيح كيفية عمل المكدس. تخيل أن لدينا مكدسًا فارغًا. نقوم بـ “Push” بالأرقام 1، 2، و 3. الآن، المكدس يحتوي على العناصر [1, 2, 3]، حيث 3 هو العنصر الموجود في الأعلى. إذا قمنا بعملية “Pop”، فسنحصل على 3، والمكدس سيصبح [1, 2]. إذا قمنا بعملية “Peek”، فسنحصل على 2 دون إزالته من المكدس.
مثال بلغة بايثون (باستخدام قائمة):
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
else:
return None # Or raise an exception
def peek(self):
if not self.is_empty():
return self.items[-1]
else:
return None # Or raise an exception
def size(self):
return len(self.items)
مثال على الاستخدام:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(f"Size: {stack.size()}") # Output: 3
print(f"Popped: {stack.pop()}") # Output: 3
print(f"Peek: {stack.peek()}") # Output: 2
print(f"Size: {stack.size()}") # Output: 2
مقارنة المكدس بأنواع البيانات المجردة الأخرى
بالمقارنة مع أنواع البيانات المجردة الأخرى، مثل قوائم الانتظار (Queues)، يختلف المكدس في طريقة الوصول إلى البيانات. في قائمة الانتظار، يعمل مبدأ “الأول في الدخول، الأول في الخروج” (First In, First Out – FIFO)، على عكس LIFO في المكدس. هذه الاختلافات تجعل كل نوع بيانات مناسبًا لحالات استخدام مختلفة.
على سبيل المثال، قائمة الانتظار مناسبة لمهام مثل معالجة الطلبات بالتسلسل، بينما المكدس مثالي لتتبع استدعاءات الدوال أو تنفيذ وظائف التراجع.
مزايا وعيوب المكدس
المزايا:
- بساطة: المفهوم والعمليات الأساسية للمكدس بسيطة وسهلة الفهم والتنفيذ.
- الكفاءة: عمليات Push و Pop عادة ما تكون سريعة (O(1)) عند استخدام المصفوفات أو القوائم المترابطة.
- إدارة الذاكرة: في بعض الحالات، مثل إدارة ذاكرة البرنامج، يساعد المكدس على إدارة الذاكرة بكفاءة.
العيوب:
- الوصول المقيد: يمكن الوصول إلى العنصر الموجود في الأعلى فقط، مما يحد من المرونة في بعض الحالات.
- الحجم الثابت (في بعض التنفيذات): عند استخدام المصفوفات، قد يكون حجم المكدس ثابتًا، مما يتطلب تحديدًا مسبقًا لحجمه الأقصى.
- الفيضان والانهيار (Stack Overflow/Underflow): قد يحدث فيضان للمكدس (عند محاولة إضافة عنصر إلى مكدس ممتلئ) أو انهيار للمكدس (عند محاولة إزالة عنصر من مكدس فارغ).
خاتمة
المكدس هو نوع بيانات أساسي في علوم الحاسوب، يوفر طريقة فعالة لتخزين البيانات وتنظيمها بناءً على مبدأ LIFO. يجد المكدس تطبيقات واسعة في مجالات مختلفة مثل إدارة الذاكرة، وتقييم التعبيرات، وتنفيذ وظائف التراجع/الإعادة. على الرغم من بعض القيود، تظل بساطته وكفاءته تجعله أداة قيمة في تطوير البرمجيات.