المكدس

المكدس (stack) بنية بيانات خطية تتبع مبدأ آخر ما يدخل يخرج أولاً (LIFO).

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

كما يظهر في الشكل التالي، نسمي أعلى العناصر المكدسة "القمة" وأدناها "القاع". وتسمى عملية إضافة عنصر إلى القمة "الدفع" (push)، وتسمى عملية إزالة العنصر العلوي "السحب" (pop).

عمليات المكدس الشائعة

تظهر العمليات الشائعة على المكدس في الجدول التالي. وتعتمد أسماء الدوال المحددة على لغة البرمجة المستخدمة. وهنا نستخدم التسمية الشائعة push() وpop() وpeek().

جدول   كفاءة عمليات المكدس

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

/* تهيئة المكدس */
// في Go، يُنصح باستخدام Slice كمكدس
var stack []int

/* دفع العناصر */
stack = append(stack, 1)
stack = append(stack, 3)
stack = append(stack, 2)
stack = append(stack, 5)
stack = append(stack, 4)

/* الاطّلاع على العنصر العلوي */
peek := stack[len(stack)-1]

/* سحب العنصر */
pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]

/* الحصول على طول المكدس */
size := len(stack)

/* التحقق مما إذا كان فارغاً */
isEmpty := len(stack) == 0

/* تهيئة المكدس */
// لا تحتوي TypeScript على فئة مكدس مدمجة، ويمكن استخدام Array كمكدس
const stack: number[] = [];

/* دفع العناصر */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);

/* الاطّلاع على العنصر العلوي */
const peek = stack[stack.length - 1];

/* سحب العنصر */
const pop = stack.pop();

/* الحصول على طول المكدس */
const size = stack.length;

/* التحقق مما إذا كان فارغاً */
const is_empty = stack.length === 0;

تنفيذ المكدس

لفهم كيفية عمل المكدس فهماً أعمق، دعنا نحاول تنفيذ فئة مكدس بأنفسنا.

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

التنفيذ بقائمة مترابطة

عند تنفيذ مكدس باستخدام قائمة مترابطة، يمكننا اعتبار العقدة الرأسية للقائمة المترابطة قمةَ المكدس والعقدة الذيلية قاعَه.

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

فيما يلي شيفرة نموذجية لتنفيذ مكدس قائم على قائمة مترابطة:

/* مكدس قائم على تنفيذ قائمة مترابطة */
class LinkedListStack {
    private stackPeek: ListNode | null; // استخدم العقدة الرأسية كقمة للمكدس
    private stkSize: number = 0; // طول المكدس

    constructor() {
        this.stackPeek = null;
    }

    /* الحصول على طول المكدس */
    get size(): number {
        return this.stkSize;
    }

    /* التحقق مما إذا كان المكدس فارغاً */
    isEmpty(): boolean {
        return this.size === 0;
    }

    /* الدفع */
    push(num: number): void {
        const node = new ListNode(num);
        node.next = this.stackPeek;
        this.stackPeek = node;
        this.stkSize++;
    }

    /* السحب */
    pop(): number {
        const num = this.peek();
        if (!this.stackPeek) throw new Error('Stack is empty');
        this.stackPeek = this.stackPeek.next;
        this.stkSize--;
        return num;
    }

    /* إعادة القائمة للطباعة */
    peek(): number {
        if (!this.stackPeek) throw new Error('Stack is empty');
        return this.stackPeek.val;
    }

    /* تحويل القائمة المترابطة إلى Array وإعادتها */
    toArray(): number[] {
        let node = this.stackPeek;
        const res = new Array<number>(this.size);
        for (let i = res.length - 1; i >= 0; i--) {
            res[i] = node!.val;
            node = node!.next;
        }
        return res;
    }
}

التنفيذ بمصفوفة

عند تنفيذ مكدس باستخدام مصفوفة، يمكننا اعتبار نهاية المصفوفة قمةَ المكدس. وكما يظهر في الشكل التالي، تقابل عمليتا الدفع والسحب إضافة عناصر وحذفها عند نهاية المصفوفة، وكلتاهما بتعقيد زمني $O(1)$.

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

/* مكدس قائم على تنفيذ مصفوفة */
class ArrayStack {
    private stack: number[];
    constructor() {
        this.stack = [];
    }

    /* الحصول على طول المكدس */
    get size(): number {
        return this.stack.length;
    }

    /* التحقق مما إذا كان المكدس فارغاً */
    isEmpty(): boolean {
        return this.stack.length === 0;
    }

    /* الدفع */
    push(num: number): void {
        this.stack.push(num);
    }

    /* السحب */
    pop(): number | undefined {
        if (this.isEmpty()) throw new Error('Stack is empty');
        return this.stack.pop();
    }

    /* إعادة القائمة للطباعة */
    top(): number | undefined {
        if (this.isEmpty()) throw new Error('Stack is empty');
        return this.stack[this.stack.length - 1];
    }

    /* إعادة Array */
    toArray() {
        return this.stack;
    }
}

مقارنة بين التنفيذين

العمليات المدعومة

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

الكفاءة الزمنية

في التنفيذ القائم على المصفوفة، تحدث عمليتا الدفع والسحب معاً في ذاكرة متجاورة مخصصة مسبقاً، وهو ما يتمتع بمحلية جيدة لذاكرة التخزين المؤقت (cache locality)، وبالتالي يكون أكثر كفاءة. غير أنه إذا تجاوز الدفع سعة المصفوفة، فسيُفعِّل آلية توسيع، مما يجعل التعقيد الزمني لعملية الدفع تلك تحديداً $O(n)$.

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

خلاصةً، عندما تكون العناصر المدفوعة والمسحوبة من أنواع بيانات أساسية مثل int أو double، يمكننا استخلاص الاستنتاجين التاليين:

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

الكفاءة المكانية

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

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

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

التطبيقات النموذجية للمكدس

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