كدسة

بقائمة متصلة

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

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

بلغات برمجة مختلفة

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

بلغات برمجة مختلفة

• الكدسة المبنية بقائمة متصلة ودوالها مُنجَزة بلغة سي++:
• الكدسة المبنية بقائمة متصلة مُنجَزة بلغة جافا:
• الكدسة المبنية بقائمة متصلة مُنجَزة بلغة بايثون:
• انظرأيضًا
• الرتل
• ملاحظات
• المراجع
• فهرس الإحالات
• المنشورات
• بالعربية
• بالألمانية
• بالإنجليزية
• الوب
• بالألمانية
• بالإنجليزية
• ثبت المراجع
• المقالات المُحكَّمة
• بالألمانية
• بالإنجليزية
• الكتب
• بالعربية

مبدأ العمل

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

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

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

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

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

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

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

التسمية

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

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

البنية والسلوك

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

وفي هذا السياق، تضيف إجرائية الدفع عنصرًا لرأس الكدسة وتزيد قيمتها بمقدار واحد بعد التأكد من عدم حصول فيض (طَفح):

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

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

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

التنجيز

بمصفوفة

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

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

نبذة تاريخية

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

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