ماهي المكدسات ..؟؟

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذا الرابط]

ماهي المكدسات ..؟؟

هذا السؤال قد يراود الكثيرين منا .. ولم نعرف له اجابة قط... ولكن الان سوف نتعرف على المكدسات

المكدسات:

تعريفها: هي إحدى طرق تركيب البيانات التي تكون من نفس النوع.

مبدأ عملها: تتم عملية الإضافة والإزالة من طرف واحد .

من يدخل آخرا يخرج أولا LIFO.

طرق التعبير عن المكدسات

• يعبر عنها بمصفوفة أحادية .

• نحتاج إلى الإعلان عن متغير يعمل كمؤشر يشير إلى أخر عنصر موجود في المكدسة يسمى TOP ويمثل INDEX لها.

في البداية تكون قيمة TOP = -1

العمليات الممكنة عليها :

• عملية الإضافة PUSH

• عملية الحذف POP

• فحص هل المكدسة فارغة STACK EMPTY

• فحص هل المكدسة ممتلئة STACK FULL

الإضافة PUSH :

• عند القيام بعملية الإضافة لا بد من فحص المصفوفة هل هي ممتلئة أم لا .

• ملاحظة إذا كان عدد العناصر= N فإن موقع أخر عنصر= N-1

• لإضافة القيمة F :

IF TOP>=N-1 THEN

ممتلئة PRINT “OVERFLOW ”

ELSE

TOP=TOP+1

S(TOP)=F

END IF

الحذف pop :

• قبل الحذف لا بد فحص المصفوفة إذا ما كانت فارغة .

• يتم ذلك من خلال فحص قيمة TOP

IF TOP= -1 THEN

PRINT “EMPTY”

ELSE

F=S(TOP)

END IF

من أشهر التطبيقات على المكدسات :

• تستخدم لفحص التعابير الحسابية التي تحتوي على أقواس (مطابقة الأقواس).

• مثل (((5+2)*3)-1)

• المبدأ:

• قوس يسار :إضافة

• قوس يمين : إزالة

• تحليل النتيجة : 1- الانتهاء والمصفوفة (المكدسة )فارغة يكون التعبير صحيحا.

2-إذا تعرضنا لحالة إخراج pop وكانت المصفوفة فارغة

يكون عدد الأقواس اليمنى >من اليسرى.

3-الانتهاء والمصفوفة غير فارغة يكون عدد الأقواس اليسرى >من اليمنى.

الطوابير –الأرتالQUEUES

• التعريف: نوع من التراكيب لبيانات من نفس النوع.

• مبدأ العمل : تتم الإضافة من طرف (المؤخرة ) والحذف من الطرف الأخر .

من يدخل أولا يخرج أولا FIFO

العمليات على الطوابير

• الإضافة : تتم من المؤخرة

• الحذف تتم من المقدمة

• فحص الطابور :فارغ أم لا قبل الحذف

• فحص الطابور ممتلئ أم لا قبل الإضافة .

في البداية

• نجعل FRONT = 0

• REAR = -1

• يكون الطابور فارغا عندما FRONT > REAR

(عدد العناصر= صفر .)

• يكون الطابور ممتلئا عندما يكون عدد العناصر= سعته

• نحسب عدد العناصر كالتالي:

• N = REAR - FRONT +1

الإضافة

• قبل الإضافة لا بد من فحص إذا ما كان الطابور ممتلئا :

نجد عدد العناصر= N = REAR-FRONT+1

IF N= SIZE THEN

PRINT “FULL”

ELSE

REAR=REAR+1

Q(REAR)= F

END IF

الحذف من الطابور

• قبل الحذف نفحص هل هو فارغ أم لا وذلك عن طريق فحص عدد العناصر أو FRONT > REAR

• IF FRONT > REAR THEN

• PRINT “EMPTY”

• ELSE

• F=Q(FRONT)

• FRONT=FRONT+1

• END IF

قد نصل إلى حالة :

• مثلا نريد أن نضيف عنصرا إلى المصفوفة المجاورة.

• نفحص هل ممتلئة حسب عدد العناصر :الجواب لا !

• نزيد قيمة REAR=REAR+1

• نحصل على القيمة 5 للمتغير REAR

• عندما نقوم بإدخال القيمة للمتغير Q(REAR) أي Q(5)

• يظهر خطأ لأن موقع أخر عنصر هو Q(4) !

من هنا نتجت فكرة الطوابير الدائرية .

الطوابير الدائرية

• نحتاج إلى عداد C ليحسب عدد العناصر المدخلة إلى الطابور

• نصفر قيم المتغيرات FRONT =0 ,REAR=0 , C=0

• نستخدم العداد لفحص حالة الطابور ممتلئ أم لا .

عند الإضافة نستخدم الجملتين :

REAR = (REAR+1) MOD 5

C=C+1

عند الحذف نستخدم الجملتين :

FRONT= (FRONT+1) MOD 5

C=C-1

وذلك حتى تبقى قيم FRONT ,REAR محصورة بين (0 و4 )

» مرض البلهارسيا .. ماهي وما أعراضها ...؟؟