المكدس (نوع بيانات مجرد)

📅 آخر تحديث: ١٧ يوليو ٢٠٢٦
✍️ نُشر في: ١٧ يوليو ٢٠٢٦
📷 يحتوي على 10 صور
الموسوعة الحرة

على غرار كومة الأطباق، فإن الإضافة أو الإزالة لا تكون عملية إلا في الأعلى.
تمثيل بسيط لوقت تشغيل المكدس مع عمليات الدفع والسحب

في علوم الحاسوب ، تُعتبر المكدسة نوعاً من البيانات المجردة التي تعمل كمجموعة من العناصر مع عمليتين رئيسيتين:

  • إضافة عنصر إلى المجموعة، و
  • Pop ، الذي يزيل العنصر المضاف مؤخرًا.

بالإضافة إلى ذلك، يمكن لعملية المعاينة ، دون تعديل المكدس، أن تُعيد قيمة آخر عنصر أُضيف (العنصر الموجود في أعلى المكدس). يُشبه اسم المكدس مجموعة من العناصر المادية المكدسة فوق بعضها البعض، مثل كومة من الأطباق.

يُوصف ترتيب إضافة العناصر إلى المكدس أو إزالتها منه بأنه " آخر ما يدخل، أول ما يخرج" ، ويُشار إليه اختصارًا بـ LIFO . [ ملاحظة 1 ] وكما هو الحال مع مكدس من الأشياء المادية، فإن هذا الهيكل يُسهّل إزالة عنصر من أعلى المكدس، ولكن الوصول إلى معلومة أعمق في المكدس قد يتطلب إزالة عدة عناصر أخرى أولًا. [ 1 ]

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

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

تاريخ

ظهرت المكدسات في أدبيات علوم الحاسوب عام 1946، عندما استخدم آلان تورينج مصطلحي "دفن" و"فك الدفن" كوسيلة لاستدعاء البرامج الفرعية والعودة منها. [ 2 ] [ 3 ] وكانت البرامج الفرعية ومكدس ثنائي المستوى قد طُبقت بالفعل في حاسوب كونراد تسوزه Z4 عام 1945. [ 4 ] [ 5 ]

اقترح كلاوس ساميلسون وفريدريش إل. باور من جامعة ميونخ التقنية فكرة مكدس يُسمى Operationskeller ("القبو التشغيلي") عام 1955 [ 6 ] [ 7 ] ، وقدّما طلب براءة اختراع عام 1957. [ 8 ] [ 9 ] [ 10 ] [ 11 ] وفي مارس 1988، بعد وفاة ساميلسون، حصل باور على جائزة IEEE للريادة في مجال الحوسبة لاختراعه مبدأ المكدس. [ 12 ] [ 7 ] وقد طوّر تشارلز ليونارد هامبلين مفاهيم مماثلة بشكل مستقل في النصف الأول من عام 1954 [ 13 ] [ 7 ] ، وكذلك فعل فيلهلم كاميرر مع ذاكرته التلقائية (automatisches Gedächtnis ) عام 1958. [ 14 ] [ 15 ] [ 7 ]

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

العمليات غير الأساسية

في العديد من التطبيقات، تحتوي المكدسة على عمليات أكثر من عمليتي "الدفع" و"السحب" الأساسيتين. ومن الأمثلة على العمليات غير الأساسية عملية "أعلى المكدسة" أو "النظرة الخاطفة"، التي تراقب العنصر العلوي دون إزالته من المكدسة. [ 18 ] وبما أنه يمكن تقسيم هذه العملية إلى "سحب" متبوعة بـ"دفع" لإعادة نفس البيانات إلى المكدسة، فإنها لا تُعتبر عملية أساسية. إذا كانت المكدسة فارغة، فسيحدث خطأ في التدفق السفلي عند تنفيذ أي من عمليتي "النظرة الخاطفة" أو "السحب". بالإضافة إلى ذلك، تتضمن العديد من التطبيقات عمليات مساعدة تُعنى بالمهام الشائعة، مثل التحقق من فراغ المكدسة أو إرجاع حجمها.

مجموعات البرامج

مخطط UML لمكدس

تطبيق

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

المصفوفة

يمكن استخدام المصفوفة لتنفيذ مكدس (محدود) كما يلي: العنصر الأول، والذي يكون عادةً عند الإزاحة الصفرية ، هو العنصر السفلي، مما يجعله array[0]أول عنصر يُضاف إلى المكدس وآخر عنصر يُزال منه. يجب على البرنامج تتبع حجم (طول) المكدس باستخدام متغير يُسمى top يسجل عدد العناصر المضافة حتى الآن، وبالتالي يشير إلى مكان إضافة العنصر التالي في المصفوفة (بافتراض استخدام فهرسة تبدأ من الصفر). وهكذا، يمكن تنفيذ المكدس نفسه كبنية ثلاثية العناصر.

بنية المكدس: الحد الأقصى للحجم: عدد صحيح أعلى : عدد صحيح العناصر: مصفوفة من العناصر
الإجراء initialize(stk : stack, size : عدد صحيح): stk.items ← مصفوفة جديدة من عناصر الحجم ، فارغة في البداية stk.maxsize ← size stk.top ← 0

تضيف عملية الدفع عنصرًا وتزيد من فهرس العنصر العلوي ، بعد التحقق من عدم وجود تجاوز:

عملية دفع متحركة على مكدس قائم على مصفوفة من التدفق السفلي إلى التدفق العلوي
الإجراء push(stk : stack, x : item): إذا كان stk.top = stk.maxsize: الإبلاغ عن خطأ تجاوز السعة آخر : stk.items[stk.top] ← x stk.top ← stk.top + 1

وبالمثل، تقوم دالة pop بإنقاص الفهرس العلوي بعد التحقق من عدم وجود تجاوز للقيمة، وتعيد العنصر الذي كان سابقًا العنصر العلوي:

عملية سحب متحركة لعنصر من مكدس قائم على مصفوفة، من حالة المكدس الكامل إلى حالة التدفق السفلي.
الإجراء pop(stk : stack): إذا كان stk.top = 0: الإبلاغ عن خطأ في التدفق السفلي آخر : stk.top ← stk.top − 1 r ← stk.items[stk.top] إرجاع r

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

قائمة مرتبطة

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

إطار الهيكل : البيانات: عنصر التالي: إطار أو لا شيء
بنية المكدس: الرأس: إطار أو لا شيء الحجم: عدد صحيح
الإجراء initialize(stk : stack): stk.head ← nil حجم المخزن ← 0

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

عملية دفع متحركة على مكدس قائم على قائمة مرتبطة.
الإجراء push(stk : stack, x : item): رأس جديد ← إطار جديد newhead.data ← x newhead.next ← stk.head stk.head ← newhead حجم المخزن ← حجم المخزن + 1
عملية سحب العناصر المتحركة على مكدس قائم على قائمة مرتبطة.
الإجراء pop(stk : stack): إذا كان stk.head = nil: الإبلاغ عن خطأ في التدفق السفلي آخر : r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 إرجاع r

الحزم البرمجية ولغات البرمجة

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

فيما يلي مثال على معالجة المكدس في لغة Common Lisp (" > " هو موجه مترجم Lisp؛ الأسطر التي لا تبدأ بـ " > " هي استجابات المترجم للتعبيرات):

> ( setf stack ( list 'a 'b 'c )) ;; تعيين قيمة المتغير "stack" ( A B C ) > ( pop stack ) ;; الحصول على العنصر العلوي (الأيسر)، يجب تعديله في المكدس A > stack ;; التحقق من قيمة المكدس ( B C ) > ( push 'new stack ) ;; إضافة عنصر علوي جديد إلى المكدس ( NEW B C )

تتضمن العديد من أنواع الحاويات في مكتبة C++ القياسيةpush_back() عملياتٍ pop_back()ذات دلالات LIFO؛ بالإضافة إلى ذلك، std::stackتُكيّف فئة القالب الحاويات الموجودة لتوفير واجهة برمجة تطبيقات محدودة تقتصر على عمليات الدفع والسحب. تحتوي PHP على SplStackفئةٍ مماثلة. تحتوي مكتبة Java على Stackفئةٍ تُعدّ تخصصًا من الفئة المذكورة Vector. فيما يلي مثالٌ لبرنامج مكتوب بلغة Java ، يستخدم هذه الفئة.

package org.wikipedia.examples ;استيراد java.util.Stack ؛public class Example { public static void main ( String [] args ) { Stack < Character > stack = new Stack <> (); stack . push ( 'a' ); // إدراج 'a' في المكدس stack . push ( 'b' ); // إدراج 'b' في المكدس stack . push ( 'c' ); // إدراج 'c' في المكدس stack . push ( 'd' ); // إدراج 'd' في المكدس System . out . println ( stack . peek ()); // طباعة العنصر العلوي ('d') stack . pop (); // إزالة العنصر العلوي التالي ('d') stack . pop (); // إزالة العنصر العلوي التالي ('c') } }

تتميز بعض المعالجات، مثل PDP - 11 و VAX وسلسلة Motorola 68000 ، بأنماط عنونة مفيدة لمعالجة المكدس. يقوم كود التجميع البسيط التالي لمعالج PDP-11 بدفع رقمين إلى المكدس وجمعهما، تاركًا النتيجة في المكدس.

يُفترض أن R0 يشير إلى منطقة مكدس ؛ -(R0) يُنقص مؤشر المكدس قبل تخصيص عنصر على المكدس ؛ (R0)+ يزيد مؤشر المكدس بعد إزالة عنصر من المكدس ؛ MOV #12,-(R0) ; إضافة 12 إلى المكدس MOV #34,-(R0) ; إضافة 34 إلى المكدس ADD ( R0 ) + ,( R0 ) ; إزالة 34 من المكدس وإضافتها إلى 12 ; مع إبقاء النتيجة على المكدس

مجموعة الأجهزة

يتمثل الاستخدام الشائع للمكدسات على مستوى البنية في كونها وسيلة لتخصيص الذاكرة والوصول إليها.

البنية الأساسية للمكدس

المكدس النموذجي هو مساحة في ذاكرة الحاسوب ذات نقطة بداية ثابتة وحجم متغير. في البداية، يكون حجم المكدس صفرًا. يشير مؤشر المكدس (عادةً ما يكون على شكل سجل معالج ) إلى آخر موقع تمت الإشارة إليه في المكدس؛ عندما يكون حجم المكدس صفرًا، يشير مؤشر المكدس إلى نقطة بداية المكدس.

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

  • عملية الدفع : يتم تعديل العنوان في مؤشر المكدس حسب حجم عنصر البيانات، ويتم كتابة عنصر البيانات في الموقع الذي يشير إليه مؤشر المكدس.
  • عملية سحب أو إخراج : يتم قراءة عنصر البيانات الموجود في الموقع الحالي الذي يشير إليه مؤشر المكدس، ويتم تحريك مؤشر المكدس بمسافة تتوافق مع حجم عنصر البيانات هذا.

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

قد تشير مؤشرات المكدس إلى نقطة بداية المكدس أو إلى نطاق محدود من العناوين أعلى أو أسفل نقطة البداية (بحسب اتجاه نمو المكدس)؛ ومع ذلك، لا يمكن لمؤشر المكدس تجاوز نقطة البداية. بمعنى آخر، إذا كانت نقطة بداية المكدس عند العنوان 1000، وكان المكدس ينمو نزولًا (باتجاه العناوين 999، 998، وهكذا)، فلا يجب أبدًا زيادة مؤشر المكدس إلى ما بعد 1000 (إلى 1001 أو ما بعدها). إذا تسببت عملية سحب عنصر من المكدس في تجاوز مؤشر المكدس لنقطة البداية، يحدث نقص في سعة المكدس . أما إذا تسببت عملية دفع عنصر إلى المكدس في زيادة أو إنقاص مؤشر المكدس إلى ما بعد الحد الأقصى لسعة المكدس، يحدث تجاوز في سعة المكدس .

قد توفر بعض البيئات التي تعتمد بشكل كبير على المكدسات عمليات إضافية، على سبيل المثال:

  • التكرار : يتم إخراج العنصر العلوي ثم دفعه مرتين، بحيث توجد نسختان من العنصر العلوي السابق في الأعلى.
  • نظرة خاطفة : يتم فحص العنصر العلوي (أو إرجاعه)، لكن مؤشر المكدس وحجم المكدس لا يتغيران (أي أن العنصر يبقى في المكدس). ويمكن تسمية هذه العملية أيضًا بعملية العنصر العلوي .
  • التبديل أو الاستبدال : يتبادل العنصران العلويان في المجموعة أماكنهما.
  • التدوير (أو الدوران) : يتم تحريك العناصر n العلوية في المكدس بشكل دائري. على سبيل المثال، إذا كان n = 3 ، فسيتم نقل العناصر 1 و2 و3 إلى المواضع 2 و3 و1 في المكدس، على التوالي. توجد العديد من أشكال هذه العملية، وأكثرها شيوعًا التدوير إلى اليسار والتدوير إلى اليمين.

غالبًا ما تُصوَّر الأكوام على أنها تنمو من الأسفل إلى الأعلى (مثل الأكوام الحقيقية). ويمكن أيضًا تصويرها وهي تنمو من اليسار إلى اليمين، حيث تكون القمة في أقصى اليمين، أو حتى تنمو من الأعلى إلى الأسفل. والميزة المهمة هي أن تكون قاعدة الكومة ثابتة. الرسم التوضيحي في هذا القسم مثال على تصوير النمو من الأعلى إلى الأسفل: القمة (28) هي "قاعدة" الكومة، لأن "قمة" الكومة (9) هي المكان الذي تُضاف إليه العناصر أو تُزال منه.

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

تفاحة وموزة موز ===تدوير لليمين==> خيار خيار وتفاح
خيار وتفاح موز ===تدوير لليسار==> خيار تفاحة وموزة

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

يؤدي دفع عنصر إلى المكدس إلى تعديل مؤشر المكدس وفقًا لحجم العنصر (إما بالزيادة أو النقصان، حسب اتجاه نمو المكدس في الذاكرة)، ليشير إلى الخلية التالية، ثم ينسخ العنصر العلوي الجديد إلى منطقة المكدس. وبحسب آلية التنفيذ، قد يشير مؤشر المكدس في نهاية عملية الدفع إلى الموقع غير المستخدم التالي في المكدس، أو إلى العنصر العلوي فيه. إذا كان المكدس يشير إلى العنصر العلوي الحالي، فسيتم تحديث مؤشر المكدس قبل دفع العنصر الجديد إليه؛ أما إذا كان يشير إلى الموقع المتاح التالي، فسيتم تحديثه بعد دفع العنصر الجديد .

إن عملية إزالة عنصر من المكدس هي ببساطة عكس عملية الإضافة. يتم إزالة العنصر العلوي من المكدس ويتم تحديث مؤشر المكدس، بترتيب معاكس للترتيب المستخدم في عملية الإضافة.

مكدس في الذاكرة الرئيسية

تتميز العديد من تصميمات وحدات المعالجة المركزية من نوع CISC ، بما في ذلك x86 و Z80 و 6502 ، بسجل مخصص يُستخدم كمؤشر لمكدس الاستدعاءات ، مع تعليمات مخصصة للاستدعاء والإرجاع والدفع والسحب، والتي تُحدّث هذا السجل المخصص ضمنيًا، مما يزيد من كثافة التعليمات البرمجية . كما تتميز بعض معالجات CISC، مثل PDP-11 و 68000 ، بأنماط عنونة خاصة لتنفيذ المكدسات ، وعادةً ما يكون لها مؤشر مكدس شبه مخصص (مثل A7 في 68000). في المقابل، لا تحتوي معظم تصميمات وحدات المعالجة المركزية من نوع RISC على تعليمات مكدس مخصصة، وبالتالي يمكن استخدام معظم السجلات، إن لم يكن جميعها، كمؤشرات مكدس عند الحاجة.

قم بتخزين البيانات في سجلات أو ذاكرة مخصصة

كانت الآلة الحاسبة الجيبية القابلة للبرمجة HP-42S من عام 1988، مثل جميع آلات الحاسبة التي أنتجتها الشركة تقريبًا في ذلك الوقت ، تحتوي على مكدس من 4 مستويات، ويمكنها عرض قيمتين من أصل أربع قيم من سجلات المكدس X وY وZ وT في نفس الوقت بفضل شاشتها ذات السطرين، وهما X وY هنا. في الطرازات اللاحقة مثل HP-48 ، تم زيادة عدد المستويات بحيث أصبح محدودًا فقط بحجم الذاكرة.

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

كان عدد من الحواسيب المركزية والحواسيب الصغيرة عبارة عن حواسيب مكدسة، وأشهرها أنظمة بوروز الكبيرة . ومن الأمثلة الأخرى حواسيب CISC HP 3000 وحواسيب CISC من شركة تانديم كمبيوترز .

تُعد بنية الفاصلة العائمة x87 مثالاً على مجموعة من السجلات المنظمة على شكل مكدس حيث يكون الوصول المباشر إلى السجلات الفردية (بالنسبة إلى الأعلى الحالي) ممكنًا أيضًا .

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

تُعد Sun SPARC و AMD Am29000 و Intel i960 أمثلة على البنى التي تستخدم نوافذ التسجيل داخل مكدس التسجيل كاستراتيجية أخرى لتجنب استخدام الذاكرة الرئيسية البطيئة لوسائط الدوال وقيم الإرجاع.

يوجد أيضًا عدد من المعالجات الدقيقة الصغيرة التي تُنفذ مكدسًا مباشرةً في مكوناتها المادية، وبعض وحدات التحكم الدقيقة لها مكدس ذو عمق ثابت لا يمكن الوصول إليه مباشرةً. ومن الأمثلة على ذلك وحدات التحكم الدقيقة PIC ، و Computer Cowboys MuP21 ، وسلسلة Harris RTX ، و Novix NC4016 . تُنفذ عائلة واحدة على الأقل من عائلات وحدات التحكم الدقيقة، وهي COP400 ، مكدسًا إما مباشرةً في مكوناتها المادية أو في ذاكرة الوصول العشوائي (RAM) عبر مؤشر مكدس، وذلك حسب الجهاز. وقد استُخدمت العديد من المعالجات الدقيقة القائمة على المكدس لتنفيذ لغة البرمجة Forth على مستوى الشفرة المصغرة .

تطبيقات المكدسات

تقييم التعبير وتحليل بناء الجملة

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

التراجع

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

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

إدارة الذاكرة في وقت الترجمة

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

تعتمد العديد من لغات البرمجة على بنية المكدس ، أي أنها تُعرّف معظم العمليات الأساسية (مثل جمع عددين أو طباعة حرف) على أنها تأخذ وسائطها من المكدس، وتضع أي قيم مُعادة فيه. على سبيل المثال، تحتوي لغة PostScript على مكدس للإرجاع ومكدس للمعاملات، بالإضافة إلى مكدس لحالة الرسومات ومكدس للقواميس. كما أن العديد من الآلات الافتراضية تعتمد على بنية المكدس، بما في ذلك آلة p-code وآلة Java الافتراضية .

تستخدم معظم اصطلاحات الاستدعاء -أي الطرق التي تستقبل بها الإجراءات الفرعية معاملاتها وتُعيد نتائجها -مكدسًا خاصًا (يُسمى " مكدس الاستدعاء ") لحفظ معلومات حول استدعاء الإجراءات/الدوال وتداخلها، وذلك للانتقال إلى سياق الدالة المُستدعاة والعودة إلى سياق الدالة المُستدعِية عند انتهاء الاستدعاء. تتبع الدوال بروتوكولًا زمنيًا بين الدالة المُستدعِية والدالة المُستدعاة لحفظ الوسائط وقيمة الإرجاع في المكدس. تُعد المكدسات وسيلةً مهمةً لدعم استدعاءات الدوال المتداخلة أو المتكررة . يستخدم المُصرّف هذا النوع من المكدسات ضمنيًا لدعم عبارات CALL وRETURN (أو ما يُعادلها)، ولا يُمكن للمُبرمج التعامل معه مُباشرةً.

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

خوارزميات فعالة

تستخدم العديد من الخوارزميات مكدسًا (منفصلًا عن مكدس استدعاء الدوال المعتاد في معظم لغات البرمجة) كبنية البيانات الرئيسية التي تنظم بها معلوماتها. وتشمل هذه الخوارزميات ما يلي:

  • مسح غراهام ، خوارزمية لحساب الغلاف المحدب لنظام ثنائي الأبعاد من النقاط. يتم الاحتفاظ بالغلاف المحدب لمجموعة فرعية من المدخلات في مكدس، والذي يُستخدم لإيجاد وإزالة التقعرات في الحدود عند إضافة نقطة جديدة إلى الغلاف. [ 20 ]
  • يستخدم جزء من خوارزمية SMAWK لإيجاد القيم الدنيا للصفوف في مصفوفة رتيبة المكدسات بطريقة مشابهة لمسح غراهام. [ 21 ]
  • جميع القيم الأصغر الأقرب ، وهي مشكلة إيجاد أقرب عدد أصغر من كل عدد في مصفوفة. تستخدم إحدى الخوارزميات لحل هذه المشكلة مكدسًا للاحتفاظ بمجموعة من القيم المرشحة لأقرب قيمة أصغر. لكل موضع في المصفوفة، يُسحب عنصر من المكدس حتى يتم العثور على قيمة أصغر في قمته، ثم تُضاف القيمة الموجودة في الموضع الجديد إلى المكدس. [ 22 ]
  • خوارزمية سلسلة الجوار الأقرب ، هي طريقة للتجميع الهرمي التراكمي تعتمد على الاحتفاظ بمجموعة من المجموعات، كل منها هو أقرب جار للمجموعات السابقة لها في المجموعة. عندما تجد هذه الطريقة زوجًا من المجموعات التي تُعتبر أقرب جيران لبعضها البعض، يتم حذفها ودمجها. [ 23 ]

حماية

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

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

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

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

انظر أيضاً

ملحوظات

  1. ↑ على النقيض من ذلك، تعمل قائمة الانتظار وفقًا لأسلوب "الأول في الداخل، الأول في الخارج"، ويشار إليها بالاختصار FIFO .

مراجع

  1. 1 2 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات (  الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ص 232 – 233. ISBN  0-262-03384-4.
  2. ↑ تورينج، آلان ماثيسون (1946-03-19) [1945]. مقترحات للتطوير في قسم الرياضيات لمحرك الحوسبة الآلي (ACE) .(ملاحظة: تم تقديمها في 19-03-1946 أمام اللجنة التنفيذية للمختبر الفيزيائي الوطني (بريطانيا العظمى).)
  3. ↑ كاربنتر، برايان إدوارد ؛ دوران، روبرت ويليام (1977-01-01) [أكتوبر 1975]. "آلة تورينج الأخرى" . مجلة الكمبيوتر . 20 (3): 269-279 . doi : 10.1093/comjnl/20.3.269 .(11 صفحة)
  4. ↑ بلاو، جيريت آن ؛ بروكس الابن، فريدريك فيليبس (1997). هندسة الحاسوب: المفاهيم والتطور . بوسطن، ماساتشوستس، الولايات المتحدة الأمريكية: شركة أديسون-ويسلي لونغمان للنشر.
  5. ↑ لافوريست، تشارلز إريك (أبريل 2007). "2.1 لوكاسيفيتش والجيل الأول: 2.1.2 ألمانيا: كونراد تسوزه (1910-1995)؛ 2.2 الجيل الأول من الحواسيب المكدسة: 2.2.1 تسوزه Z4". بنية حاسوب مكدس من الجيل الثاني (ملف PDF) (أطروحة). واترلو، كندا: جامعة واترلو . الصفحات 8، 11. مؤرشف (ملف PDF) من الأصل بتاريخ 20 يناير 2022. تم الاطلاع عليه بتاريخ 2 يوليو 2022 . (178 صفحة)
  6. ^ ساملسون، كلاوس (1957) [1955]. تمت كتابته في Internationales Kolloquium über Concerne der Rechentechnik، دريسدن، ألمانيا. مشكلة البرامج (باللغة الألمانية). برلين، ألمانيا: VEB Deutscher Verlag der Wissenschaften . ص 61 – 68. (ملاحظة: تم تقديم هذه الورقة لأول مرة في عام 1955. وهي تصف مكدس الأرقام ( Zahlenkeller )، ولكنها تسميه ذاكرة مساعدة خطية ( linearer Hilfsspeicher ).)
  7. 1 2 3 4 فوث، مايكل؛ ويلك، توماس، محرران. (2015) [2014-11-14]. كتب في جينا، ألمانيا. Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial [ القبو والمكدس والذاكرة التلقائية - هيكل ذو إمكانات ] (PDF) (Tagungsband zum Kolloquium 14. نوفمبر 2014 في جينا). سلسلة GI: ملاحظات المحاضرات في المعلوماتية (LNI) - المواضيع (باللغة الألمانية). المجلد. تي-7. بون، ألمانيا: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. رقم ISBN  978-3-88579-426-4ISSN 1614-3213 . مؤرشف (PDF) من الأصل بتاريخ 12 أبريل 2020. تم الاطلاع عليه بتاريخ 12 أبريل 2020 . (77 صفحة)
  8. ^ باور، فريدريش لودفيج ؛ ساملسون ، كلاوس (30/03/1957). "Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens" (باللغة الألمانية). ميونيخ، ألمانيا: Deutsches Patentamt. دي-بس 1094019 . تم الاسترجاع 2010-10-01 .
  9. ^ باور، فريدريش لودفيج ؛ جوس، جيرهارد [بالألمانية] (1982). المعلوماتية – Eine einführende Übersicht (باللغة الألمانية). المجلد. الجزء 1 (3 طبعة). برلين: سبرينغر-فيرلاغ . ص. 222. ردمك    3-540-11722-9. تم الحصول على براءة اختراع "كيلر" من قبل باور وساملسون في براءات الاختراع الألمانية في 30 مارس 1957.
  10. ^ ساملسون، كلاوس ؛ باور، فريدريش لودفيج (1959). "Sequentielle Formelübersetzung" [ ترجمة الصيغة المتسلسلة ] . Elektronische Rechenanlagen (باللغة الألمانية). 1 (4): 176- 182.
  11. ↑ ساميلسون، كلاوس ؛ باور، فريدريش لودفيج (1960). "ترجمة الصيغ المتسلسلة" . اتصالات رابطة آلات الحوسبة . 3 (2): 76-83 . doi : 10.1145/366959.366968 . S2CID 16646147 . 
  12. ↑ «جائزة IEEE-Computer-Pioneer-Preis – باور، فريدريش ل.» الجامعة التقنية في ميونخ ، كلية علوم الحاسوب. 1989-01-01. مؤرشف من الأصل في 2017-11-07.
  13. ↑ هامبلين، تشارلز ليونارد (مايو 1957). نظام ترميز بدون عناوين قائم على الترميز الرياضي (ملف PDF) (مخطوطة). جامعة نيو ساوث ويلز للتكنولوجيا . الصفحات 121-1 – 121-12 . مؤرشف (ملف PDF) من الأصل بتاريخ 12 أبريل 2020. تم الاطلاع عليه بتاريخ 12 أبريل 2020 . (12 صفحة)
  14. ^ كامرير، فيلهلم [بالألمانية] (1958/12/11). Ziffern-Rechenautomat mit Programmierung nach mathematischem Formelbild (أطروحة التأهيل) (باللغة الألمانية). جينا، ألمانيا: كلية الرياضيات الطبيعية، جامعة فريدريش شيلر . جرة:nbn:de:gbv:27-20130731-133019-7 . بابن:756275237. مؤرشفة من الأصلي بتاريخ 2023-10-14 . تم الاسترجاع 2023-10-14 .(صفحتان + 69 صفحة)
  15. ^ كامرير، فيلهلم [بالألمانية] (1960). Ziffernrechenautomaten . Elektronisches Rechnen und Regeln (باللغة الألمانية). المجلد. 1. برلين، ألمانيا: Akademie-Verlag . 
  16. ↑ بول، جون أ. (1978). خوارزميات لحاسبات RPN ( الطبعة الأولى). كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية: وايلي-إنترساينس ، جون وايلي وأولاده، المحدودة. ISBN  978-0-471-03070-6. إل سي سي إن 77-14977 . 
  17. ↑ جودسي، أتول ب.؛ جودسي، ديبالي أ. (2010-01-01). هندسة الحاسوب . منشورات تقنية. ص 1-56 . ISBN  978-8-18431534-9تم الاطلاع عليه بتاريخ 30 يناير 2015 .
  18. ↑ هورويتز، إليس (1984). أساسيات هياكل البيانات في باسكال . مطبعة علوم الحاسوب . ص 67. 
  19. ↑ باندي ، شريشام (2020). "هياكل البيانات باختصار" . ديف جينيوس . 2020. SSRN 4145204 . 
  20. ↑ غراهام، رونالد "رون" لويس (1972). خوارزمية فعالة لتحديد الغلاف المحدب لمجموعة مستوية منتهية (ملف PDF) . رسائل معالجة المعلومات 1. المجلد 1. الصفحات 132-133 . مؤرشف (ملف PDF) من الأصل بتاريخ 22-10-2022.  
  21. ↑ أغاروال، ألوك؛ كلاوي، ماريا م .؛ موران، شلومو ؛ شور، بيتر ؛ ويلبر، روبرت (1987). " التطبيقات الهندسية لخوارزمية البحث في المصفوفات". Algorithmica . 2 ( 1-4 ): 195-208 . doi : 10.1007/BF01840359 . MR 0895444. S2CID 7932878 .  .
  22. ↑ بيركمان، عمر؛ شيبر، باروخ ؛ فيشكين، عوزي (1993). "خوارزميات متوازية لوغاريتمية مزدوجة مثلى تعتمد على إيجاد جميع القيم الأصغر الأقرب". مجلة الخوارزميات . 14 (3): 344-370 . CiteSeerX 10.1.1.55.5669 . doi : 10.1006/jagm.1993.1018 . .
  23. ↑ مورتاغ، فيون (1983). "دراسة استقصائية للتطورات الحديثة في خوارزميات التجميع الهرمي" (ملف PDF) . مجلة الكمبيوتر . 26 (4): 354-359 . doi : 10.1093/comjnl/26.4.354 ..

للمزيد من القراءة