مكدس (بنية بيانات)
عودة للموسوعةيعهد المكدس (بالإنجليزية: Stack) بأنه بنية معطيات مجردة أومجموعة يمكن فيها القيام بعمليات محددة على العناصر وهي إضافة عنصر حديث إلى المجموعة (تعهد هذه العملية بالدفع (بالإنجليزية: Push)) وإزالة عنصر من المجموعة (تعهد هذه العملية بالطرح (بالإنجليزية: Pop)). تجعل عمليتا الدفع والطرح المكدس بنية معطيات تتمتع بخاصية من يدخل أخيراً يخرج أولاً (بالإنجليزية: Last-In-First-Out) أواختصاراً LIFO. في بنية المعطيات ذات الخاصية LIFOقد يكون آخر عنصر تم إضافته للمجموعة هوأول عنصر تتم إزالته منها. يعهد المكدس بأنه بنية معطيات متسلسلة تتم فيها عمليات الإضافة والحذف عند نهاية واحدة فقط من السلسلة. عادةً ما يشار إلى آخر عنصر تمت إضافته إلى المكدس باسم قمة (بالإنجليزية: Top) المكدس كما يزود المكدس بعملية استراق (بالإنجليزية: Peek) تمكن من فهم قيمة قمة المكدس دون القيام بإزالته منه.
للمكدس سعة محدودة. فإذا كان المكدس ممتلئاً لا يمكن عندئذ القيام بعملية دفع عنصر إليه، وتسبب محاولة القيام بهذه العملية حصول
طفحان (أوما يعهد بتجاوز الحد الأعلى للسعة (بالإنجليزية: Overflow)). تقوم عملية الطرح بإزالة قمة المكدس وتسبب إما الكشف عن العناصر الموجودة داخل المكدس بالتتابع أوالحصول على مكدس فارغ، إذا كان المكدس فارغاً فإن محاولة القيام بالطرح يسبب حصول تجاوز الحد الأدنى للسعة (بالإنجليزية: Underflow).
يعهد المكدس أيضاً بأنه بنية معطيات مقيدة، يعود السبب في ذلك إلى وجود عدد قليل نسبياً من العمليات التي يمكن إجراؤها عليه. كما حتى طبيعة عمليات الدفع والطرح تفرض ترتيباً طبيعياً على العناصر. ذلك حتى ترتيب حذف العناصر من المكدس يعاكس تماماً ترتيب إضافتها إليه. وبالتالي فإن العناصر الموجودة "أسفل" المكدس ستبقى فترةً أطول من نظيرتها الموجودة بالقرب من قمة المكدس.
تاريخ المكدس
اقترح آلان تورنغ عام 1946 بنية المعطيات المكدس لأول مرة كجزء من تصميمه للكومبيوتر كطريقة لاستنادىء والعودة من الإجراءات الفرعية (وقد استخدم مصطلحات "الدفن" (بالإنجليزية: bury) و"النبش" (بالإنجليزية: unbury) للإشارة إلى هذه العمليات). وقد اقترح الألمانيان كلاوس ساملسن وفريدريش باور من جامعة ميونيخ التقنية بنية المعطيات المكدس عام 1955 وتقدما بطلب براءة اختراع له. وقد اقترح الأسترالي تشارلز لينارد هامبلن المبدأ ذاته عام 1957.
العمليات المجردة
يعهد المكدس بأنه بنية معطيات بسيطة تتمتع بعدد من العمليات المجردة والتي يمكن تحقيقها بحرية تامة. أويمكن تعريف المكدس بأنه قائمة خطية من العناصر التي يمكن إضافتها وحذفها عند نهاية واحدة تعهد باسم القمة.
فيما يلي قائمة بتواقيع الطرق الخاصة ببنية معطيات المكدس:
init: -> Stack
push: N x Stack -> Stack
(top: Stack -> (N U ERROR
pop: Stack -> Stack
isempty: Stack -> Boolean
حيث يشير N إلى نمط معطيات عناصر المكدس (في هذه الحالة عدد طبيعي)، ويشير U إلى معامل الاجتماع المنطقي.
وفيما يلي معاني هذه العمليات:
top(init()) = ERROR
top(push(i,s)) = i
()pop(init()) = init
pop(push(i, s)) = s
isempty(init()) = true
isempty(push(i, s)) = false
تحقيق المكدس بلغة الباسكال
أبسط طريقة لتعريف المكدس هي استخدام المصفوفة في تمثيل المكدس، يفترض أن نصرح عن المكدس كما في حالة التصريح عن المسجل بلغة الباسكال :
Const maxstack = 100;
Type stack = record;
Item : array [1..maxstack] of integer;
Top : 0..maxstack;
Var s:stack
من التصريحات المعطاة نجد حتى عناصر المكدس s
الموجودة في المصفوفة s.item
هي أعداد سليمة وأن المكدس لن يحتوي على من أكثر من maxstack
عنصر، ويمكن تغيير عناصر المكدس بتغيير نوع عناصر المصفوفة s.item
.بما حتى top
هوحقل في المسجل stack
فإن قيمة المؤشر الذي يشير على عنصر القمة هوs.top
. إذا كانت قيمة s.top = 3
فهذا يشير على حتى المكدس يحتوي على ثلاثة عناصر هي s.item[1]
وs.item[2]
وs.item[3]
.
إذا طبقنا عملية pop على المكدس فإن قيمة s.top
يجب حتى تعدل لتصبح مساوية 2 ويصبح عنصر القمة هو[s.item[2
، بينما إذا طبقنا عملية push
على المكدس فإن قيمة s.top
يجب حتى تعدل لتصبح مساوية أربعة ويصبح عنصر القمة هو[s.item[4
. للبدء بمكدس فارغ يجب حتى نخط : s.top=0
.
بالاعتماد على ما تجاوز يمكن كتاية التابع (empty(s
بلغة الباسكال كما يلي:
Function Empty(s:stack) : Boolean;
Begin
If s.stop = 0 Then empty =true;
Else empty =false;
End;
ويمكن استنادىء هذا التابع بالشكل :
If Empty(s)
Then {المكدس فارغ
Else {المكدس ليس فارغاً
تحقيق عملية الطرح
ينفذ التابع (Pop(s
الذي يأخذ بعين الاعتبار حالة كون المكدس فارغ كما يلي:
- إذا كان المكدس فارغاً فإنه يطبع رسالة تدل على الخطأ.
- وإلا يتم سحب عنصر القمة من المكدس وإعطاء هذا العنصر إلى البرنامج المستدعي.
ويخط هذا التابع بلغة الباسكال كما يلي :
Function Pop (var s:stack) : integer
Begin
If empty(s) Then
error('stack underflow');
Else
Begin
Pop =s.item[s.top];
s.top =s.top - 1;
End;
End;
تحقيق عملية الدفع
يتم ادخال عنصر إلى المكدس عن طريق زيادة s.top بمقدار 1 ومن ثم إدخال x إلى المصفوفة s.item. يُخط الإجراء الذي يقوم بذلك على الشكل التالي:
Procedure push (var s:stack; x:integer)
Begin
s.top = s.top + 1;
s.item[s.top] = x;
End;
قبل استنادىء الاجراء push يجب التأكد من حتى المكدس غير ممتلئ وبالتالي يجب تعديل الجراء السابق بحيث يصبح كالآتي:
Procedure Push (var s:stack; x:integer)
Begin
If s.top = maxstack Then
error('stack overflow');
Else
Begin
s.top = s.top + 1;
s.item[s.top] = x;
End;
End;
تحقيق المكدس بلغة سي
#include<stdio.h>
#include<stdlib.h>
typedef struct _StackObject {
int stack_top;
int *stack;
StackObject;
int stack_init(StackObject *object, int size);
int stack_destroy(StackObject *object);
void stack_push(StackObject *object, int value);
int stack_pop(StackObject *object);
void stack_inverse(StackObject *object);
int main(int argc, char **argv) {
StackObject stack;
stack_init(&stack, 10);
stack_push(&stack, 11);
stack_push(&stack, 22);
stack_push(&stack, 33);
printf("1- %d\n", stack_pop(&stack));
printf("2- %d\n", stack_pop(&stack));
printf("3- %d\n", stack_pop(&stack));
stack_push(&stack, 11);
stack_push(&stack, 22);
stack_push(&stack, 33);
stack_inverse(&stack);
printf("1- %d\n", stack_pop(&stack));
printf("2- %d\n", stack_pop(&stack));
printf("3- %d\n", stack_pop(&stack));
stack_destroy(&stack);
return(0);
int stack_init(StackObject *object, int size) {
object->stack_top = -1;
object->stack = (int *) malloc(sizeof(int) * size);
if(object->stack == NULL)
return(-1);
return(0);
int stack_destroy(StackObject *object) {
free(object->stack);
return(0);
void stack_push(StackObject *object, int value) {
object->stack_top = object->stack_top++;
object->stack[object->stack_top] = value;
int stack_pop(StackObject *object) {
int temp = object->stack[object->stack_top];
object->stack_top = object->stack_top--;
return(temp);
void stack_inverse(StackObject *object) {
int first = object->stack[0];
int last = object->stack[object->stack_top];
object->stack[0] = last;
object->stack[object->stack_top] = first;
int i;
for(i = 1 ; i < object->stack_top ; i++)
object->stack[object->stack_top - i] = object->stack[i];
استخدام المكدس بلغة سي++
#include <stack>
#include <iostream>
using namespace std;
int main () {
stack <int> a;
int j;
while (1){
cin>>j;
a.push(j);
if (j==0) break;
cout<<endl<<"how many elements you wish to delete ? ";
cin>>j;
cout<<endl<<"the last element was "<<a.top();
cout<<endl<<"after the delete ";
for (int i=1;i<=j;i++){
a.pop();
cout<<a.top();
return 0;
انظر أيضاً
- الرتل
- قائمة حزم أباتشي - ماي سيكيول - بي اتش بي
مراجع
- ^ Newton, David E. (2003). . Philadelphia: Xlibris. صفحة 82. ISBN . مؤرشف من الأصل في 1 يناير 2017. اطلع عليه بتاريخ 28 يناير 2015.
- ^ Ball, John A. (1978). Algorithms for RPN calculators (الطبعة 1). Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley & Sons, Inc. ISBN .
- ^ IEEE-Computer-Pioneer-Preis -- Bauer, Friedrich L., Technical University of Munich, Faculty of Computer Science, (1 January 1989).[وصلة مكسورة]نسخة محفوظة 11 2يناير7 على مسقط واي باك مشين.
التصنيفات: بنية الحاسوب, بنى البيانات, جميع المقالات ذات الوصلات الخارجية المكسورة, مقالات ذات وصلات خارجية مكسورة منذ مايو 2019, قالب أرشيف الإنترنت بوصلات واي باك, مقالات تحتوي نصا بالإنجليزية, وصلات إنترويكي بحاجة لمراجعة, بوابة برمجة الحاسوب/مقالات متعلقة, جميع المقالات التي تستخدم شريط بوابات, قالب تصنيف كومنز بوصلة كما في ويكي بيانات, صفحات تستخدم خاصية P227