السلام عليكم ورحمة الله تعالى وبركاته، هذا الدرس ختام الفصل الثالث من كتاب «استيعاب الخوارزميات Grokking Algorithms»، والذي كان آخر درس منه درس «العَوْدِيَّة».

مفهوم الكَدسَة مفهوم مهم في البرمجة على المبرمج فهمه وخاصةً عند استعمال العَوْدِيَّة، وقبل الشروع في شرحه علينا تبيين مفهوم مهم ألا وهو نوع معطيات مجرد ADT.

نوع معطيات مُجرَّد

نوع معطيات مُجرَّد abstract data type: أسلوب لتنظيم وتخزين المعطيات data بطريقة محددة، دون تفاصيل عن كيفية إنجازه implementation برمجيًا.

بمعنى آخر فإن نوع المعطيات المُجرَّد، اختصارًا ADT، ليس إلا وصف لمجموعة من المُعطيات والعمليات التي ستُنفَّذ عليها، دون التطرق إلى تفاصيل التنجيز implementation.
لم تفهم بعد؟
حسنًا، نوع المعطيات المُجرَّد يشبه آلة بيع المشروبات الغازية!
تضع العملة في الآلة وتختار المشروب، لا حاجة لتعلم كيف تعمل هذه الآلة داخليًا لتستعملها، ضع المال واضغط على الزر، وسيخرج مشروبك!

وبالمثل فإن نوع المعطيات المُجرَّد يشبهه تمامًا. سيتضح ذلك في شرح مفهوم الكَدسَة.

برمجيًا نحن نستعمل وظائف functions كثيرة، مثلًا في لغة الثعبان python نستعمل الوظيفة open لفتح ملف والكتابة إليه أو قراءته، وأيضًا الوظيفة print، لكن أنعلم ما الذي يحدث حقًا؟
أيعلم أحدكم كيف تعمل وظيفة open أو وظيفة print؟

لنكن صريحين، الغالبية لا تعلم ما الذي يحدث ولا يهمنا عادة الذي يحدث، كل ما يهمنا أننا نقدر على استعمالها مثل آلة المشروبات الغازية!

طبق أنواع المعطيات المُجرَّدة في أي لغة برمجة، لست محصورًا بأي لغة، وأيضًا نوع المعطيات المُجرَّد يستعمل لبناء بُنى معطيات data structures وخوارزميات معقدة، فإنها مفيدة ​لتسهيل تصميم وصيانة أنظمة البرمجيات، بطريقة واضحة ومختصرة للتعبير عن خصائص وسلوك بُنى المعطيات.

إن لم تفهم ما قلته حتى الآن ستفهم نوع المعطيات المُجرَّد بفهمك لمفهوم الكَدسَة، الذي هو موضوع مقالنا لليوم.

الكَدسَة stack

من الاسم، الكَدسَة، ما الذي تبادر لذهنك؟
مجموعة من الأشياء مكدسة، بعضها فوق بعض؟
أحسنت، كَدسَة كتب أو صحون، مثل هذه الصورة:

لسحب كتاب من هذه الكَدسَة، ولنقل الكتاب الأوسط، فعلينا إنزال الكتب التي تعلوه أولًا، ننزلهم واحدًا واحدًا حتى نصل للكتاب المطلوب.

ولو أردنا إضافة كتاب وضعناه في القمة، قمة الكَدسَة.

هل تعلم أنك فهمت مفهوم الكَدسَة الآن؟
لنفصل القول!
الكَدسَة stack: نوع معطيات مُجرَّدة تقدر على تنفيذ عمليتين عليها، وهما إضافة قيمة وحذف قيمة، أي يمكِن دفع (إضافة) قيمٍ إليها، كما يمكِن نزعُها (إخراجها) منها.

إضافة قيمة يعرف بالدفع push، لإضافة قيمة جديدة. أما حذف قيمة فيعرف بالطرح pop. ويشار إلى آخر قيمة في الكَدسَة بالقمة top.

تمتاز الكَدسَة بخاصية تعرف اختصارًا بكلمة LIFO، وهي اختصار لجملة Last in First Out، أي من يدخل أخيرًا يخرج أولًا. ركز على هذه الخاصية ولا تنسها!

للكَدسَة سعة محددة، إذا كانت ممتلئة فلن تقدر على إضافة أي قيمة، وإن حاولت سيحدث فيض overflow: تجاوز الحد الأعلى للسعة. أما إن كانت فارغة وحاولت طرح قيمة فسيحدث غيض underflow: تجاوز الحد الأدنى للسعة.

قد يكون للكَدسَة عمليات أخرى، غير أساسية عكس عمليتي الدفع والطرح، مثل الاستراق peek: معرفة قيمة القمة دون طرحها.

أتذكر مفهوم نوع المعطيات المُجرَّد؟

كما ترى وصفنا ما هي الكَدسَة، وأنت قادر الآن على برمجتها سواء باستعمال لائحة مترابطة linked list أو صفيفة array، التي سبق وأن شرحتها هنا.

لست بحاجة لأن تعرف كيف تُخزِّن المعطيات data أو كيف تعمل عمليتي الإضافة والحذف في الكَدسَة، كل ما يهمك معرفة كيف تستعمل عمليتي الدفع والطرح لإضافة وإزالة القيم من الكَدسَة.

لِمَ اسمها الكَدسَة وليس المُكدِّس؟

كما ذكرت سابقًا، أعتمدُ على معجم المصطلحات المعلوماتية للجامعة السورية، وقد تُرجِمَت لفظة stack إلى كَدسَة، أما المُكدِّس فترجمة لكلمة heap، فجزاهم الله ألف خير.

مثال نظري

هل تساءلت كيف يعرف حاسوبك في أي جزء من البرنامج وصل في التنفيذ؟

لأجيبك على السؤال لنسمع قصة صاحبنا عبود!

في يوم من الأيام أراد عبود كتابة مقال يتحدث فيه عن إنجاز عظيم فعله، لقد دمج بطاريتين بالتوازي وصنع خازن شحن يأخذه أينما ذهب، وقد طار فرحًا!

قسم إنجازه العظيم إلى مراحل، وكتب كل مرحلة على قطعة ورق، ووضع كل قطعة داخل مكعب، وبنى برجًا من المكعبات، فوضع مكعبًا فوق مكعب، وهلم جرا.

ثم يأخذ مكعبًا من أعلى الكَدسَة، ويستخرج منه الجزء المُراد الكتابة عنه، وينجزه، وثم ينتقل للمكعب الثاني وهكذا…

ولقد كتب المقال كاملًا بتلك الطريقة، ونشره بين الأصدقاء إفادة لهم!

انتهينا من قصة عبود، فعل عرفت الآن إجابة السؤال؟

بالمثل، كما أتبع عبود تلك الطريقة، فإن الحاسوب يستعمل شيء يسمى كَدسَة الاستدعاءات call stack، يستعملها الحاسوب ليتذكر أين وصل في البرنامج، فالحاسوب غبي لا عقل له.

فالكَدسَة مثل برج المكعبات التي استعملها عبود، فعندما نشغل برنامجًا في الحاسوب فإنه يبدأ من أول الرِّمَاز ويضعه في مكعب ويضع المكعب في كَدسَة مكعبات، برج المكعبات، ويضيف مكعبًا كلما تقدم في تنفيذ البرنامج، كما أضاف عبود مكعبًا إلى برج المكعبات.

يحتوي كل مكعب في كَدسَة الاستدعاءات معلومات عن الوظيفة التي تعمل الآن، والوظيفة مجموعة تعليمات يتبعها الحاسوب لتأدية وظيفة، مثل إضافة رقمين أو طرحهما.

تتضمن تلك المعلومات مكان بدء الوظيفة، والمعطيات التي تحتاجها الوظيفة لتأدية وظيفتها. إذا استدعت الوظيفة أ وظيفة أخرى، لنقل الوظيفة ب، فإن الحاسوب يضيف معلومات هذه الوظيفة إلى كَدسَة الاستدعاءات أعلاها.

يستمر الحاسوب بإضافة وحذف المكعبات (الاستدعاءات) حتى يصل إلى نهاية البرنامج.

مثال عملي

سنرى ما سبق بمثال عملي. افترض أن لديك وظيفة تستقبل اسمًا وثم تلقي عليه التحية:

def greet(name):
    print(f"Hello {name}!")
    greet2(name)
    print("Getting ready to say bye...")
    bye()  

كما ترى في الرِّمَاز السابق، فإن هذه الوظيفة تستدعي وظيفتين، الوظيفة الأولى greet2:

def greet2(name):
    print(f"How are you {name}?")

وهذه الوظيفة تسأل الشخص عن حاله. أما الوظيفة الأخيرة، وظيفة التوديع bye:

def bye():
    print("Ok, Bye!")

تودع الشخص في نهاية هذا البُريمج الصغير.

لنرى ماذا سيحدث في استدعاء تلك الوظائف.

ملاحظة: سنتجاهل وظيفة الطباعة print التي في لغة الثعبان python ليكون المثال مفهومًا واضحًا.

لنفترض أنك استدعيت وظيفة التحية باسم maggie:

greet("maggie")

 

عند استدعاء الوظيفة فإن الحاسوب سيأخذ مكعبًا من الذاكرة، أي سيبدأ استعمال كَدسَة الاستدعاءات call stack.

ثم سيستعمل هذا الجزء من الذاكرة. وفي هذا الجزء من الذاكرة سيُعيَّن المتغير name على القيمة maggie، ويحفظ فيها.

في كل مرة تستدعي فيها وظيفة فإن الحاسوب سيحفظ جميع قيم تلك المتغيرات في الذاكرة بنفس الطريقة السابقة.

بعد استدعاء الوظيفة greet واقتطاع جزء من الذاكرة لحفظ معلومات الوظيفة، ستبدأ الوظيفة بالعمل، وستطبع اسم الشخص:

hello maggie!

ثم ستستدعى الوظيفة الثانية greet2(“maggie”). وكما حدث مع الاستدعاء الأول لوظيفة greet سيحدث لهذه الوظيفة.

سيأخذ الحاسوب مكعبًا به معلومات الوظيفة الحالية ويضعه فوق المكعب السابق، لتبدأ الكَدسَة بالتكون. وبما أننا قلنا إن الكَدسَة تتمتع بخاصية من يدخل أخيرًا يخرج أولًا Last in First Out، اختصارًا LIFO، فإن الوظيفة greet2 ستكون في قمة الكَدسَة، وبما أنها آخر من دخل ستكون أول من يخرج وسيشغلها الحاسوب.

سيشغلها ويطبع:

how are you, maggie?

وبما أن هذه الوظيفة انجزت عملها فلا حاجة لبقائها في قمة الكَدسَة لذا سنطرحها pop:

وبعد طرحها سنعود للوظيفة الرئيسة greet، فتستأنف العمل، فإن الوظيفة الرئيسة تترك في حالة مكتملة جزئيًا حتى تنتهي الوظيفة الفرعية من إنجاز عملها، وثم تستأنف الوظيفة الرئيسة العمل.

بعد عودتنا للوظيفة greet ستُطبعُ رسالة:

Getting ready to say bye!

وثم تستدعى الوظيفة التوديع bye، وعند استدعاء هذه الوظيفة فإن النظام يأخذ مكعبًا لها، ويضيفه (يدفعه push) إلى قمة الكَدسَة.

ستنفذ هذه الوظيفة وتطبع:

Ok, Bye!

وثم سنعود للوظيفة الرئيسة بعد طرح وظيفة التوديع من قمة الكَدسَة.

وعند عودتنا للوظيفة الرئيسة فلم يتبق أي شيء لفعله لذا سنخرج أيضًا من هذه الوظيفة وتكون الكَدسَة فارغة فينتهي البرنامج!

وها قد انتهينا، وكما ترى فهذا مفهوم الكَدسَة!

الكَدسَة والعَوْدِيَّة

لتفهم درس اليوم أكثر وتراجع الدرس السابق فإننا سنربطهما معًا!
أتتذكر مثال العاملي في الدرس السابق، درس العَوْدِيَّة؟
إذا شغلت وظيفة عَوْدِيَّة فإنها ستستعمل كَدسَة الاستدعاءات call stack أيضًا!

سأريك ذلك باستعمال العاملي، عاملي الثلاثة !3.

هذه وظيفة العاملي التي كتبناها في الدرس السابق:

def factorial(n):
    if n == 0: return 1
    return n*factorial(n-1)

سنرى استدعاءات هذه الوظيفة سطرًا بسطر الآن!

هذا الاستدعاء الأول للوظيفة، ولقد أخذ الحاسوب مربعًا ووضع للوظيفة، وعرف المتغير X بالقيمة ٣.

وكما ترى في أول ثلاثة سطور فكل شيء على حاله.

لما يصل للسطر الرابع الآن، سطر الاستدعاء العَوْدِي، سيأخذ الحاسوب مربعًا للوظيفة المستدعاة.

سننتقل الآن إلى السطر الأول من الوظيفة الثانية:

سننتقل للسطر الثالث من الوظيفة الثانية الآن:

بعد الانتقال للسطر الرابع من الوظيفة الثانية، سطر الاستدعاء العَوْدِي، سيأخذ الحاسوب مربعًا للوظيفة الثالثة كما في الصورة التالية.

وسترى في هذه الصورة أول سطر في الوظيفة الثالثة، سطر التوقف base case.

في هذه المرحلة الوظيفة الثالثة في قمة الكَدسَة سترجع العدد ١.

وستطرح بقية الصناديق من الكَدسَة حتى نصل للقيمة النهائية وهي ٦.

وكما رأيت فإن في كل استدعاء للوظيفة يكون للوظيفة المستدعاة متغير X خاص بها لا يمكن النفاذ access إليه.

الخاتمة

 وها أنا أخط بقلمي الخطوط الأخيرة لهذا المقال الشائق، وأرجو إني قد وفِّقت في شرح العَوْدِيَّة وتقريبها من الأذهان.

وفي نهاية الأمر لا يسعني سوى أن أشكرك على حسن قراءتك لهذا المقال، وأني لبشر أصيب وأخطِئ، فإن وفِّقت في طرح الموضوع فمن اللّٰه عز وجل وإن أخفقت فمن نفسي والشيطان.

أرجو منك تقييم كفاءة المعلومات من أجل تزويدي بالملاحظات والنقد البناء في خانة التعليقات أو عبر حساب الموقع، والسلام عليكم ورحمة اللّٰه تعالى وبركاته.