المحاضرة 8: بنية البيانات المكدس (Stack)

جامعة حمص - كلية الهندسة المعلوماتية - السنة الثانية

المحاضر

ناديا خرسان

المادة

الخوارزميات وبنى المعطيات 1

النوع

بنية بيانات خطية (Linear Data Structure)

تعريف المكدس (Stack)

المكدس هو بنية معطيات خطية تشبه القائمة المترابطة ولكن لا يمكن الوصول إلا لآخر عنصر تم إدخاله.

يدعى مكان العنصر الأخير قمة المكدس (TOP).

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

«العنصر الداخل أخيراً هو الخارج أولاً» (LIFO = Last In, First Out)

شرح مفصل:

المكدس يشبه تمامًا كومة من الأطباق في المطبخ:

  • عندما تضيف طبقًا جديدًا، تضعه فوق الكومة (Push)
  • عندما تأخذ طبقًا، تأخذه من أعلى الكومة (Pop)
  • لا يمكنك أخذ طبق من منتصف الكومة أو أسفلها
  • الطبق الأخير الذي وضعته هو أول طبق ستأخذه

هذا هو مبدأ LIFO (Last-In-First-Out) الذي يحكم عمل بنية البيانات المكدس.

قمة المكدس (TOP)
e4
e3
e2
e1

خصائص المكدس:

  • بنية بيانات خطية (Linear Data Structure)
  • يتبع مبدأ LIFO (Last-In-First-Out)
  • الإضافة والحذف من جهة واحدة فقط (TOP)
  • الوصول محدود لعنصر القمة فقط
  • يحتوي على مؤشر خاص (TOP) يشير إلى آخر عنصر تم إضافته
  • له سعة محدودة في التمثيل بالمصفوفة، وغير محدودة في التمثيل بالقائمة المترابطة

استخدامات المكدس

يمكن استخدام المكدسات في العديد من التطبيقات التي تتطلب تخزين البيانات ثم استرجاعها بترتيب عكسي:

  • تخزين بيانات وعناوين العودة للتوابع عند استدعاءها: عند استدعاء دالة، يتم تخزين معلومات العودة في المكدس
  • معالجة التعابير الحسابية: تقييم التعابير أو تحويلها من صيغة إلى أخرى (مثل تحويل من Infix إلى Postfix)
  • اختبار تناسق الأقواس في تعبير أو نص (Parenthesis Matching): التأكد من أن الأقواس متوازنة ومغلقة بشكل صحيح
  • تحويل الخوارزميات العودية إلى تكرارية: يمكن استخدام المكدس لتحويل الدوال العودية إلى تكرارية
  • آلية عمل زر التراجع (Undo) في البرامج: تخزين الإجراءات السابقة في مكدس للرجوع إليها
  • سجل الصفحات التي تمت زيارتها في متصفح الويب: المكدس يستخدم لتتبع تاريخ التصفح
  • انعكاس سلسلة (String Reversal): يمكن عكس سلسلة باستخدام مكدس بسهولة

مثال: اختبار توازن الأقواس

يتم استخدام المكدس للتأكد من أن الأقواس متوازنة في تعبير ما:

  • عند مواجهة قوس فتح '('، نضعه في المكدس
  • عند مواجهة قوس إغلاق ')'، نخرج قوسًا من المكدس
  • إذا كان المكدس فارغًا عند مواجهة قوس إغلاق، فهذا يعني أن الأقواس غير متوازنة
  • إذا انتهى التعبير ولم يكن المكدس فارغًا، فهذا يعني أن الأقواس غير متوازنة

التعبير الصحيح: (a + b) * (c - d) → متوازن

التعبير الخطأ: (a + b) * (c - d)) → غير متوازن

تمثيل المكدس

شرح مفصل:

يمكن تمثيل المكدس بطريقتين رئيسيتين:

  1. باستخدام المصفوفات (Arrays): طريقة بسيطة وسهلة التنفيذ، ولكن لها سعة محدودة
  2. باستخدام القوائم المترابطة (Linked Lists): أكثر مرونة حيث لا يوجد حد أقصى للسعة (إلا الذاكرة المتاحة)

كل طريقة لها مميزاتها وعيوبها، ويعتمد اختيار الطريقة على متطلبات التطبيق.

تمثيل المكدس باستخدام مصفوفة (Array)

في هذا التمثيل نستخدم مصفوفة ذات حجم ثابت لتخزين عناصر المكدس.

// تعريف بنية المكدس
const int MAX_SIZE = 100;
struct stack {
    int top; // مؤشر قمة المكدس
    int elm[MAX_SIZE]; // عناصر المكدس
};

حالة المكدس الفارغ: top = -1

المميزات:

  • سهولة التنفيذ
  • كفاءة في استخدام الذاكرة (لا حاجة لمؤشرات إضافية)

العيوب:

  • حجم ثابت (قد يحدث طفحان - Stack Overflow)
  • غير مرن في تغيير الحجم

تمثيل المكدس باستخدام قائمة مترابطة (Linked List)

في هذا التمثيل نستخدم عقد مترابطة لتخزين عناصر المكدس.

// تعريف بنية العقدة
struct node {
    int data; // بيانات العقدة
    node* next; // مؤشر للعقدة التالية
};

node* top = NULL; // مؤشر قمة المكدس

حالة المكدس الفارغ: top = NULL

المميزات:

  • حجم ديناميكي (يتغير حسب الحاجة)
  • لا يوجد مشكلة طفحان (إلا في حالة نفاد الذاكرة)
  • مرن وسهل الإضافة والحذف

العيوب:

  • يستهلك ذاكرة أكثر بسبب تخزين المؤشرات
  • تنفيذه أكثر تعقيدًا قليلًا

العمليات الأساسية على المكدس

شرح مفصل:

تعتمد بنية البيانات المكدس على مجموعة من العمليات الأساسية التي تحكم طريقة عمله:

  • تهيئة المكدس (Initialization): إنشاء مكدس جديد فارغ
  • الإضافة (Push): إضافة عنصر جديد إلى قمة المكدس
  • الحذف (Pop): إزالة العنصر الموجود في قمة المكدس وإرجاع قيمته
  • قراءة القمة (Peek/Top): قراءة قيمة العنصر في قمة المكدس دون إزالته
  • التحقق من الفراغ (isEmpty): معرفة ما إذا كان المكدس فارغًا
  • التحقق من الامتلاء (isFull): معرفة ما إذا كان المكدس ممتلئًا (في حالة التمثيل بالمصفوفة)
  • الحصول على الحجم (getSize): معرفة عدد العناصر الموجودة في المكدس

initStack()

تهيئة المكدس بحيث يصبح فارغاً

للمصفوفة: top = -1

للقائمة: top = NULL

التعقيد الزمني: O(1)

push(item)

إضافة عنصر جديد إلى قمة المكدس

يجب التحقق من عدم امتلاء المكدس لتجنب الطفحان (Overflow)

التعقيد الزمني: O(1)

pop()

حذف العنصر الموجود في قمة المكدس وإرجاع قيمته

يجب التحقق من عدم فراغ المكدس لتجنب الجفاف (Underflow)

التعقيد الزمني: O(1)

getTop()

قراءة العنصر الموجود في قمة المكدس دون حذفه

يجب التحقق من عدم فراغ المكدس

التعقيد الزمني: O(1)

isEmpty()

التحقق مما إذا كان المكدس فارغاً

للمصفوفة: return (top == -1)

للقائمة: return (top == NULL)

التعقيد الزمني: O(1)

isFull()

التحقق مما إذا كان المكدس ممتلئاً

للمصفوفة: return (top == MAX_SIZE-1)

للقائمة: عادة لا يكون ممتلئاً إلا في حالة نفاد الذاكرة

التعقيد الزمني: O(1)

getSize()

الحصول على عدد العناصر الموجودة في المكدس

للمصفوفة: return top + 1

للقائمة: عادة نحتفظ بعدد العناصر في متغير

التعقيد الزمني: O(1)

تنفيذ المكدس باستخدام المصفوفة (Array)

شرح مفصل:

في هذا التنفيذ، نستخدم مصفوفة ذات حجم ثابت لتخزين عناصر المكدس.

نستخدم متغير top لتتبع موقع العنصر الأخير في المكدس:

  • عند الإضافة (push): نزيد قيمة top ثم نخزن العنصر الجديد في الموقع الجديد
  • عند الحذف (pop): نسترجع العنصر في الموقع top ثم نخفض قيمة top
  • عند الفراغ: top == -1
  • عند الامتلاء: top == MAX_SIZE - 1
// ملف stack.h
#include <iostream>
const int MAX_SIZE = 100;

class Stack {
    int top; // مؤشر قمة المكدس
    int element[MAX_SIZE]; // عناصر المكدس

    public:
        // Constructor - المُنشئ
        Stack() { top = -1; }

        void initStack() {
            top = -1;
        }

        bool isEmpty() {
            return (top == -1);
        }

        bool isFull() {
            return (top == MAX_SIZE - 1);
        }

        void push(int x) {
            if (!isFull()) {
                top++;
                element[top] = x;
            } else {
                std::cout << "Overflow! Stack is full.";
            }
        }

        int pop() {
            if (!isEmpty()) {
                int value = element[top];
                top--;
                return value;
            } else {
                std::cout << "Underflow! Stack is empty.";
                return -1; // قيمة خطأ
            }
        }

        int getTop() {
            if (!isEmpty()) {
                return element[top];
            } else {
                std::cout << "Stack is empty.";
                return -1; // قيمة خطأ
            }
        }

        int getSize() {
            return top + 1;
        }
};

مثال استخدام المكدس

// ملف main.cpp
#include <iostream>
#include "stack.h"

int main() {
    Stack s; // إنشاء كائن المكدس
    int x;

    // التحقق من حالة المكدس
    if (!s.isEmpty()) {
        std::cout << "\n Top = " << s.getTop() << std::endl;
    } else {
        std::cout << "\n المكدس فارغ.\n";
    }

    // إضافة 5 عناصر جديدة إلى المكدس
    std::cout << "\n إضافة 5 عناصر جديدة إلى المكدس:\n";
    for (int i = 0; i < 5; ++i) {
        std::cout << " أدخل x = ";
        std::cin >> x;
        s.push(x);
    }
    std::cout << " القمة = " << s.getTop() << std::endl;

    // إزالة عنصر من المكدس
    std::cout << "\n إزالة عنصر من المكدس:\n";
    s.pop();
    std::cout << " القمة = " << s.getTop() << std::endl;

    // ملء المكدس حتى الحجم الأقصى
    std::cout << "\n ملء المكدس حتى الحجم الأقصى:\n";
    for (int j = s.getSize(); j < MAX_SIZE; ++j) {
        s.push(j + 1);
    }
    std::cout << " القمة = " << s.getTop() << std::endl;
    std::cout << " عدد العناصر في المكدس = " << s.getSize() << std::endl;

    // محاولة إضافة عنصر إلى مكدس ممتلئ
    std::cout << "\n محاولة إضافة عنصر جديد:\n";
    std::cout << " أدخل x = ";
    std::cin >> x;
    s.push(x); // ستسبب overflow

    // تفريغ المكدس
    std::cout << "\n تفريغ المكدس.";
    s.initStack();
    if (!s.isEmpty()) {
        std::cout << "\n القمة = " << s.getTop();
    } else {
        std::cout << "\n المكدس فارغ.";
    }
    return 0;
}

مثال على مخرجات البرنامج:

المكدس فارغ.

إضافة 5 عناصر جديدة إلى المكدس:

أدخل x = 10

أدخل x = 20

أدخل x = 30

أدخل x = 40

أدخل x = 50

القمة = 50

إزالة عنصر من المكدس:

القمة = 40

ملء المكدس حتى الحجم الأقصى:

القمة = 99

عدد العناصر في المكدس = 100

محاولة إضافة عنصر جديد:

أدخل x = 100

Overflow! Stack is full.

تفريغ المكدس.

المكدس فارغ.

محاكاة عمليات المكدس

قمة المكدس (TOP)
حالة المكدس: فارغ