المكدس Stack

ماهو الـ .Stack…؟!! وما أنواع الـ Stack…؟! و ما التطبيقات التي يمكن أن نستخدم فيها Stack …؟؟!! وما هي عمليات الـ Stack..؟؟!! وكيف يتم تنفيذ الـ Stack من خلال التعليمات البرمجية ..؟؟!!

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

تعريف الـ Stack ؟

في هذا الجزء سنتعرف على :

مفهوم الـ Stack.
أنواع الـ Stack.
خصائص الـ Stack
مزايا وعيوب Stack.

مفهوم الـ Stack

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

ومنها هذا نستنتج أن في Stack أول عنصر يتم اضافته هو آخر عنصر يمكن الوصول له والعكس بمعنى آخر عنصر تتم إضافته هو أول عنصر يتم الوصول إليه. فـ Stack في البرمجة يعرف بخوارزمية تقوم بإنشاء قائمة من العناصر التي يمكن الوصول إليها فقط من نهاية القائمة ، والتي تسمى Top of the Stack .فقد نسمي الترتيب في Stack :

LIFO (Last In First Out) و يشير LIFO إلى أن العنصر الذي تم إدراجه أخيرًا ، يخرج أولاً
أو FILO (First In Last Out) . ويشير FILO إلى أن العنصر الذي تم إدراجه أولاً ، يخرج أخيرًا.

الـ Stack شائع الاستخدام في معظم لغات البرمجة. وهو عبارة عن نوع من قوائم البيانات الخطية و وهياكل البيانات الخطية linear data structure التي تتبع عناصرها ترتيبًا معينًا. في Stack يتم الترتيب بناء على تنفيذ العمليات به.

و لتنفيذ الـ Stack، يلزم الاحتفاظ بالمؤشر إلى أعلى الـ Stack ،والمقصود بـ Top of the Stack المؤشر الذي يتم من خلاله الوصول إلى العناصر وإدراجها وحذفها في Stack . إنه المؤشر إلى أعلى عنصر في Stack أي آخر عنصر يتم إدراجه.

أنواع الـ Stack

Register Stack

الـ Stack المسجل و يستخدم للتعامل مع كمية صغيرة من البيانات فقط. فهو يكون محدودًا الارتفاع نظرًا لأن حجم Stack التسجيل صغير جدًا مقارنة بالنوع الآخر الخاص بالذاكرة.

Memory Stack

و يمكن لهذا النوع من الـ Stack معالجة كمية كبيرة من بيانات الذاكرة. ارتفاع هذا النوع مرن لأنه يشغل كمية كبيرة من بيانات الذاكرة.

خصائص الـ Stack

يمكن تلخيص خصائص الـ Stack فيما يلي :

سعة Stack هي عدد العناصر التي يمكن للـ Stack الاحتفاظ بها.
يقبل Stack القيمة الخالية كقيمة صالحة ويسمح بالعناصر المكررة.
عند إضافة العناصر إلى Stack ، يتم زيادة السعة تلقائيًا حسب الحاجة من خلال إعادة التخصيص.
إذا كان عدد عناصر للـ Stack أقل من سعة Stack ، فإن Push هي عملية O(1) . أما إذا كانت السعة بحاجة إلى زيادة لاستيعاب العنصر الجديد ، فإن Push يصبح عمليةO(n) ، حيث n هي عدد عناصر الـ Stack .
وتكون عملية Pop O(1) .

للمزيد عن عمليات O(n) أو O(1) انظر مقال عن كفاءة الخوارزميات و الـ Big-O.

مزايا وعيوب Stack

تعدد مزايا الـ Stack ومنها :

يساعد Stack في إدارة البيانات التي تتبع أسلوب LIFO.
تعد Stacks أكثر أمانًا وموثوقية لأنها لا تتلف بسهولة.
تُستخدم Stacks لإدارة الذاكرة بشكل منهجي.
تتميز Stacks بإدارة فعالة للدوال Functions عندما يتم استدعاء دالة ، يتم تخزين المتغيرات المحلية والـ Parameters الدالة الأخرى في Stack ويتم إتلافها تلقائيًا بمجرد إرجاعها من الدالة .
يتم استخدام Stack في العديد من الأجهزة الافتراضية مثل JVM.
يقوم Stack بتنظيف Objects تلقائيًا.
يسمح Stack بالتحكم في تخصيص الذاكرة وإلغاء تخصيصها.

أيضاً يوجد للـ Stack بعض العيوب ومنها :

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

تطبيقات و استخدامات الـ Stack

تعتبر الـ Stack من البنى الأساسية في العديد من التطبيقات، فماهي استخدامات Stack ؟ يستخدم Stack في العديد من المجالات، بدءًا من التطبيقات البسيطة إلى التطبيقات المعقدة، مثل اللغات البرمجية وأنظمة التشغيل والمواقع الإلكترونية.

اللغات البرمجية: تستخدم الـ Stack في العديد من لغات البرمجة، مثل Java و C++ و C# وغيرها، وتستخدم الـ Stack في تنفيذ العديد من العمليات المختلفة، مثلاً:
- يستخدم stack في مطابقة الأوسمة tags في HTML و XML.
- عمل وظيفة التراجع في أي محرر نصوص.
- تساعد Stacks في عكس أي مجموعة من البيانات أو نصوص strings .
- عمليات التحويل من Infix إلى postfix أو العكس أو من Infix الى Prefix أو العكس .
- يستخدم Stack مع استخدام المعاملات والعمليات لتقييم التعبيرات الحسابية .
- تعد Stacks مفيدة لاستدعاءات الدوال ، وتخزين السجلات و نشيط وحذفها بعد ارجاع القيم من الدوال .
أنظمة التشغيل: تستخدم أنظمة التشغيل الـ Stack في تخزين معلومات العمليات المختلفة، مثل العناوين والبيانات والمتغيرات.
المواقع الإلكترونية: تستخدم الـ Stack في العديد من المواقع الإلكترونية لتنفيذ العمليات المختلفة، مثل تسجيل الدخول وتخزين المعلومات.

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

العمليات على Stack

عند السؤال كيف يعمل المكدس Stack ؟ نجد أن ترتيب العناصر في Stack يعتمد على العمليات التي تنفذ ونعني هنا عمليات Stack الأساسية وهي الإضافة Push والحذف Pop كما يمكن إجراء بعض العمليات الإضافية على Stack مثل إرجاع اخر قيمة و ومعرفة طول الـ Stack والتحقق من وجود عناصر أو لا. وهنا ثميل لأهم الدوال من أجل إجراء عمليات على Stack :

العمليات الأساسية على Stack

push() إدراج عنصر إلى Stack .
pop() حذف عنصر من Stack .

وهنا بعض العمليات الإضافية على Stack

peek() إرجاع آخر عنصر تم ادراجه في Stack .
size() إرجاع حجم الـ Stack.
top() إرجاع ترتيب العنصر الأخير في Stack.
isEmpty() التحقق فيما اذا كان الـ Stack فارغ أو لا..
isFull() التحقق فيما إذا كان الـ Stack ممتلئ أو لا. .

ويوضح الشكل مثال على العمليات الأساسية في Stack

stack push and pop operations عمليات stack

Push Operation in Stack

في Push يتم التأكد من فيما إذا كان الـ Stack ممتلئ او لا فإن كان ممتلئ سنحصل على فائض Overflow. لتكون خطوات عملية إضافة عنصر الى Stack كتالي :

عند إنشاء الـ Stack يتم تعيين قيمة top بـ -1 ( أي top < max size of Stack في الحجم الثابت للـ Stack ).
قبل اضافة العنصر تحقق من أن الـ Stack غير ممتلئ .إذا حاولنا إدخال العنصر وكان Stack ممتلئًا ، عندئذٍ تحدث حالة الفائض Overflow.
عندما تتم إضافة العنصر يتم زياد top بمقدار 1 ( top=top+1) وسيكون موقع العنصر الجديد يساوي top .

سنتمكن من إضافة العناصر إلى stack حتى تصل قيمة الـ top الى الحجم الأقصى للـ Stack ( max size of Stac)

وتتضح عملية push في الشكل التالي :

وهنا خوارزمية عملية Push على Stack

...........
 if stack is full
    return 
else  
 increment top
 stack[top] assign value
...........

Pop Operation in Stack

وتتم عملية الحذف Pop للعنصر الأخير كتالي :

قبل حذف عنصر من Stack نتحقق فيما إذا كان الـ Stack فارغ فإذا حاولنا حذف عنصر من Stack فارغ فسنحصل على حالة Underflow .
وان لم الـ Stack فارغ هنا سيتم حذف العنصر في الموقع الذي يساوي top بعد الحذف سنقوم بإنقاص قيمة 1 من top ( top=top-1 )

وتتضح عملية Pop في الشكل التالي :

وهنا خوارزمية عملية Pop على Stack

...........
if stack is empty
    return
else
 store value of stack[top]
 decrement top
 return value
...........

تنفيذ الـ Stack في C#

يمكن تنفيذ Stack بعدة أشكال على سبيل المثال يمكن استخدام المصفوفات Array أو القوائم المترابطة LinkedList سنرى فيما يلي تنفيذ Stack بواسطة الـ Array و LinkedList من خلال تعليمات لغة .C#

أولاً : تطبيق Stack من خلال Array

سيكون هذا ببناء Class للـ Stack ويحتوى على العمليات الممكن إجراءها على Stack كالتالي:

class SStack 
    {
        private int Max; 
        private int top;
        private object[] items;
        public SStack (int max)
        {
            Max = max;
            top = -1;
            items = new object[Max];
        }
        public SStack()
        {
            Max = 5;
            top = -1;
            items = new object[Max];
        }
        //check the stack is full
        public bool isFull()
        { 
            return ( top == Max -1);
        }
        //check the stack is empty
        public bool isEmpty()
        {
             return (top == -1);      
        }
        //push method for adding items to the stack
        public void Push( object data)
        {
            if (isFull())
                throw new Exception ("stack is full");
                    top++;
                items[top] = data; 
        }
        //pop method for removing items from the stack
        public object pop()
        {
            if(isEmpty())
                throw new Exception("Stack is empty");
            object data = items[top];
            top--;
            return data;
        }
        //peek method that return the value of last item adding to the stack 
        public object peek()
        {
            if (isEmpty()) 
                throw new Exception("Stack is empty");
                    
            else 
                return items[top];
         }
         //return the stack size
        public int size()
        {
            return items.Count();
        }
         //print the stack items 
        public void print()
        {
            if (isEmpty()) 
                throw new Exception("Stack is empty");
            else 
                {
                    for (int i = 0; i &lt;= top; i++) 
                        Console.Write(" "+items[i]);
                    Console.WriteLine();
                }
        }       
}

نلاحظ في المثال السابق طريقة تنفيذ العمليات للـ Stack في الدالتين push() و pop() كما عرض المثال طريقة تنفيذ عمليات أخرى مثل isFull() و isEmpty() للتحقق من وجود عناصر للـ Stack وتنفيذ الدالة peek() التي ترجع قيمة آخر عنصر تم اضافتة للـ Stack.

ويتم استخدام هذا الـ class في تنفيذ الـ Stack على Array كالتالي :

...........
 public static void Main( String [] args)
        {
           string[] names = {"Mona", "Reem", "Sara", "Nora"};
           SStack stackNames = new SStack(names);
            //Add itemes to stack 
            for(int i =0; i < names.Length; i++)
                stackNames.Push(names[i]);

            //print the stack items 
            stackNames.print(); 
            //trturn the top item 
            Console.WriteLine(stackNames.peek());
            //stack size 
            Console.WriteLine(stackNames.size());
            //remove the top 
            stackNames.pop();
            Console.WriteLine(stackNames.peek()) ; 
            stackNames.print(); 

            Console.ReadKey();     
...........

الكود بالكامل متوفر على الرابط هنا

و لمراجعة الـ Array في لغة C# يمكن الاطلاع على المقالات ( المصفوفات Arrays و العمل مع Class Array )

ثانياً : تطبيق الـ Stack بواسطة LinkedList

هنا سنقوم ببنايمكن ايضاً تنفيذ الـ Stack بواسطة القوائم المترابطة LinkedList وهذا يتم بناء Node class للبناء العقد و Class للعمليات على LinkedList كما عرفنا في مقال سابق عن LinkedList وعلى هذا الرابط مثال يوضح تنفيذ Stack من خلال LinkedList

استخدام Stack Class في C#

توفر لغة C# كبقية لغات الـ OOP ( من مقال مقدمة إلى C# ) مجموعة من المكتبات البرمجية التي توفر Class يمكن العمل معها ببساطة ومن هذه الـ Classes مايهمنا في هذا المقال وهو Stack Class الذي يكون العمل معه كالتالي :

...........
ublic static void Main( String [] args)
        {
           Stack<string> s =new Stack<string>();
           s.Push("Mona");
           s.Push("Reem");
           s.Push("Sara");
           s.Push("Nora");

            //print the stack items 
            foreach (string n in s)
                 Console.Write(n + " ");
            Console.WriteLine();
            Console.WriteLine(s.Peek());
           
            //remove the top 
            s.Pop(); 
            foreach (string n in s)
                 Console.Write(n + " ");
            Console.ReadKey();     
        }
...........

ملخص Stack

وهنا فيديو عن الـ Stack وهي بنية بيانات اساسية في البرمجة وعلوم الحاسوب، ويقدم الفيديو شرحًا للعمليات الأساسية التي يمكن تنفيذها على الـ Stack.

إلى هنا ينتهي هذا المقال الذي تكلم عن نوع من انواع هياكل البيانات Data Structure وهو الـ Stacks تعرفنا فيه على مفهوم Stack وأنواعه والتطبيقات التي يمكن استخدام Stack فيها وشرحنا طريقة العمل مع Stack من خلال التعرف على أسلوب بناء العمليات الأساسية على Stack ,و من خلال تعليمات لغة C# قمنا بتنفيذ للـ Stack .

الإبلاغ عن إساءة الاستخدام

Kholood Tech Notes

المكدس Stack