شرح هيكل بيانات المكدس
المكدس (Stack) هو هيكل بيانات خطي يتبع مبدأ "آخر ما يدخل هو أول ما يخرج"، والذي يُعرف اختصاراً بـ LIFO. هذا يعني أن آخر عنصر يتم إضافته إلى المكدس هو أول عنصر يتم إزالته منه.
المكدسات بسيطة، لكنها مهمة جداً في علوم الحاسوب. تُستخدم في استدعاءات الدوال، وأنظمة التراجع (undo)، وسجل المتصفح، وتقييم التعبيرات، وتحليل الصيغة (syntax parsing)، والتراجع (backtracking)، والعديد من أنظمة البرامج الحقيقية.
مقدمة
تساعد هياكل البيانات المطورين على تنظيم وإدارة البيانات بكفاءة. المصفوفات (Arrays)، القوائم المرتبطة (Linked Lists)، الطوابير (Queues)، المكدسات (Stacks)، الأشجار (Trees)، الرسوم البيانية (Graphs)، وجداول التجزئة (Hash Tables) كلها تحل أنواعاً مختلفة من المشكلات.
المكدس هو أحد أبسط هياكل البيانات وأكثرها فائدة. يسهل فهمه لأنه يتصرف مثل كومة أطباق حقيقية. عندما تضيف طبقاً جديداً، تضعه في الأعلى. عندما تزيل طبقاً، فإنك تزيل الطبق العلوي أولاً.
هذا السلوك يظهر في العديد من مواقف البرمجة. كلما كان يجب معالجة العنصر الأحدث أولاً، غالباً ما يكون المكدس حلاً واضحاً وطبيعياً.
ما هو المكدس؟
المكدس هو مجموعة من العناصر حيث يتم الإدخال والإزالة من نفس الطرف. غالباً ما يسمى هذا الطرف بـ "قمة المكدس" (top of the stack).
يتبع المكدس قاعدة LIFO:
هذا يعني أن العنصر الذي تمت إضافته مؤخراً هو أول عنصر يتم إزالته.
الفكرة الرئيسية بسيطة:
إضافة عناصر جديدة إلى قمة المكدس.
إزالة العناصر من قمة المكدس.
النظر إلى العنصر العلوي دون إزالته عند الحاجة.
التحقق مما إذا كان المكدس فارغاً قبل إزالة أو قراءة العنصر العلوي.
لا يركز المكدس على الوصول العشوائي. هدفه الرئيسي هو التحكم في الوصول عبر القمة.
تشبيه واقعي للمكدس
مثال شائع في الحياة الواقعية للمكدس هو كومة من الأطباق.
تخيل أطباقاً موضوعة فوق بعضها البعض:
تم وضع الطبق A أولاً. تم وضع الطبق B بعده. تم وضع الطبق C أخيراً.
إذا احتجنا إلى إزالة طبق، فإننا نزيل الطبق C أولاً لأنه في الأعلى. هذا يتوافق مع مبدأ LIFO.
هذه الفكرة البسيطة هي بالضبط كيف يعمل المكدس في البرمجة.
مبدأ LIFO
LIFO تعني "آخر ما يدخل هو أول ما يخرج" (Last In, First Out). هذا يعني أن آخر عنصر تم إدخاله إلى المكدس هو أول عنصر يتم إخراجه منه.
على سبيل المثال، إذا قمنا بإضافة (push) القيم بهذا الترتيب:
سيبدو المكدس كالتالي:
إذا قمنا بإزالة (pop) عنصراً، فسيتم إزالة القيمة 30 أولاً لأنها في القمة.
هذا السلوك يختلف عن الطابور (Queue)، الذي يتبع مبدأ FIFO (First In, First Out) أو "أول ما يدخل هو أول ما يخرج".
عمليات المكدس الأساسية
عادةً ما يدعم المكدس مجموعة صغيرة من العمليات المهمة.
push: يضيف عنصراً إلى قمة المكدس.
pop: يزيل ويعيد العنصر العلوي.
peek: يعيد العنصر العلوي دون إزالته.
isEmpty: يتحقق مما إذا كان المكدس لا يحتوي على عناصر.
size: يعيد عدد العناصر في المكدس.
هذه العمليات كافية لحل العديد من المشكلات التي تتطلب معالجة أحدث البيانات أولاً.
عملية Push
عملية push تضيف عنصراً جديداً إلى قمة المكدس.
إذا كان المكدس فارغاً وقمنا بإضافة 10 (push(10))، يصبح المكدس:
إذا قمنا بإضافة 20 (push(20))، يصبح المكدس:
إذا قمنا بإضافة 30 (push(30))، يصبح المكدس:
يتم وضع كل عنصر جديد فوق العنصر العلوي السابق.
عملية Pop
عملية pop تزيل العنصر العلوي من المكدس وتعيده.
لنأخذ هذا المكدس في الاعتبار:
إذا استدعينا pop، فسيتم إزالة القيمة 30.
يصبح المكدس:
إذا استدعينا pop مرة أخرى، فسيتم إزالة القيمة 20.
يصبح المكدس:
يجب استخدام عملية pop بحذر عندما يكون المكدس فارغاً. الإزالة من مكدس فارغ تسمى عادة "فيضان سفلي للمكدس" (stack underflow).
عملية Peek
عملية peek تعيد العنصر العلوي دون إزالته.
لنأخذ هذا المكدس في الاعتبار:
إذا استدعينا peek، تكون النتيجة:
لكن المكدس يبقى دون تغيير:
عملية peek مفيدة عندما نحتاج إلى فحص العنصر التالي الذي سيتم إزالته، ولكننا لا نريد تعديل المكدس.
عملية isEmpty
عملية isEmpty تتحقق مما إذا كان المكدس يحتوي على أي عناصر.
إذا كان المكدس لا يحتوي على عناصر:
فإن isEmpty تعيد true.
إذا كان المكدس يحتوي على عناصر:
فإن isEmpty تعيد false.
هذه العملية مهمة قبل استدعاء pop أو peek لأن تلك العمليات تحتاج إلى وجود عنصر علوي.
مثال تشغيل يدوي
دعنا نجري سلسلة من عمليات المكدس يدوياً.
نبدأ بمكدس فارغ:
الخطوة 1: push(10)
نضيف 10 إلى قمة المكدس.
الخطوة 2: push(20)
نضيف 20 فوق 10.
الخطوة 3: push(30)
نضيف 30 فوق 20.
الخطوة 4: peek()
العنصر العلوي هو 30.
لا يتغير المكدس:
الخطوة 5: pop()
يتم إزالة العنصر العلوي 30.
يصبح المكدس:
الخطوة 6: push(40)
نضيف 40 إلى القمة.
الخطوة 7: pop()
يتم إزالة العنصر العلوي 40.
يصبح المكدس:
الخطوة 8: pop()
يتم إزالة العنصر العلوي 20.
يصبح المكدس:
يوضح هذا التشغيل اليدوي سلوك LIFO بوضوح. القيمة التي تم دفعها مؤخراً هي دائماً أول قيمة يتم إزالتها.
تنفيذ المكدس باستخدام مصفوفة
غالباً ما يتم تنفيذ المكدس باستخدام مصفوفة. في هذا التنفيذ، يمثل نهاية المصفوفة قمة المكدس.
على سبيل المثال:
القيمة 30 هي العنصر العلوي لأنها في نهاية المصفوفة.
يعد استخدام نهاية المصفوفة فعالاً لأن العديد من لغات البرمجة يمكنها إضافة وإزالة العناصر من النهاية بسرعة.
شبه كود للمكدس
يُظهر هذا شبه الكود السلوك الرئيسي للمكدس دون الاعتماد على لغة برمجة معينة.
مثال المكدس في PHP
إليك تنفيذ نظيف للمكدس في PHP باستخدام مصفوفة:
يحمي هذا التنفيذ المكدس من العمليات غير الصالحة عن طريق رمي استثناء (exception) عند استدعاء pop أو peek على مكدس فارغ.
مثال المكدس في JavaScript
إليك تنفيذ المكدس في JavaScript:
يتبع التنفيذ في JavaScript نفس منطق إصدار PHP. المصفوفة الداخلية تخزن القيم، وقمة المكدس هي نهاية المصفوفة.
تنفيذ المكدس باستخدام قائمة مرتبطة
يمكن أيضاً تنفيذ المكدس باستخدام قائمة مرتبطة (Linked List). في هذا الإصدار، يمثل رأس القائمة المرتبطة قمة المكدس.
عندما نقوم بعملية push لقيمة، نقوم بإدراج عقدة جديدة في البداية. عندما نقوم بعملية pop، نقوم بإزالة العقدة الأولى.
هذا التنفيذ مفيد عندما نريد سلوك ذاكرة ديناميكي قائم على العقد.
مثال قائمة مرتبطة للمكدس في JavaScript
في هذا الإصدار، تعمل عمليتا push و pop عند رأس القائمة المرتبطة، لذا فهما فعالتان.
مكدس المصفوفة مقابل مكدس القائمة المرتبطة
يمكن استخدام كل من المصفوفات والقوائم المرتبطة لتنفيذ المكدس.
يكون مكدس المصفوفة أبسط عادةً ويعمل بشكل جيد في معظم لغات البرمجة عالية المستوى. يكون مكدس القائمة المرتبطة مفيداً عند تعلم الهياكل القائمة على العقد أو عندما يكون سلوك الذاكرة الديناميكي مهماً.
الاختلافات الرئيسية تشمل:
مكدس المصفوفة أسهل في التنفيذ.
مكدس القائمة المرتبطة يستخدم العقد والإشارات.
قد يقوم مكدس المصفوفة بإعادة التحجيم داخلياً من حين لآخر.
مكدس القائمة المرتبطة يخصص الذاكرة عقدة بعقدة.
كلاهما يمكن أن يدعم push و pop في زمن O(1).
بالنسبة لمعظم الأمثلة العملية في JavaScript و PHP، فإن مكدس المصفوفة واضح وكافٍ.
التعقيد الزمني لعمليات المكدس
يصف التعقيد الزمني كيف ينمو وقت تشغيل العملية مع زيادة عدد العناصر.
بالنسبة للمكدس القياسي، عادةً ما يكون للعمليات الرئيسية التعقيدات التالية:
push: O(1)
pop: O(1)
peek: O(1)
isEmpty: O(1)
size: O(1)
search: O(n)
عمليات push و pop و peek هي عمليات ذات وقت ثابت لأنها تعمل مباشرة مع قمة المكدس.
لماذا Push هي O(1)
عملية push تضيف عنصراً جديداً إلى قمة المكدس. لا تحتاج إلى فحص جميع العناصر.
على سبيل المثال:
فقط القمة تتغير، لذا فإن العملية تستغرق وقتاً ثابتاً:
لماذا Pop هي O(1)
عملية pop تزيل العنصر العلوي. لا تحتاج إلى البحث عن العنصر لأن القمة معروفة بالفعل.
يتم إزالة أو تحديث القمة فقط، لذا فإن العملية تستغرق وقتاً ثابتاً:
لماذا Search هي O(n)
البحث داخل المكدس ليس عملية مكدس قياسية لأن المكدسات مصممة للوصول إلى العنصر العلوي فقط.
إذا احتجنا إلى البحث عن قيمة، فقد نحتاج إلى فحص العناصر واحداً تلو الآخر.
للبحث عن 10، قد يحتاج الخوارزمية إلى التحقق من 30، ثم 20، ثم 10. في أسوأ الحالات، تفحص جميع العناصر.
لذلك، فإن البحث هو:
التعقيد المكاني للمكدس
التعقيد المكاني للمكدس هو O(n)، حيث n هو عدد العناصر المخزنة في المكدس.
كل عنصر يتم دفعه يتطلب ذاكرة. إذا كان المكدس يحتوي على 100 قيمة، فإنه يخزن 100 قيمة. إذا كان يحتوي على 1000 قيمة، فإنه يخزن 1000 قيمة.
عادةً ما تستخدم العمليات نفسها قدراً قليلاً فقط من الذاكرة الإضافية، ولكن هيكل البيانات يخزن n عنصراً.
فيضان المكدس (Stack Overflow) وفيضان المكدس السفلي (Stack Underflow)
هناك خطأان مهمان متعلقان بالمكدس هما فيضان المكدس (stack overflow) وفيضان المكدس السفلي (stack underflow).
فيضان المكدس (Stack overflow): يحدث عندما يحاول مكدس النمو بما يتجاوز حد الذاكرة المسموح به. يمكن أن يحدث هذا في المكدسات ذات الحجم الثابت منخفض المستوى أو مع الكثير من استدعاءات الدوال العودية.
فيضان المكدس السفلي (Stack underflow): يحدث عندما يحاول برنامج إجراء عملية pop أو peek على مكدس فارغ.
يجب أن تتعامل تطبيقات المكدس الجيدة مع الفيضان السفلي بأمان عن طريق إعادة قيمة null، أو إعادة قيمة خطأ، أو رمي استثناء.
المكدسات واستدعاءات الدوال
أحد أهم الاستخدامات الحقيقية للمكدس هو إدارة استدعاءات الدوال. تستخدم لغات البرمجة مكدس الاستدعاء (call stack) لتذكر استدعاءات الدوال النشطة.
عند استدعاء دالة، يتم دفع إطار مكدس جديد (stack frame) إلى مكدس الاستدعاء. عندما تنتهي الدالة، يتم إخراج إطار المكدس الخاص بها.
قد يبدو مكدس الاستدعاء كالتالي:
عندما تنتهي validateInput()، يتم إخراجها أولاً. ثم يستمر login(). هذا يتبع LIFO.
المكدسات والتكرار (Recursion)
يعتمد التكرار بشكل كبير على مكدس الاستدعاء. كل استدعاء تكراري يضيف إطار دالة جديد إلى المكدس.
على سبيل المثال، دالة حساب المضروب التكراري تنشئ استدعاءات متعددة:
يجب أن ينتهي الاستدعاء الأخير أولاً، ثم تعود السيطرة إلى الاستدعاءات السابقة.
لهذا السبب يمكن أن يسبب التكرار فيضان المكدس إذا أصبح عمق التكرار كبيراً جداً.
المكدسات وأنظمة التراجع (Undo)
تُستخدم المكدسات بشكل شائع لتنفيذ سلوك التراجع (undo).
تخيل محرراً للنصوص حيث يقوم المستخدم بتنفيذ الإجراءات التالية:
يمكن دفع كل إجراء إلى مكدس تراجع (undo stack):
عندما يضغط المستخدم على "تراجع" (undo)، يتم عكس الإجراء الأحدث أولاً. هذا هو بالضبط سلوك LIFO.
المكدسات وسجل المتصفح
يمكن أيضاً فهم سجل المتصفح باستخدام المكدسات.
عندما يزور المستخدم الصفحات:
يجب أن يعيد زر "رجوع" (back button) إلى الصفحة السابقة التي تمت زيارتها مؤخراً.
عندما يعود المستخدم للخلف، يتم إزالة "اتصل بنا" أولاً، ثم يصبح "المدونة" هو الصفحة السابقة الحالية.
المكدسات وتقييم التعبيرات
تُستخدم المكدسات في تقييم التعبيرات الرياضية والتحقق من الصيغة (syntax).
على سبيل المثال، عند التحقق من الأقواس المتوازنة:
يقوم الخوارزمية بدفع الأقواس المفتوحة إلى المكدس وإزالتها عند ظهور الأقواس المغلقة المطابقة.
إذا كان لكل قوس مفتوح قوس مغلق مطابق بالترتيب الصحيح، فسيتم موازنة التعبير.
مثال الأقواس المتوازنة
دعنا نتحقق من هذا التعبير:
العملية هي:
في النهاية، يكون المكدس فارغاً، لذا فإن الأقواس متوازنة.
إذا كان التعبير هو:
فلن يتطابق القوس المغلق مع أحدث قوس مفتوح، وبالتالي سيكون التعبير غير صالح.
الأقواس المتوازنة في JavaScript
هذه مشكلة مكدس كلاسيكية لأن أحدث قوس مفتوح يجب إغلاقه أولاً.
مثال عملي: مكدس التراجع في JavaScript
إليك مثال بسيط لمكدس تراجع:
أحدث إجراء يتم التراجع عنه دائماً أولاً.
متى يجب على المطورين استخدام المكدس؟
يجب على المطورين استخدام المكدس عندما يجب معالجة العنصر الأحدث أولاً.
المكدسات مفيدة عندما:
يلزم سلوك التراجع (undo).
يلزم التراجع (backtracking).
تكون استدعاءات الدوال أو التكرار متضمنة.
يلزم تحليل الصيغة (syntax parsing).
يلزم تقييم التعبيرات.
يلزم سلوك يشبه سجل المتصفح.
يلزم تنفيذ البحث بعمق أول (Depth-first search) بشكل تكراري.
الإشارة الرئيسية هي سلوك LIFO. إذا كان يجب معالجة أحدث عنصر أولاً، فقد يكون المكدس هو الهيكل المناسب.
متى لا يجب استخدام المكدس
المكدس ليس الهيكل المناسب عندما تحتاج العناصر إلى المعالجة بنفس الترتيب الذي تمت إضافتها به.
يجب على المطورين تجنب المكدس عندما:
يلزم سلوك "أول ما يدخل هو أول ما يخرج" (FIFO).
يلزم الوصول العشوائي السريع حسب الفهرس.
يلزم البحث عن العناصر بشكل متكرر.
يلزم المعالجة القائمة على الأولوية.
يجب معالجة أقدم عنصر أولاً.
في تلك الحالات، قد تكون الطوابير (Queue) أو المصفوفات (Array) أو جداول التجزئة (Hash Table) أو الطوابير ذات الأولوية (Priority Queue) أكثر ملاءمة.
المكدس مقابل الطابور
المكدسات والطوابير كلاهما هياكل بيانات خطية، لكنهما يتبعان قواعد مختلفة.
يتبع المكدس LIFO:
يتبع الطابور FIFO:
على سبيل المثال، المكدس يشبه كومة أطباق. آخر طبق يتم إضافته هو أول طبق يتم إزالته.
الطابور يشبه خط أشخاص ينتظرون الخدمة. أول شخص يدخل الخط يتم خدمته أولاً.
الاختلافات الرئيسية تشمل:
المكدس يزيل أحدث عنصر أولاً.
الطابور يزيل أقدم عنصر أولاً.
يستخدم المكدس push و pop.
يستخدم الطابور enqueue و dequeue.
المكدس مفيد للتراجع (undo) والتراجع (backtracking).
الطابور مفيد للجدولة وخطوط الانتظار.
الأخطاء الشائعة عند تعلم المكدسات
غالباً ما يفهم المبتدئون الفكرة الأساسية للمكدس، لكنهم قد يرتكبون أخطاء في التنفيذ.
الأخطاء الشائعة تشمل:
الخلط بين المكدس والطابور.
الإزالة من نهاية خاطئة للمصفوفة.
نسيان معالجة حالات المكدس الفارغ.
استخدام المكدس عندما يلزم الوصول العشوائي.
افتراض أن البحث هو O(1).
تجاهل فيضان المكدس في الحلول التكرارية.
تغيير المكدس عندما يلزم peek فقط.
القاعدة الأكثر أماناً بسيطة: يجب الوصول إلى العنصر العلوي فقط بشكل مباشر.
قائمة تدقيق عملية لفهم المكدسات
قبل الانتقال إلى الطوابير (Queues) أو الأشجار (Trees) أو الرسوم البيانية (Graphs) أو الخوارزميات المتقدمة، يجب أن يكون المطورون قادرين على الإجابة على هذه الأسئلة:
ماذا يعني LIFO؟
ما هي قمة المكدس؟
ماذا تفعل عملية push؟
ماذا تفعل عملية pop؟
ماذا تفعل عملية peek؟
لماذا push و pop هما O(1)؟
ما هو فيضان المكدس السفلي (stack underflow)؟
كيف تُستخدم المكدسات في استدعاءات الدوال؟
لماذا المكدسات مفيدة لأنظمة التراجع (undo)؟
ما الفرق بين المكدس والطابور؟
إذا كانت هذه الأسئلة واضحة، فإن المطور يفهم المنطق الحقيقي وراء المكدسات.
مزايا المكدسات
للمكدسات عدة مزايا.
سهلة الفهم.
سهلة التنفيذ.
عمليات push و pop هي O(1).
تدعم بشكل طبيعي سلوك LIFO.
مفيدة للتراجع (undo) والتكرار (recursion) والتحليل (parsing) والتراجع (backtracking).
يمكن تنفيذها باستخدام المصفوفات أو القوائم المرتبطة.
هذه المزايا تجعل المكدسات واحدة من أهم هياكل البيانات للمبتدئين والمحترفين.
عيوب المكدسات
للمكدسات أيضاً قيود.
لا توفر وصولاً عشوائياً سريعاً.
ليست مناسبة لسلوك FIFO.
البحث داخل المكدس هو O(n).
يمكن أن تسبب فيضان المكدس (overflow) إذا تم الوصول إلى حدود الذاكرة.
إنها مقيدة لأن العنصر العلوي فقط يمكن الوصول إليه مباشرة.
هذه القيود ليست مشكلات عندما يتم استخدام المكدس للغرض الصحيح. إنها ببساطة تحدد متى قد يكون هيكل بيانات آخر أفضل.
المكدسات في مشاريع البرمجيات الحقيقية
تظهر المكدسات في مشاريع البرمجيات الحقيقية بأشكال عديدة، حتى عندما لا ينشئ المطورون فئة مكدس يدوياً.
الاستخدامات الشائعة في العالم الحقيقي تشمل:
إدارة مكدس الاستدعاء في لغات البرمجة.
ميزات التراجع والإعادة (undo/redo) في المحررات.
التنقل للخلف في المتصفحات.
تحليل الصيغة (syntax parsing) في المترجمات (compilers).
تقييم التعبيرات في الآلات الحاسبة.
خوارزميات التراجع (backtracking algorithms).
البحث بعمق أول (Depth-first search) في الرسوم البيانية.
سجل التوجيه (routing history) في التطبيقات.
فهم المكدسات يساعد المطورين على فهم كيفية عمل هذه الأنظمة داخلياً.
خاتمة
المكدس هو هيكل بيانات خطي يتبع مبدأ "آخر ما يدخل هو أول ما يخرج". آخر عنصر يتم إضافته إلى المكدس هو أول عنصر يتم إزالته.
عمليات المكدس الرئيسية هي push و pop و peek و isEmpty و size. Push تضيف عنصراً إلى القمة، pop تزيل العنصر العلوي، و peek تقرأ العنصر العلوي دون إزالته.
توفر المكدسات عادةً تعقيداً زمنياً O(1) لعمليات push و pop و peek و isEmpty و size. يستغرق البحث داخل المكدس O(n) لأن الهيكل غير مصمم للوصول العشوائي.
يمكن تنفيذ المكدسات باستخدام المصفوفات أو القوائم المرتبطة. تُستخدم في استدعاءات الدوال، والتكرار، وأنظمة التراجع، وسجل المتصفح، وتقييم التعبيرات، والتحقق من الصيغة، والتراجع.
بالنسبة للمطورين الذين يتعلمون هياكل البيانات والخوارزميات، فإن المكدسات ضرورية. إنها تعلم الوصول المتحكم فيه، وسلوك LIFO، والتفكير في الذاكرة، والأساس للعديد من التقنيات الخوارزمية المستخدمة في أنظمة البرمجيات الحقيقية.
