• 0
مصطفى 36a2

تعرف إلى 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- أن تسأل عن أمر غير متعلق بالموضوع ..

 

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

تم تعديل بواسطه مصطفى 36a2
5

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

5 إجابة على هذا السؤال .

  • 0

كيف يمكنك الاساءة الى المشاركة .. أن ترد بكلمة شكر فقط ..

 

شكرا أخي مصطفى على هذا الموضوع الرائع :D

+1

 

بالإضافة إلى ما ذكره الأخ مصطفى, يوجد مثال هنا قد يُفيد القارئ :

اختبر قدراتك في C/CPP - الحلقة الرابعة, الجزء الثالث

 

أيضا زيادة على stack و queue, توجد كذلك priority_queue. يمكنني توضيحها قليلا إن أردت :)

 

 

تحياتي.

تم تعديل بواسطه Snack3r
1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

موضوع  جميل  وشرح  واضح  جزاك الله  كل خير

 

و  عشان  ما اسيء للموضوع :P

 

هذا شرح  جميل لهياكل البيانات بس بالانجليزي اتمنى انه يفيد

 

http://www.cplusplus.com/doc/tutorial/structures/

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0
stack<T, Sequence>

الشىء الذي لم افهمه هو مادور sequence هنا ,

بالانجليزي يقلك هو : The type of the underlying container used to implement the stack  , والحالة الافتراضية له هي :

 	deque<T>

ياريت احد الاخوة يشرحلنا فائدة sequence

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

موضوع مفيد وسهل

وهذا من مزايا stl

يعني كلها متشابهة تقريبا list vector ....

شكرا لك اخي

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أخي فؤاد2008 .. أهلا بك

بالنسبة لسؤالك .. اقرأ النص التالي :

 


Stack is a container adaptor, meaning that it is implemented on top of some underlying container type. By default that underlying type is deque, but a different type may be selected explicitly.

المصدر

وهذا يعني أن طريقة تنفيذ المفهوم المجرّد لstack تتم عن طريق deque فهو في الحقيقة deque ولكننا نستخدم توابع إضافة العناصر وسحب العناصر من المقدّمة فقط ..

عند تغيير الsequence الذي ينفّذ implements المبدأ النظري في collection معينة .. فهذا يعني أننا سنستخدم توابع الإضافة والسحب الخاصة بهذا العنصر ..

 

لنفرض أن لديك كائنا a من نوع أنت أنشأته يحوي على التوابع التالية :

a.back() a.push_back(t) a.pop_back()

المصدر

عندها يمكنك استخدام هذا النوع كـSequence

 

بالتوفيق :)

تم تعديل بواسطه مصطفى 36a2
التنسيق
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .