تنفيذ Stack باستخدام Linked List في Java: شرح وكود كامل

تُستخدم بنية Stack عندما نحتاج إلى معالجة العناصر بترتيب «آخر ما يدخل أول ما يخرج» (LIFO). في هذا الدليل ستتعلم تنفيذ Stack باستخدام Linked List في Java، وفهم عمليتي الإضافة والحذف، ثم تشغيل مثال كامل واختبار الحالات المهمة. يفيد هذا الأسلوب عندما يتغير عدد العناصر أثناء التشغيل، لأن القائمة المرتبطة تنمو عند الحاجة من دون تحديد سعة ثابتة للمصفوفة.

المكدس Stack هو طريقة لتنظيم الوصول إلى البيانات: الإضافة والحذف يكونان من جهة واحدة تسمى القمة Top. أما Linked List فهي طريقة لربط العقد؛ تحتوي كل عقدة على قيمة ورابط إلى العقدة التالية. يمكن بناء المكدس فوق مصفوفة أو قائمة مرتبطة، مع إبقاء واجهة الاستخدام واحدة: push للإضافة، وpop للحذف، وpeek لقراءة القمة.

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

احفظ المثال باسم LinkedStackDemo.java ثم شغله باستخدام Java 8 أو إصدار أحدث:

public class LinkedStackDemo {
    private static class Node {
        int value;
        Node next;

        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node top;
    private int size;

    public void push(int value) {
        top = new Node(value, top);
        size++;
    }

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        int value = top.value;
        top = top.next;
        size--;
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.value;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        LinkedStackDemo stack = new LinkedStackDemo();
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Top: " + stack.peek());
        System.out.println("Removed: " + stack.pop());
        System.out.println("New top: " + stack.peek());
        System.out.println("Size: " + stack.size());
    }
}

الناتج المتوقع هو أن تكون القمة 30، ثم تُحذف 30، وتصبح القمة 20 ويصبح الحجم 2. لاحظ أن Node فئة داخلية خاصة؛ فالمستخدم يتعامل مع عمليات المكدس ولا يحتاج إلى تعديل الروابط بنفسه.

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

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

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

تعمل عمليات push وpop وpeek وisEmpty بزمن O(1)؛ فهي تتعامل مع القمة مباشرة. استهلاك الذاكرة هو O(n) لعدد العناصر، مع مساحة إضافية لمؤشر داخل كل عقدة. لا تحتاج القائمة إلى مساحة محجوزة لعناصر لم تُضف بعد، لكنها تستهلك ذاكرة إضافية للروابط مقارنة بمصفوفة بسيطة.

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

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

يعتمد تنفيذ Stack باستخدام Linked List في Java على عقدة ورابط القمة؛ لذلك تكون الإضافة والحذف من البداية في زمن ثابت. بعد فهم هذا المثال، يمكنك مراجعة مقالات Java التعليمية، ومقارنة تنظيم البيانات مع شرح Selection Sort في Java، ثم تطبيق مهاراتك على التعامل مع الملفات وامتداداتها في Java.