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

على غرار مجموعة اللوحات ، لا يمكن الإضافة أو الإزالة إلا في الجزء العلوي.

تمثيل بسيط لوقت تشغيل المكدس مع عمليات الدفع والبوب .

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

Push ، التي تضيف عنصرًا إلى المجموعة ، و
Pop ، الذي يزيل أحدث عنصر مضاف لم تتم إزالته بعد.

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

يتم وصف الترتيب الذي يتم به إضافة عنصر إلى مكدس أو إزالته منه على أنه ما يرد أخيرًا يصرف أولاً ويشار إليه بالاختصار LIFO . ^{[nb 1]} كما هو الحال مع كومة من الكائنات المادية ، فإن هذا الهيكل يجعل من السهل أخذ عنصر من أعلى المكدس ، ولكن الوصول إلى مسند أعمق في المكدس قد يتطلب خلع عدة عناصر أخرى أولاً. ^[1]

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

هناك حاجة إلى مكدس لتنفيذ بحث العمق أولاً .

التاريخ

دخلت Stacks أدب علوم الكمبيوتر في عام 1946 ، عندما استخدم Alan M. ^[2]^[3] تم تنفيذ الروتينات الفرعية بالفعل في Z4 الخاص بـ Konrad Zuse في عام 1945.

كلاوس ساملسون وفريدريك إل باور من جامعة ميونيخ التقنية اقترحوا فكرة المكدس في عام 1955 ^[4]^[5] وقدموا براءة اختراع في عام 1957. ^[6]^[7]^[8]^[9] في مارس 1988 ، والتي بموجبها وقت وفاة Samelson ، حصل Bauer على جائزة IEEE Computer Pioneer لاختراع مبدأ المكدس. ^[10]^[5] تم تطوير مفاهيم مماثلة بشكل مستقل بواسطة تشارلز ليونارد هامبلين في النصف الأول من عام 1954 ^[11] وويلهلم كاميرر [ دي ] في عام 1958. ^[12]^[13]

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

العمليات غير الضرورية

في العديد من التطبيقات ، يكون للمكدس عمليات أكثر من عمليات "الدفع" و "الفرقعة" الأساسية. من الأمثلة على العمليات غير الضرورية "أعلى المكدس" أو "نظرة خاطفة" ، والتي تراقب العنصر العلوي دون إزالته من المكدس. ^[16] يمكن القيام بذلك باستخدام "فرقعة" متبوعة بـ "دفع" لإعادة نفس البيانات إلى المكدس ، لذلك لا تعتبر عملية أساسية. إذا كان المكدس فارغًا ، فستحدث حالة underflow عند تنفيذ عمليات "stack top" أو "pop". بالإضافة إلى ذلك ، توفر العديد من التطبيقات التحقق مما إذا كان المكدس فارغًا ويعيد حجمه.

أكوام البرمجيات

التنفيذ

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

صفيف

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

كومة الهيكل :
    الحجم الأقصى: عدد صحيح
    أعلى: عدد صحيح
    العناصر: مجموعة من العناصر

إجراء تهيئة (stk: stack ، الحجم: عدد صحيح):
    stk.items ← مصفوفة جديدة من عناصر الحجم فارغة في البداية
    stk.maxsize ← الحجم
    stk.top ← 0

تضيف عملية الدفع عنصرًا وتزيد المؤشر العلوي ، بعد التحقق من الفائض:

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

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

انبثاق
     الإجراء (stk: stack): إذا كان stk.top = 0:
        الإبلاغ عن خطأ تحت التدفق
    آخر :
        stk.top ← stk.top - 1
        r ← stk.items [stk.top]
        عودة ص

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

قائمة مرتبطة

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

إطار الهيكل :
    البيانات: العنصر
    التالي: إطار أو لا شيء

كومة الهيكل :
    الرأس: إطار أو لا شيء
    الحجم: عدد صحيح

تهيئة الإجراء (stk: stack):
    stk.head ← لا شيء
    حجم stk. ← 0

يحدث دفع وفرقعة العناصر في رأس القائمة ؛ تجاوز السعة غير ممكن في هذا التنفيذ (ما لم يتم استنفاد الذاكرة):

دفع الإجراء (stk: stack ، x: item):
    newhead ← إطار جديد
    newhead.data ← x
    newhead.next ← stk.head
    stk.head ← newhead
    حجم stk.size ← stk.size + 1

انبثاق
     الإجراء (stk: stack): إذا كان stk.head = لا شيء:
        الإبلاغ عن خطأ تحت التدفق
    r ← stk.head.data
    stk.head ← stk.head.next
    حجم الملف ← stk.size - 1
    عودة ص

الأكوام ولغات البرمجة

بعض اللغات ، مثل Perl و LISP و JavaScript و Python ، تجعل عمليات المكدس تعمل بالدفع والبوب في أنواع القائمة / المصفوفات القياسية الخاصة بها. تم تصميم بعض اللغات ، لا سيما تلك الموجودة في عائلة Forth (بما في ذلك PostScript ) ، حول حزم المعرفة بلغة والتي تكون مرئية مباشرة ويتلاعب بها المبرمج.

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

>  ( مكدس setf  ( قائمة 'أ ' ب 'ج )) ؛؛ اضبط المتغير "المكدس" ( A B C ) > ( pop stack ) ؛ get top (أقصى اليسار) ، يجب تعديل المكدس A > stack ؛؛ تحقق من قيمة المكدس ( B C ) > ( دفع ' المكدس الجديد ) ؛؛ ادفع قمة جديدة على المكدس ( NEW B C )

العديد من أنواع حاويات مكتبة C ++ القياسية لها عمليات push_back و pop_back مع دلالات LIFO ؛ بالإضافة إلى ذلك ، تتكيف فئة قالب المكدس مع الحاويات الموجودة لتوفير واجهة برمجة تطبيقات مقيدة بعمليات دفع / فرقعة فقط. تحتوي PHP على فئة SplStack . تحتوي مكتبة Java على فصل دراسي هو تخصص لـ . فيما يلي مثال لبرنامج بلغة جافا ، باستخدام تلك الفئة. StackVector

استيراد  java.util.Stack ؛

class  StackDemo  { 
    public  static  void  main ( String [ ] args )  { 
        Stack <String> stack = new Stack <String> ( ) ؛ _ كومة . دفع ( "أ" ) ؛ // أدخل "A" في مكدس المكدس . دفع ( "ب" ) ؛ // أدخل "B" في مكدس المكدس . دفع ( "C" ) ؛ // أدخل "C" في مكدس المكدس .    
            
            
            
        دفع ( "D" ) ؛     // أدخل "D" في نظام المكدس 
        . خارج . println ( stack . peek ()) ؛ // يطبع الجزء العلوي من المكدس ("D") المكدس . البوب () ؛ // إزالة المكدس العلوي ("D") . البوب () ؛ // إزالة الجزء العلوي التالي ("C") } }

مكدس الأجهزة

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

العمارة الأساسية للمكدس

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

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

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

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

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

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

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

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

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

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

تفاح الخيار
موز === تناوب إلى اليسار ==> خيار
التفاح والموز

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

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

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

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

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

تكديس في السجلات أو الذاكرة المخصصة

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

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

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

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

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

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

تطبيقات المداخن

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

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

التراجع

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

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

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

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

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

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

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

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

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

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

الأمن

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

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

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

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

انظر أيضا

ملاحظات

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

المراجع

^ ^أ ^ب كورمين ، توماس هـ . ليسرسون ، تشارلز إي . ريفيست ، رونالد ل . شتاين ، كليفورد (2009) [1990]. مقدمة في الخوارزميات (الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ص 232 - 233. رقم ISBN 0-262-03384-4.
^ تورينج ، آلان ماتيسون (1946/03/19) [1945]. مقترحات للتطوير في قسم الرياضيات لمحرك الحوسبة الآلية (ACE) .(ملحوظة. تم تقديمها بتاريخ 1946-03-19 أمام اللجنة التنفيذية للمختبر الفيزيائي الوطني (بريطانيا العظمى).)
^ كاربنتر ، بريان إدوارد ؛ دوران ، روبرت ويليام (1 يناير 1977) [أكتوبر 1975]. "آلة تورينج الأخرى" . مجلة الكمبيوتر . 20 (3): 269-279. دوى : 10.1093 / comjnl / 20.3.269.003 .(11 صفحة)
^ كلاوس ساملسون (1957) [1955]. كُتب في الندوة الدولية حول مشاكل الحوسبة ، دريسدن ، ألمانيا. مشاكل تكنولوجيا البرمجة (في المانيا). برلين ، ألمانيا: ناشر العلوم الألماني VEB . ص 61 - 68.(ملاحظة: تم تقديم هذه الورقة لأول مرة في عام 1955. وهي تصف مجموعة أرقام ( Zahlenkeller ) ، لكنها تسميها الذاكرة المساعدة الخطية ( الخطي Hilfsspeicher ).)
^ ^أ ^ب فوث ، مايكل ؛ ويلك ، توماس ، محرران. (2015) [2014-2014]. مكتوب في جينا ، ألمانيا. قبو ومكدس وذاكرة تلقائية - بنية ذات إمكانات [ قبو ومكدس وذاكرة تلقائية - بنية ذات إمكانات ] (PDF) (وقائع الندوة في 14 نوفمبر 2014 في جينا). سلسلة GI: ملاحظات محاضرة في المعلوماتية (LNI) - موضوعات (باللغة الألمانية). المجلد. T-7. بون ، ألمانيا: Gesellschaft für Informatik (GI) / Koellen Druck + Verlag GmbH. رقم ISBN 978-3-88579-426-4. ISSN 1614-3213 . أرشفة (PDF) من الأصل بتاريخ 2020-04-12 . تم الاسترجاع 2020/04/12 . [1] (77 صفحة)
^ باور ، فريدريش لودفيج ؛ ساميلسون ، كلاوس (1957/03/30). "طريقة المعالجة التلقائية للبيانات المشفرة وآلة الحوسبة لتنفيذ الطريقة" (باللغة الألمانية). ميونيخ ، ألمانيا: مكتب براءات الاختراع الألماني. DE-PS 1094019 . تم الاسترجاع 2010-10-01 .
^ باور ، فريدريش لودفيج ؛ جووس ، غيرهارد (بالألمانية] (1982). المعلوماتية - نظرة عامة تمهيدية (في المانيا). المجلد. الجزء 1 (3 ed.). برلين: Springer-Verlag . ص. 222- رقم ISBN 3-540-11722-9. تم تقديم مصطلح "كيلر" لهذا الغرض من قبل باور وساميلسون في طلب براءة اختراع ألماني بتاريخ 30 مارس 1957.
^ كلاوس ساملسون . باور ، فريدريش لودفيج (1959). "ترجمة الصيغة المتسلسلة". أنظمة الحوسبة الإلكترونية (في المانيا). 1 (4): 176-182.
^ كلاوس ساملسون . باور ، فريدريش لودفيج (1960). "ترجمة الصيغة المتسلسلة". اتصالات من ACM . 3 (2): 76-83. دوى : 10.1145 / 366959.366968 . S2CID 16646147 .
^ "IEEE-Computer-Pioneer-Preis - Bauer، Friedrich L." جامعة ميونخ التقنية ، كلية علوم الحاسب. 1989-01-01. مؤرشفة من الأصلي في 2017-11-07.
^ هامبلين ، تشارلز ليونارد (مايو 1957). مخطط تشفير بدون عنوان يعتمد على تدوين رياضي (PDF) (نص مكتوب). جامعة نيو ساوث ويلز للتكنولوجيا . ص 121-1 - 121-12. أرشفة (PDF) من الأصل بتاريخ 2020-04-12 . تم الاسترجاع 2020/04/12 . (12 صفحة)
^ كاميرر ، فيلهلم [بالألمانية] (1958). آلة حاسبة رقمية مع البرمجة حسب الصيغ الرياضية (أطروحة التأهيل) (باللغة الألمانية). جامعة فريدريش شيلر ، جينا ، ألمانيا.
^ كاميرر ، فيلهلم [بالألمانية] (1960). حاسبات رقمية . الحسابات والقواعد الإلكترونية (باللغة الألمانية). المجلد 1. برلين ، ألمانيا: Akademie-Verlag .
^ الكرة ، جون أ. (1978). خوارزميات لآلات حاسبة RPN (1 ed.). كامبريدج ، ماساتشوستس ، الولايات المتحدة الأمريكية: Wiley-Interscience ، John Wiley & Sons ، Inc. ISBN 978-0-471-03070-6.
^ جودسي ، أتول ب. ؛ جودسي ، ديبالي أ. (2010-01-01). هندسة الحاسوب . المنشورات الفنية. ص. 1-56. رقم ISBN 978-8-18431534-9. تم الاسترجاع 30 يناير 2015 .
^ هورويتز ، إليس (1984). أساسيات هياكل البيانات في باسكال . مطبعة علوم الكمبيوتر . ص. 67.
^ جراهام ورونالد "رون" لويس (1972). خوارزمية فعالة لتحديد الهيكل المحدب لمجموعة مستوية محدودة (PDF) . رسائل معالجة المعلومات 1. المجلد. 1. ص 132 - 133. مؤرشف (PDF) من الأصل بتاريخ 2022-10-22.
^ أجروال ، ألوك ؛ كلاوي ، ماريا م . شلومو موران ؛ شور ، بيتر ؛ ويلبر ، روبرت (1987). "التطبيقات الهندسية لخوارزمية البحث عن المصفوفة". الخوارزمية . 2 (1-4): 195-208. دوى : 10.1007 / BF01840359 . السيد 0895444 . S2CID 7932878 . .
^ بيركمان ، عمر. شيبر ، باروخ ؛ فيشكين ، عوزي (1993). "الخوارزميات المتوازية اللوغاريتمية المزدوجة المثلى بناءً على إيجاد جميع القيم الأصغر الأقرب". مجلة الخوارزميات . 14 (3): 344-370. سيتسيركس 10.1.1.55.5669 . دوى : 10.1006 / jagm.1993.1018 . .
^ مرتاغ ، فيون (1983). "مسح للتطورات الحديثة في خوارزميات المجموعات الهرمية" (PDF) . مجلة الكمبيوتر . 26 (4): 354–359. دوى : 10.1093 / comjnl / 26.4.354 . .

تحتوي هذه المقالة على مواد ذات ملكية عامة من Paul E. Black. "المكدس المربوط" . قاموس الخوارزميات وهياكل البيانات . نيست .

قراءات إضافية

دونالد كنوث . فن برمجة الحاسوب ، المجلد الأول: الخوارزميات الأساسية ، الطبعة الثالثة. أديسون ويسلي ، 1997. ISBN 0-201-89683-4 . القسم 2.2.1: Stacks، Queues، and Deques، pp.238–243.
لانجماك ، هانز [بالألمانية] (2015) [2014-2014]. كتب في كيل ، ألمانيا. يعمل فريدريش إل باور وكلاوس ساملسون في الخمسينيات من القرن الماضي حول إدخال مصطلحات مبدأ القبو والقبو الآلي ] ( PDF) (في ألمانيا جينا ، ألمانيا: معهد علوم الكمبيوتر ، جامعة كريستيان ألبريشت في كيل. ص 19 - 29. أرشفة (PDF) من الأصل بتاريخ 2022-11-14 . تم الاسترجاع 2022-11-14 . (11 صفحة) (ملحوظة منشورة في Fothe & Wilke .)
جووس ، غيرهارد [بالألمانية] (2017/08/07). تاريخ المعلوماتية في البلدان الناطقة بالألمانية - لغات البرمجة وتصميم المترجم ] ( PDF) (في ألمانيا). كارلسروه ، ألمانيا: كلية علوم الكمبيوتر ، معهد كارلسروه للتكنولوجيا (KIT). أرشفة (PDF) من الأصل بتاريخ 2022-05-19 . تم الاسترجاع 2022-11-14 .(11 صفحة)

روابط خارجية

[NB1-1] على النقيض من ذلك ، تعمل قائمة الانتظار أولاً في البداية ، ويشار إليها بالاختصار FIFO .

[clrs-2] أ ^ب كورمين ، توماس هـ . ليسرسون ، تشارلز إي . ريفيست ، رونالد ل . شتاين ، كليفورد (2009) [1990]. مقدمة في الخوارزميات (الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ص 232 - 233. رقم ISBN 0-262-03384-4.

[Turing_1945-3] تورينج ، آلان ماتيسون (1946/03/19) [1945]. مقترحات للتطوير في قسم الرياضيات لمحرك الحوسبة الآلية (ACE) .(ملحوظة. تم تقديمها بتاريخ 1946-03-19 أمام اللجنة التنفيذية للمختبر الفيزيائي الوطني (بريطانيا العظمى).)

[Carpenter_1977-4] كاربنتر ، بريان إدوارد ؛ دوران ، روبرت ويليام (1 يناير 1977) [أكتوبر 1975]. "آلة تورينج الأخرى" . مجلة الكمبيوتر . 20 (3): 269-279. دوى : 10.1093 / comjnl / 20.3.269.003 .(11 صفحة)

[Samelson_1955-5] كلاوس ساملسون (1957) [1955]. كُتب في الندوة الدولية حول مشاكل الحوسبة ، دريسدن ، ألمانيا. مشاكل تكنولوجيا البرمجة (في المانيا). برلين ، ألمانيا: ناشر العلوم الألماني VEB . ص 61 - 68.(ملاحظة: تم تقديم هذه الورقة لأول مرة في عام 1955. وهي تصف مجموعة أرقام ( Zahlenkeller ) ، لكنها تسميها الذاكرة المساعدة الخطية ( الخطي Hilfsspeicher ).)

[Wilke_2015-6] أ ^ب فوث ، مايكل ؛ ويلك ، توماس ، محرران. (2015) [2014-2014]. مكتوب في جينا ، ألمانيا. قبو ومكدس وذاكرة تلقائية - بنية ذات إمكانات [ قبو ومكدس وذاكرة تلقائية - بنية ذات إمكانات ] (PDF) (وقائع الندوة في 14 نوفمبر 2014 في جينا). سلسلة GI: ملاحظات محاضرة في المعلوماتية (LNI) - موضوعات (باللغة الألمانية). المجلد. T-7. بون ، ألمانيا: Gesellschaft für Informatik (GI) / Koellen Druck + Verlag GmbH. رقم ISBN 978-3-88579-426-4. ISSN 1614-3213 . أرشفة (PDF) من الأصل بتاريخ 2020-04-12 . تم الاسترجاع 2020/04/12 . [1] (77 صفحة)

[Bauer_1957-7] باور ، فريدريش لودفيج ؛ ساميلسون ، كلاوس (1957/03/30). "طريقة المعالجة التلقائية للبيانات المشفرة وآلة الحوسبة لتنفيذ الطريقة" (باللغة الألمانية). ميونيخ ، ألمانيا: مكتب براءات الاختراع الألماني. DE-PS 1094019 . تم الاسترجاع 2010-10-01 .

[Bauer_1982-8] باور ، فريدريش لودفيج ؛ جووس ، غيرهارد (بالألمانية] (1982). المعلوماتية - نظرة عامة تمهيدية (في المانيا). المجلد. الجزء 1 (3 ed.). برلين: Springer-Verlag . ص. 222- رقم ISBN 3-540-11722-9. تم تقديم مصطلح "كيلر" لهذا الغرض من قبل باور وساميلسون في طلب براءة اختراع ألماني بتاريخ 30 مارس 1957.

[Samelson_1959-9] كلاوس ساملسون . باور ، فريدريش لودفيج (1959). "ترجمة الصيغة المتسلسلة". أنظمة الحوسبة الإلكترونية (في المانيا). 1 (4): 176-182.

[Samelson_1960-10] كلاوس ساملسون . باور ، فريدريش لودفيج (1960). "ترجمة الصيغة المتسلسلة". اتصالات من ACM . 3 (2): 76-83. دوى : 10.1145 / 366959.366968 . S2CID 16646147 .

[IEEE_1989-11] "IEEE-Computer-Pioneer-Preis - Bauer، Friedrich L." جامعة ميونخ التقنية ، كلية علوم الحاسب. 1989-01-01. مؤرشفة من الأصلي في 2017-11-07.

[Hamblin_1957-12] هامبلين ، تشارلز ليونارد (مايو 1957). مخطط تشفير بدون عنوان يعتمد على تدوين رياضي (PDF) (نص مكتوب). جامعة نيو ساوث ويلز للتكنولوجيا . ص 121-1 - 121-12. أرشفة (PDF) من الأصل بتاريخ 2020-04-12 . تم الاسترجاع 2020/04/12 . (12 صفحة)

[Kämmerer_1958-13] كاميرر ، فيلهلم [بالألمانية] (1958). آلة حاسبة رقمية مع البرمجة حسب الصيغ الرياضية (أطروحة التأهيل) (باللغة الألمانية). جامعة فريدريش شيلر ، جينا ، ألمانيا.

[Kämmerer_1960-14] كاميرر ، فيلهلم [بالألمانية] (1960). حاسبات رقمية . الحسابات والقواعد الإلكترونية (باللغة الألمانية). المجلد 1. برلين ، ألمانيا: Akademie-Verlag .

[Ball_1978-15] الكرة ، جون أ. (1978). خوارزميات لآلات حاسبة RPN (1 ed.). كامبريدج ، ماساتشوستس ، الولايات المتحدة الأمريكية: Wiley-Interscience ، John Wiley & Sons ، Inc. ISBN 978-0-471-03070-6.

[Godse_2010-16] جودسي ، أتول ب. ؛ جودسي ، ديبالي أ. (2010-01-01). هندسة الحاسوب . المنشورات الفنية. ص. 1-56. رقم ISBN 978-8-18431534-9. تم الاسترجاع 30 يناير 2015 .

[Horowitz_1984-17] هورويتز ، إليس (1984). أساسيات هياكل البيانات في باسكال . مطبعة علوم الكمبيوتر . ص. 67.

[Graham_1972-18] جراهام ورونالد "رون" لويس (1972). خوارزمية فعالة لتحديد الهيكل المحدب لمجموعة مستوية محدودة (PDF) . رسائل معالجة المعلومات 1. المجلد. 1. ص 132 - 133. مؤرشف (PDF) من الأصل بتاريخ 2022-10-22.

[Aggarwal_1987-19] أجروال ، ألوك ؛ كلاوي ، ماريا م . شلومو موران ؛ شور ، بيتر ؛ ويلبر ، روبرت (1987). "التطبيقات الهندسية لخوارزمية البحث عن المصفوفة". الخوارزمية . 2 (1-4): 195-208. دوى : 10.1007 / BF01840359 . السيد 0895444 . S2CID 7932878 . .

[Omer_1993-20] بيركمان ، عمر. شيبر ، باروخ ؛ فيشكين ، عوزي (1993). "الخوارزميات المتوازية اللوغاريتمية المزدوجة المثلى بناءً على إيجاد جميع القيم الأصغر الأقرب". مجلة الخوارزميات . 14 (3): 344-370. سيتسيركس 10.1.1.55.5669 . دوى : 10.1006 / jagm.1993.1018 . .

[Martagh_1983-21] مرتاغ ، فيون (1983). "مسح للتطورات الحديثة في خوارزميات المجموعات الهرمية" (PDF) . مجلة الكمبيوتر . 26 (4): 354–359. دوى : 10.1093 / comjnl / 26.4.354 . .

[nb 1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]