الــ Stacks في لغة C

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

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

الفهرس

• تعريف
• المحاكاة باستخدام المصفوفات
• المحاكاة باستخدام القوائم البسيطة
• المحاكاة باستخدام القوائم المزدوجة
• اختبر قدراتك

تعريف
يُمكن تشبيه المكدس أو الــ 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.

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

تحياتي.