كدسة

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

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

يُمكن أن تنشأ الكدسة بقائمة متصلة مع مؤشر يدل على قمة الكدسة. ويُمكن أيضًا أن تكون ذات مقاسٍ ثابت، فلو تجاوزته كمية البيانات قيل عندها أن الكدسة قد فاضت أو طفحت.

 التسمية 

يذكر معجم لسان العرب في مادة (ك د س): «الكُدْس والكَدْس: العَرَمَة مِنَ الطَّعَامِ وَالتمر وَالدراهِمِ ونحو ذلك، والجمع أَكداس». ويتصرَّف فعلها الثلاثي المُجرَّد من الباب الثاني: «كَدَسَ يَكْدِس كَدْساً». وفي المعجم المدرسي أن: «الكُدْس هو المجتمع من كل شيء»، ويذكر مزيده الثلاثي بحرفين (تكدَّس): «تكدس الحصيد: جُعِل كُدْسًا. وتكدَّست الأشياء: تراكمت وازدحمت وتجمع بعضها فوق بعض».

وفي المعاجم التقنية ورد لفظ (كدسة) من غير ضبطٍ كما في (معجم مصطلحات المعلوماتية) الصادر عن الجمعية العلمية السورية للمعلوماتية. ومن الأسماء الأخرى لهذه البنية أيضًا: المَكْدَس والكَوْمة والرُّكام، والرَّصَّة والصف القائم.

 نبذة تاريخية 

بدأ ظهور مفهوم الكدسة في علم الحاسوب بدءًا من سنة 1946م، عندما استعمل آلان تورنغ مصطلحي دَفَن ونقَّب للإشارة إلى استدعاء دالة وإعادة قيمة منها. أُنجِزت الكدسة وعمليتا الدفع والنزع مسبقًا في حاسوب زد4 الذي صنعه كونراد سوزه سنة 1945م.

اقترح فريدريش باور وكلاوس ساميلسون في أثنا عملهما في جامعة ميونخ التقنية فكرة الكدسة سنة 1955، وسمياها «المستدعي العملياتي»، وسجلا براءة اختراع فيها سنة 1957م. حصل ساميلسون سنة 1988، بعد وفاة باور (1980م)، على  التي يقدمها معهد مهندسي الكهرباء والإلكترونيات.

 مبدأ العمل 
تصغير|200بك|تمثيل مُبسَّط للكدسة وللعمليات الرئيسة عليه

الكدسة قائمة خطية تجري كل العمليات عليها، من إدراج عناصر جديدة فيها وإزالة العناصر منها والوصول إلى عناصر فيها، على أحد نهايتي القائمة. وهي تختلف بذلك على القوائم الخطية الأخرى: الرتل، الذي تجري عمليات الإدخال على أحد نهايته، والإزالة على النهاية الأخرى، و: الذي تجري عمليات الإدخال والإخراج على نهايتيه.

ويتفق (معجم أكسفورد لعلم الحاسوب) مع هذا التعريف فالكَدْسة وفقًا له: قائمة خطية تُنجز العمليات على عنصرها، وصولًأ وإدراجًا وحذفًا، من أحد طرفيها الذي يُسمَّى قمةً، والوصول إلى عناصرها أو إدراجها وحذفها. وتُعرِّف الطبعة الرابعة من (معجم الحاسبات) الصادر عن مجمع اللغة العربية بالقاهرة الكدسة بأنها: «طريقة لتخزين البيانات في هيكل مدخله هو مخرجه، فيكون آخر بيان دخولًا هو أولها خروجًا»

140بك|يمين|تصغير|كدسة الصحون تشبه في مبدأ عملها كدسة البيانات: لا يُمكن إزالة الصحون أو إضافتها إلا من رأس الكدسة.
تشبه الكدسة المحوسبة كدسة الصحون ذات النابض في المقاهي، وفيها تُوضع الصحون النظيفة الجاهزة للاستعمال على قمة الكدسة دافعة الصحون الموجودة مسبقًا إلى الأسفل. عند إزالة الصحن الموجود في القمة يحل محله الصحن الموجود تحته مباشرة.

للكدسة عمليتان رئيستان:

 الدفع: أي إضافة عنصر على أعلى الكدسة.
 النزع، وتُسمَّى أيضًا القَطْف: أي سحب عنصرٍ من أعلى الكدسة.

يُمكن أيضًا قراءة قيمة العنصر في أعلى الكدسة من غير تعديلها، وتُسمَّى هذه العملية . لا تعد الوَصْوصة عملية رئسية لأنها تشمل عمليتن رئيستين: نزع القيمة لقراءتها ثُمَّ دفعها للكدسة.

يُسمَّى العنصر الأعلى في الكدسة رأسها، وهو العنصر الذي سيُزال لو أجريت عملية نزعٍ، ويُسمى العنصر تحته العنصر التالي بعد الرأس، والذي يليه الثالث بدءًا من الرأس وهكذا وصولًا لقعر الكدسة، وهو أبعد العناصر فيها عن الرأس.

إذا كانت الكدسة فارغة، أي لا عناصر فيها فهي في حالة غَيْض، وعندها لا يُمكِن إجراء عمليتي النزع والوَصْوصة لعدم وجود أي عنصر، أما إذا كانت الكدسة ممتلئة على آخرها، فهي في حالة فيض أو طَفْح، ولا يُمكن عندها إجراء عملية الدفع.

 التنجيز 

200بك|تصغير|مخطط صنفي لكدسة بلغة النمذجة الموحَّدة.

يمكن تنجيز الكدسة بسهولة باستعمال مصفوفة أو قائمة متصلة مع اعتبارها حالة خاصة من القوائم المتصلة. ما يجعل بنية البيانات كدسةً ليس ليس طريقة تنجيزها بل طريقة التعامل معها: يُمكِن للمستخدم نزع عتصر من رأسها أو دفع عنصر إليها.

للكدسة 3 دوال رئيسة: دالة الدفع: لإضافة عنصر لرأس للكدسة ويُمرَّر لها العنصر الذي يُراد إضافته ولا تُعيد أي قمية، ودالة النزع: لإخراج عنصر من رأس الكدسة وهي تعيد العنصر المنزوع، ودالة التحقق من فراغها وتعيد قيمة منطقية: صائب للدالة على فراغ الكدسة، وباطل للدلالة على عدم فراغها. إذا كان للكدسة قد محدد فيمكن كتابة دالة تعيد القد.

 بمصفوفة 
 البنية والسلوك 
يُمكن أن تُستعمل مصفوفة لتنجيز كدسة محدودة القد. يؤدي الموقع الأول في المصفوفة،أي الموقع الذي تكون إزاحته صفرية array[0]، دور قعر الكدسة، سيخزن هذا الموقع أول عنصر يُدفَع إلى المصفوفة وهو الهنصر الأخير الذي سيزال قبل الوصول لحالة الغيض. يلزم تتبع قد الكدسة بمتغير يُسمَّى الرأس يحفظ عدد العناصر المدفوعة للكدسة، وبما أن إزاحة العنصر الأول صفرية، فإن الرأس يُشير إلى فهرس المصفوفة الذي سيدفع إليه العنصر التالي.

يُوصَف هيكل بيانات الكدسة المبنية بمصفوفة وإجرائية استبدائها كما يأتي:

تضيف إجرائية الدفع عنصرًا لرأس الكدسة وتزيد قيمتها بمقدار واحد بعد التأكد من عدم حصول فيض (طَفح):
تصغير|200بك|صورة مُحرَّكة لعمليات دفع متتالية لكدسة مبنية بمصفوفة من حالة الغيض إلى حالة الفيض (الطفح).

أما إجرائية النزع فتنقص الرأس بمقدار واحد بعد التأكد من عدم حصول غيض (فراغ الكدسة)، ثُم تعيد العنصر الذي كان سابقًا في رأس الكدسة.
تصغير|200بك|صورة مُحرَّكة لعمليات نزع متتالية لكدسة مبنية بمصفوفة من حالة الامتلاء الكامل إلى حالة الغيض.

يُمكن استعمال مصفوفة ديناميكية لجعل قد الكدسة ينمو ويتقلص حسب الحاجة. يُحسن هذا من كفاءة التنجيز لأن إضافة عنصر لكدسة مبنية بمصفوفة ديناميكية أو إزالته من نهاية الكدسة يستهلك زمنًا قدره O(1).

 بلغات برمجة مختلفة 
الكدسة المبنية بمصفوفة ودوالها مُنجَزة بلغة سي++:

الكدسة المبنية بمصفوفة مُنجَزة بلغة جافا:

الكدسة المبنية بمصفوفة مُنجَزة بلغة بايثون:

 بقائمة متصلة 
يُمكن أن تُبنى الكدسة بقائمة متصلة، وتكون عندها مؤشر يُشير إلى رأس القائمة وقد يُضاف إليها عداد لتتبع عدد العناصر في القائمة أي قد الكدسة. تبنى الكدسة بقائمة متصلة كما يأتي:

تُنجَز عمليتي الدفع والنزع على رأس الكدسة، ولا يُمكن نظريًا أن يحصل فيض (طَفح) لأن قد الكدسة غير ثابت، لكن استهلاك كامل الذاكرة يؤدي لفيض الكدسة.
تصغير|200بك|صورة مُحرَّكة لعمليات دفع متتالية لكدسة مبنية بقائمة متصلة.

تصغير|200بك|صورة مُحرَّكة لعمليات نزع متتالية لكدسة مبنية بقائمة متصلة.

 بلغات برمجة مختلفة 
الكدسة المبنية بقائمة متصلة ودوالها مُنجَزة بلغة سي++:

الكدسة المبنية بقائمة متصلة مُنجَزة بلغة جافا:

الكدسة المبنية بقائمة متصلة مُنجَزة بلغة بايثون:

 انظرأيضًا 


 الرتل


 ملاحظات 

 المراجع 
 فهرس الإحالات 
المنشورات
بالعربية

بالألمانية

بالإنجليزية

الوب
بالألمانية

بالإنجليزية

 ثبت المراجع 
المقالات المُحكَّمة
بالألمانية



بالإنجليزية




الكتب
بالعربية










بالإنجليزية










تصنيف:بنية الحاسوب
تصنيف:بنى البيانات
تصنيف:أنواع بيانات مجردة
تصنيف:مقالات تحوي أمثلة مكتوبة بشبه رماز