بُنى المعطيات - المُكَدِّس

يعد المكدّس (Stack) أحد أشهر بنى تخزين المعطيات ويعتمد المكدّس في آلية عمله على مبدأ بسيط جدّاً

هو أنَّ المعلومة التي تدخل أخيراً ستخرج أوّلاً (Last in first out) , بمعنى آخر

تخيّل المكدّس كما لو كان أنبوباً اسطواني الشكل له فتحة واحدة من الأعلى ;

ثم جئنا و وضعنا به كميّة من مادة س ثم وضعنا فوقها كميّة من مادة ع ثم وضعنا فوق السابقتين كميّة جديدة من مادة ص الآن لو أردنا أن نصل للمادة ع

الآن نستطيع أن نتعامل مع المادة ع بسهولة , لكن لو أردنا التعامل مع المادة ع فإننا و بشكل منطقي يجب أن نخرج المادة ص أولاً كي نتمكّن من ذلك ; انظر الشكل

الآن و بعد أن فهمنا ما هو المكدّس (نظريّاً) دعونا نعمل سويّاً كي نبني بنية المعطيات هذه

سأستعمل لغة البرمجة C++ لبناء مكدّس بسيط حتّى تتوضح الفكرة و نتمكن من استعماله في أي

من مشاريعنا لاحقاً.

نقاط العمل الرئيسيّة :

سنستفيد من بنية تخزين معرّفة مسبقاً هي بنية (المصفوفة) لتمثّل المكدّس ;

و سأفترض أن نوع البيانات الذي سيحتوي عليه المكدّس هو النوع int و أن أقصى عدد لما يمكن أن يحتويه المكدّس هو 100 عنصر للسهولة .

للمكدّس خمسة توابع اتفق المبرمجون على تسميتها بما يلي :

Stack_Init : دالة تقوم بتهيئة المكدّس الجديد .

Stack_Empty : دالة تقوم بالتحقق من أن المكدّس فارغ أم لا .

Top : دالة تقوم بإرجاع العنصر العلوي من المكدّس (العنصر المدخل أخيراً) .

Pop : دالة تقوم بحذف آخر عنصر تم ادخاله للمكدّس .

Insert : دالة تقوم بإضافة عنصر جديد للمكدّس .

دعونا نبدأ على بركة الله ;

الآن قارئتي الجميلة و قارئي الوسيم لو لاحظتما معي أنّنا نتعامل دائماً مع العنصر الأخير في المكدّس

و بكل تأكيد أنتما تعلمان أنّنا نحتاج لمعرفة فهرس كل عنصر من المصفوفة لنتعامل معه و هاتان المعلومتان

تؤديان أننا نحتاج إلى تعريف متغيّر ليدلنا على رقم العنصر الأخير من المكدّس ;انظر الشكل

الآن و قبل كتابة الدوال بما أنّنا عرفنا ما سنحتاجه دعونا نعرّف المكدّس و المتغير كما يلي

و بالتالية بإمكاننا أن نكتب شيئاً شبيها بما يلي :

int stack[100];
int T;

الدالة الأولى - تفريغ المكدّس :

لتفريغ المكدّس كل ما علينا فعله هو وضع القيمة -1 ضمن متغير رقم العنصر الأخير مما يعني أنّه لا يوجد

أي عنصر ضمن المكدّس ; انظر الشكل

و بالتالي أصبح بإمكاننا أن نكتب الدالة كما يلي

Void stack_init()
{
T=-1;
}

الدالة الثانية – هل المكدّس فارغ ؟

كما عرفنا سابقاً يكون المكدّس فارغاً إذا كان T يحتوي على القيمة -1 و بالتالي بإمكاننا بناء الدالة ببساطة كما يلي

Bool Empty()
{
	Return T==-1;
}

الدالة الثالثة – إضافة عنصر للمكدّس :

كي نضيف عنصراً جديداً للمكدّس يكفي أن نزيد قيمة المتغير T بمقدار 1 ثم نقوم بإسناد القيمة المدخلة إلى العنصر Stack[T] طبعاً على ألّا تزيد قيمة المتغيّر T عن الحد الأقصى لما يمكن أن يحتويه المكدّس و هو 100 في مثالنا و بالتالي بإمكاننا أن نكتب شيئاً قريباً مما يلي

Void insert(int value)
{
	If(T<100)
	{
		T++;
		Stack[T]=value;
	}
}

الدالة الرابعة – حذف عنصر من المكدّس :

لحذف عنصر من المكدّس يكفي أن ننقص قيمة المتغيّر T بمقدار 1 بشرط ألّا يكون المكدّس فارغاً أصلاً .

Void pop()
{
	If(T>=0)
		T--;
}

الدالة الخامسة – قراءة العنصر الأخير :

لقراءة العنصر الأخير يكفي أن نعيد العنصر Stack[T] كما يلي

Int top()
{
	Return Stack[T];
}

الآن انتهت التوابع بشكلها الأبسط و هكذا نكون انتهينا من بناء مكدّس بسيط .

ملاحظات : تستطيع بناء صف جديد ليمثل هذا المكدّس و بالتأكيد سوف تتعامل مع الذاكرة الديناميكية حيث سيصبح حجم المصفوفة متغيّراً بما يناسب احتياجات مشروعك كما تسمح لك فكرة الصف بالاستفادة من كامل ميزات البرمجة غرضية التوجه .

بالمناسبة هذا الدرس ليس إلا أفكار شخصيّة أحببت أن أفيد بها أحداً قد يستفيد و سأتابع من بنى المعطيات الأخرى في دروس لاحقة إن وفقني الله تعالى.

إلى هنا نكتفي هذا اليوم

لكم كل الود من

أخوكم :

مختار السيد صالح