تعرف إلى std::stack

السلام عليكم ورحمة الله وبركاته

بنى المعطيات Data Structures هي طرق مجرّدة لحفظ البيانات أو الكائنات ..
وأقصد بعبارة "طرق مجرّدة" أنها لا تحتاج إلى حاسوب مثلا لتكون موجوده .. كما أن الرياضيات هي أفكار مجرّدة والأرقام هي مفاهيم مجرّدة ..
سنتحدث اليوم بإذن الله عن المكدّس Stack ..

ولنبدأ بفكرته المجرّدة ..

بعد وجبة دسمة ستذهب حضرتك لترتاح أو لتتابع العمل على مشروعك .. :)
ولكن هناك من سيتحمّل عبء تنظيف الصحون !

في مرحلة معينة من تنظيف الصحون سيحدث ما يلي :
نقوم لتنظيف الصحن ثم نضعه جانباً .. بشكل أفقي /_____\
ثم نقوم بتنظيف صحن آخر ونعضع فوق الصحن الأول /====\
وهكذا سنضع صحنا فوق آخر .. في شكل رياضي مجرّد اسمه( المكدّس ) حيث تتكدّس العناصر فوق بعضها ..

والآن :

نريد اعادة ترتيب الصحون .. ونظريّا يستحيل أن نسحب الصحن في الأسفل فهذا سيؤدي إلى انهيار المكدس ..
ولذلك نقوم بسحب الصحن على السطح أولاً .. ثم الذي يليه ثم الذي يليه .. حتى نصل إلى الصحن في الأسفل ..
ما الذي حدث الآن ؟ أول صحن وضعناه (نسمي عملية الوضع  بـالدفع push ) هو آخر صحن سحبناه (نسمي عملية السحب بالإخراج pop )
وهذا ما نسمّيه (أول عنصر يدخل هو آخر عنصر يخرج .. وبالتالي : آخر عنصر يدخل هو أول عنصر يخرج )
إذا نطلق على المكدّس لقب LIFO أي Last in First Out وهذا هو التعريف الرياضي له ..
إذاً : المكدّس هو حاوية آخر ما يدخل إليها هو أول ما يخرج ..
أما الحاوية التي صفتها : أول من يدخل هو أول من يخرج فتسمّى : الطابور Queue ولن نتطرق اليها اليوم .

لنتكلّم الآن عن بعض العمليات التي يمكننا القيام بها في المكدس ( لانزال نعالج الفكرة المجرّدة ..بدون أي برمجة أو تطبيق عملي )
1- يمكننا الدفع بعنصر داخل المكدس Push
2- يمكننا إخراج عنصر من المكدس Pop
3- العنصر الوحيد الذي يمكننا رؤيته هو الذي على السطح .. وبالتالي يمكننا معرفة العنصر على السطح .. ولنسمّ العملية هذه top
4- يمكننا معرفة ما إذا كان المكدّس خالياً تماماً ... empty
5- بقي أخيراً أنه بالإمكان أن نعد عدد العناصر في المكدس .. size ( مثلاً ان تعد الصحون المتكدسة فوق بعضها )

هذا ينطبق على أي مكدّس مهما اختلفت الروايات :)

والآن لنبدأ بالتطبيق العملي ..
إنه لمن الممتع أن تكتب الكود بنفسك فستطبق بذلك ما تعلمته عن المكدس برمجياً وهذا أمر في غاية المتعة ..
وأنصحك بالقيام بهذه الخطوة لوحدك :)

ولكننا سنتعرف هنا على النوع stack والموجود ضمن المكتبة stack ضمن نطاق الأسماء std في ++C وسنتعامل مع توابعه الجاهزة والمحكمة البناء :)
بعد تضمين المكتبة stack

#include<stack>

واستخدام stack من مساحة الأسماء std

using std::stack;

نقوم بتعريف stack في البرنامج كما يلي :

stack <int>M;//stack <any type or class>M;

لاحظ أن المكدس هو قالب template مما يسمح لنا بإنشاء مكدسات لأي نوع أو صف ... (نكتب اسم النوع بين <> )

لنتعرف على التوابع الموجودة في الكائن من نوع stack
أولا الدفع push وهو يأخذ وسيطا من النوع الذي قمنا باستخدامه في القالب (وهو في المثال int)
ويعيد void

for(int i=0;i<10;i++)M.push(i);

ثانيا الاستخراج pop وهو يزيل العنصر الذي على السطح .. ويعيد void "انتبه" pop لايعيد العنصر المزال ..

M.pop();M.pop();

ملاحظة هامة : لو قمنا بعمل pop للكدس وهو فارغ أصلا سيتوقف البرنامج عن العمل .
ولذلك علينا معرفة :  هل المكدس فارغ أم لا ؟ عندما نستخدم pop وذلك باستخدام empty الذي يعيد 0 أو 1 حسب الحالة كما يلي :

if(!M.empty())    M.pop();

ثالثا  معرفة العنصر الذي على السطح باستخدام top والذي يعيد مرجعا ثابتا لأول عنصر ( أي انه لا يمكن تعديل العنصر )

std::cout<<M.top()<<std::endl;

أخيراً يمكننا معرفة حجم المكدّس بالتابع size

std::cout<<M.size()<<std::endl;

من أشهر الحلقات المستخدمة مع المكدّس هي الحلقة من الشكل التالي :

for(;!M.empty();M.pop())function(M.top);

أي أننا نستخرج عناصر المكدس واحدا واحدا حتى يفرغ .. ونطبق التابع function أياً يكن ... على كل عنصر نمر عليه

فيما يلي مثال يوضح العمليات السابقة .. سندخل نصوصاً في المكدس ثم سنستخرجها ونطبعها ..

#include <iostream>
#include <stack>
#include <string>
using std::string;
using std::stack;

using std::cin;
using std::cout;
using std::endl;

int main(int argc,char**argv)
{
    stack<string> x;
    string y;
    cout<<"Enter String !"<<endl;
    cin>>y;
    while(y.compare("end"))
    {
        x.push(y);
        cin>>y;
    }
    cout<<"size="<<x.size()<<endl;
    for(;!x.empty();x.pop())
        cout<<x.top()<<endl;
    return EXIT_SUCCESS;
}

البرنامج السابق يحفظ النصوص في مكدّس حتى ندخل end ثم يقوم بطباعتها بعكس الترتيب المدخل (لأن المكدس هو LIFO )
يمكنك الآن استعمال المكدس المعرف في المكتبة stack  دون ان تضطر لاعاداة كتابة كل شيء بنفسك (لتسريع الانجاز وتخفيض الاخطاء )

بالتوفيق :)

كيف يمكنك اغناء المشاركة ...
1- يمكنك كتابة برنامج يوضح استخدام المكدّس مع الكائنات المنشأة من صف ما .. أنشئ صفا بسيطا وكائنات منه ثم ضعها في مكدس ..
2- يمكنك كتابة مثال آخر على استخدام الدالة باستخدام الأنواع البسيطة .
3- يمكنك تقديم روابط تشرح stack من مصادر أخرى .. بشكل أفضل  .. وهنا أرغب بذكر المرجع الرائع مقالات الأخ Snack3r وهذا مقاله عن المكدسات
4- يمكنك كتابة موضوع عن استخدام هياكل بيانات أخرى مثل Tree  مثلاً

كيف يمكنك الاساءة الى المشاركة ..
1-أن ترد بكلمة شكر فقط ..
2- أن تسأل عن أمر غير متعلق بالموضوع ..

والسلام عليكم ورحمة الله وبركاته