هيكلة البيانات بواسطة Stack

مفهوم المكدس Stack:

تعني المكدس، والتي يمكننا أن نقوم بإنشائها عن طريق المصفوفات، هو أحد أهم هياكل البيانات في علم الحاسوب، ويتبع ترتيبًا معينًا في تنفيذ العمليات، يُطلق على الـ (Stack) بمجموعة (LIFO) وهي اختصار لـ (Last in, first out) أي ما يرد أخيرًا يصرف أولاً، هذا يعني أن آخر شيء أضفناه (pushed)، وهو أول شيء يتم سحبه (popped).

لفهم كيفية عمل الـ (Stack)، فكر في مجموعة من أوراق اللعب مقلوبة، يمكننا الوصول إلى البطاقة الموجودة في الأعلى فقط. عندما نريد إلقاء نظرة على البطاقة العلوية، فإن هناك شيئان يمكننا القيام بهما: يمكننا إلقاء نظرة خاطفة عليها وتركها في مكانها، أو يمكننا إخراجها. أيضاً إذا كانت البطاقة الأخيرة التي وضعناها على مجموعة البطاقات لدينا هي (بستوني أسود من فئة 10)، فإن البطاقة الأولى التي سنسحبها من الأعلى ستكون نفسها (بستوني اسود من فئة 10).

عمليات الأساسية على الـ Stack:

• ()Push: إضافة عنصر في الـ (Stack). لكن إذا كان الـ (Stack) ممتلئًا، فأنه يتم طباعة (Overflow) أي تجاوز للسعة.

• ()Pop: إزالة عنصر من الـ (Stack). تُزال العناصر بالترتيب الذي يتم إدخالها به. إذا كانت الـ (Stack) فارغاً، فأنه يتم طباعة (Underflow) أي لم يتجاوز السعة.

• ()Peek() or Top: إرجاع العنصر العلوي من الـ (Stack).

• ()isEmpty: إرجاع (true) إذا كان الـ (Stack) فارغًا ، وإلا فانه يُرجع (false).

ما هو التعقيد الوقت time complexity ل stack؟

()push  و()pop  و()isEmpty  و()top كلها تستغرق وقتًا (O(1. لأننا لا نقوم بتشغيل أي (loop) في أي من هذه العمليات.

تطبيقات على الـ Stack:

عكس الـ (string): يتم استخدام المكدس لعكس (string). ندفع أحرف (string) واحدًا تلو الآخر في الـ(Stack) ثم نخرج الحرف.

الإعراب النحوي: يستخدم العديد من الـ (compilers) الـ (Stack) لتحليل بناء جملة التعبيرات وما إلى ذلك قبل الترجمة إلى رمز منخفض المستوى.

فحص الأقواس: يستخدم الـ (Stack) للتحقق من فتح وإغلاق الأقواس بشكل صحيح.

التراجع: افترض أننا نجد طريقًا لحل مشكلة المتاهة. نختار طريقًا وبعد اتباعه ندرك أنه خطأ. نحتاج الآن إلى العودة إلى بداية المسار لنبدأ بمسار جديد. يمكن القيام بذلك بمساعدة الـ (Stack).

استدعاء الوظيفة (function): يُستخدم الـ (Stack) للاحتفاظ بالمعلومات حول الوظائف النشطة أو الإجراءات الفرعية.