هياكل البيانات في لغة C - الجزء الثالث

[ahmed.o.mohamed 931]

مرحبا بكم إخوتي الكرام في هذه السلسلة المتعلقة بهياكل البيانات في لغة C.

كنا قد تحدثنا في الجزء الأول من هذه السلسلة عن القوائم المتصلة البسيطة و تحدثنا في الجزء الثاني عن القوائم المزدوجة و يسرني أن أبدأ معكم في شرح الجزء الثالث و الذي يتعلق بالمكدسات (Stacks).

الفهرس

1. تعريف
   
2. المحاكاة باستخدام المصفوفات
   
3. المحاكاة باستخدام القوائم البسيطة
   
4. المحاكاة باستخدام القوائم المزدوجة
   
5. اختبر قدراتك

تعريف

يُمكن تشبيه المكدس أو الــ Stack بمجموعة الصحون حيث يُمكننا إضافة صحن في القمة لكن عندما نريد سحب أحد الصحون, يلزمنا سحب كافة الصحون الموجودة فوقه و هذا النوع من الترتيب يُعرف اختصاراً بــ LIFO أي Last In First Out.

المكدس لا يملك نوع بيانات خاص به و إنما هو مجرد تركيبة يُمكن محاكاتها باستخدام المصفوفات أو القوائم (سواء كانت بسيطة أو مزدوجة) أو حتى الأشجار (Trees).

تنويه:

في بقية المقالة :

• سأقوم بتقسيم الكود الكامل إلى مجموعة دوال للتوضيح.
  
• كل جزء من الكود سيكون مُرتبطاً بالجزء السابق له.
  
• الأخطاء التي شرحناها سابقا (مثل فشل عملية الحجز) لن نتعرض لها هذه المرة من أجل الاختصار.

المحاكاة باستخدام المصفوفات

لمحاكاة المكدس بالمصفوفات سنحتاج إلى :

• عدد ثابت يُمثل العدد الأقصى لعناصر المكدس.
  
• مصفوفة لتخزين العناصر.
  
• و متغير صحيح يُمثل الــ index الخاص بقمة المكدس.

إذا الإعلان عن العناصر السابقة سيكون هكذا:

نأتي الآن إلى دالة الإدراج :

إذا كانت قيمة top أكبر أو تساوي من MAXSIZE فهذا يعني أن المكدس قد امتلأ لذا قمنا بإظهار رسالة تفيد بذلك.

في الحالة المعاكسة, إذا كانت قيمة top أقل من الصفر, نقوم بإعادتها للصفر ثم نقرأ القيمة التي أدخلها المستخدم و نخزنها في قمة المكدس ثم نجعل المتغير top يُشير إلى الخانة الموالية.

بالنسبة لدالة الحذف فهي كالتالي :

إذا كان الــ index الذي يُشير إلى قمة المكدس أكبر أو يساوي صفر نقوم بعمل decrement له مما يعني الرجوع إلى الخلف بخطوة واحدة.

دالة الإظهار هي التي تُظهر حقيقة المحاكاة :-)

القيمة الابتدائية للمتغير top هي 0 و بالتالي إذا كان top أقل أو يُساوي صفر فهذا يعني أن المكدس فارغ.

في الحالة المُعاكسة, سنقوم بإظهار العناصر ابتداء من قمة المكدس وصولا إلى الصفر. (في الحقيقة, ما يحدث هو أن المكدس عبارة عن مصفوفة و إظهار العناصر يتم بالمقلوب أي من الأخير إلى الأول)

المحاكاة باستخدام القوائم - مُقدمة

يمكننا اعتبار أن المكدس ما هو إلا حالة خاصة من القوائم المتصلة حيث لا يُمكن إضافة أو حذف عنصر إلا من بداية القائمة لذا فإن العمليات ستقتصر أساسا على دالتين أساسيتين هما:

• دالة اسمها Push تقوم بإدراج عنصر في بداية المكدس.
  
• دالة اسمها Pop تقوم بحذف عنصر من بداية المكدس.

المحاكاة باستخدام القوائم البسيطة

الإعلان عن المكدس سيكون هكذا:

المكدس سيحتوي على قيمة واحدة من نوع int بالإضافة إلى المؤشر ptrPrev الذي يُمثل مفتاح الدخول. المؤشر top يُشير إلى قمة المكدس و المؤشر temp عبارة عن مؤشر مؤقت.

نبدأ مع دالة التهيئة :

في البداية, قمنا بحجز مساحة جديدة للمؤشر top ثم طلبنا من المستخدم إدخال عدد صحيح ليتم تخزينه في المتغير value داخل العقدة الجديدة. المؤشر ptrPrev جعلناه يُشير إلى NULL و temp إلى top.

دالة الإضافة مُشابهة جدا لدالة التهيئة :

فقط, الفرق يكمن في كيفية ربط المؤشر ptrPrev بالمؤشر الموالي.

دالة الحذف ستكون كالآتي :

إذا كان temp يُشير إلى NULL فهذا يعني أن المكدس فارغ لذا قمنا بإظهار رسالة تُفيد بذلك.

في الحالة المعاكسة سنقوم بنسخ temp داخل top و نُظهر القيمة التي سيتم حذفها ثم نحرر المؤشر top بعد أن ننتقل إلى العقدة السابقة.

بالنسبة لدالة الإظهار فلن تتغير (سبق و أن شرحناها في الجزء الأول) :

المحاكاة باستخدام القوائم المزدوجة

الإعلان عن مكدس باستخدام القوائم المزدوجة سيكون قريبا جدا من الإعلان السابق, فقط نُضيف مؤشر لاحق :

دالة الإضافة ستكون كالآتي :

في البداية, قمنا بالإعلان عن مكدس جديد باسم newStack و قمنا بحجز المساحة المطلوبة له ثم طلبنا من المستخدم إدخال قيمة و قمنا بتخزينها في المتغير value.

إذا كان newStack يُشير إلى NULL فهذا يعني أن المكدس فارغ و بالتالي العقدة الجديدة ستُحاط بعناوين NULL من كلا الجانبين. في الحالة المعاكسة سنجعل المؤشر اللاحق لــ newStack يُشير إلى myStack و المؤشر السابق لــ myStack يُشير إلى newStack و المؤشر السابق لــ newStack يُشير إلى NULL ثم نقوم بتحديث المكدس.

بالنسبة لدالة الحذف فستكون كالتالي :

إذا كان المكدس فارغ سيتم إظهار رسالة تُفيد بذلك و الخروج من الدالة.

في الحالة المعاكسة, سيتم إظهار العنصر الذي سيتم حذفه و التقدم إلى العقدة الموالية و حذف المؤشر الذي يُشير إلى العقدة السابقة.

عند الانتهاء من عملية الحذف, نتحقق من ما إذا كان المكدس يحتوي على عقدة واحدة أم لا ؟ إذا كان الجواب نعم, نقوم بربط العقدة الوحيدة بالمؤشر NULL كمؤشر سابق لها.

دالة الإظهار لن تتغير (سبق و أن شرحناها في الجزء الثاني) :

اختبر قدراتك

قم بعمل برنامج يحول infix إلى postfix باستخدام الــ Stacks.

إلى هنا أصل بك أخي القارئ إلى نهاية هذا الدرس, آمل أن تكون استفدت من هذا الدرس و تعلمتَ أشياء جديدة :)

تحياتي.

[A.S Hack 185]

تنسيق رائع للطرح. سلمت يمناك.

+1

[ahmed.o.mohamed 931]

شكرا أخي A.S Hack

سررت بمرورك.

[Abboodd 61]

شكراً لك أخي الكريم، اسمحلي أن أضيف هنا بعض فوائد الـStack واستخداماته:

 

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

يمكنك تطبيق الأمر ذاته على حل لعبة الـSudoko، حيث يمكنك أن تجعل الحاسوب يتخذ سلسلة من القرارات، وعندما يجد أنه وصل إلى نتيجة خاطئة، يتراجع عن آخر قرار ويغير مساره، إلى أن يصل إلى النتيجة الصحيحة، يدعى هذا الأسلوب بالـBackTracking.

 

استخدام آخر للـStack هو في تحليل الأقواس في العمليات الحسابية، فعندما ترى: 

(3 + 5(8 + 4))

فإن الـstack سيساعد البرنامج على تحديد أن أول قوس إغلاق هو لإغلاق آخر قوس فتح تم إدخاله في الـstack. أي أن أول قوس ) سيراه، هو لإغلاق العملية (8 + 4) وليس لإغلاق العملية الكاملة.

 

أما أهم استخدامات الـstack فهي الخوارزميات التي تعتمد على الـrecursion، ويمكنك النظر إلى أي كود يحتوي recursion لتجد أن هناك stack لا تراه يقوم بإدارة العملية، ويرتب الأمور بحيث أن آخر استدعاء للـfunction هو أول استدعاء سيعيد نتيجة، حلل هذا الكود لترى كيف يعمل بأسلوب الـstack، وإن كنت لا ترى الـstack أمامك، فإنه يستعمل ما يدعى بـfunction stack:

int pow(int x, int y){if (y == 0)return 1;return x * pow(x, y - 1);}if (y == 0) 

 

بشيء من التحليل لهذا الكود، سترى أن هناك stack يقوم بعمل معين وراء الكواليس، يمكنك حقيقة الاستفادة من هذا الـstack بشكل كبير. على سبيل المثال، إذا أردت برنامجاً تدخل إليه الرقم 4 مثلاً، فيطبع:

****

***

**

*

*

**

***

****

بعد قليل من النظر، ستلاحظ أنك لو أدخلت في stack السطور الأربعة الأولى ثم أخرجتها من الآخر إلى الأول، فستحصل على ما تريده تماماً، ويمكننا استعمال الـFunction stack كالتالي:

 void StackExample(int n){if (n == 0)return; for (int i= 0; i < n; i++)cout<< "*";cout<< endl; StackExample(n - 1); for (int i= 0; i < n; i++)cout<< "*";cout<< endl; }

يمكنك أن تنظر للاستدعاء العودي للدالة على أنه عمل push في الـfunction stack، بينما انتهاء الدالة هو عمل pop.

 

أرجو أن تكون الأمثلة مفيدة ووضحت شيئاً من قيمة الـstack في البرمجة

 

وشكراً لك أستاذ على هذه الدروس :)