علوم الحاسوب — هياكل البيانات: المكدسات والطوابير

المكدسات والطوابير في هياكل البيانات

تعتبر المكدسات (Stacks) والطوابير (Queues) من اهم هياكل البيانات الاساسية في علوم الحاسوب. تستخدم هاتان الهيكلتان في تنظيم وتخزين البيانات بطرق محددة تسهل عمليات المعالجة والوصول.

المكدس (Stack)

المكدس هو هيكل بيانات يتبع مبدأ “آخر ما يدخل هو اول ما يخرج” (Last In First Out – LIFO). يمكن تشبيهه بمجموعة من الاطباق المكدسة، حيث لا يمكن الوصول الى الطبق السفلي قبل رفع الاطباق التي فوقه.

العمليات الاساسية على المكدس:
– Push: اضافة عنصر الى اعلى المكدس
– Pop: ازالة العنصر العلوي من المكدس
– Peek/Top: الاطلاع على العنصر العلوي دون ازالته
– isEmpty: التحقق مما اذا كان المكدس فارغا

مثال على المكدس

تطبيق المكدس في تقييم التعبيرات الرياضية: عند تحويل تعبير من الصيغة العادية (Infix) الى الصيغة البولندية العكسية (Postfix) والتقييم، وفي وظيفة التراجع (Undo) في برامج تحرير النصوص.

الطابور (Queue)

الطابور هو هيكل بيانات يتبع مبدأ “اول ما يدخل هو اول ما يخرج” (First In First Out – FIFO). يشبه طابور الانتظار في الحياة اليومية، حيث يخدم اول شخص يصل اولا.

العمليات الاساسية على الطابور:
– Enqueue: اضافة عنصر الى نهاية الطابور
– Dequeue: ازالة عنصر من بداية الطابور
– Front: الاطلاع على اول عنصر دون ازالته
– isEmpty: التحقق مما اذا كان الطابور فارغا

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

تستخدم الطوابير في نظم التشغيل (جدولة العمليات)، ومعالجة الطلبات في خوادم الويب، وفي خوارزميات البحث في العرض اولا (BFS).

تحليل التعقيد

جميع العمليات الاساسية على المكدس والطابور (باستخدام مصفوفة او قائمة مرتبطة) تتم بزمن ثابت O(1). لمزيد من المعلومات، راجع درس الخوارزميات المتقدمة: المصفوفات والدوال ودرس الخوارزميات في الرياضيات.