تنفيذ Stack باستخدام Linked List في C++ مع إدارة الذاكرة

المكدس Stack يعمل بمبدأ LIFO: آخر عنصر يدخل هو أول عنصر يخرج. سننفذه بقائمة مترابطة في C++17، حيث تملك كل عقدة العقدة التالية باستخدام unique_ptr. يوضح المثال push وpop وpeek وحالة الفراغ، ويعيد قيمة مستقلة عن العقدة المحذوفة.

#include <iostream>
#include <memory>
#include <optional>
#include <utility>

class LinkedStack {
    struct Node {
        int value;
        std::unique_ptr<Node> next;
        Node(int v, std::unique_ptr<Node> n) : value(v), next(std::move(n)) {}
    };
    std::unique_ptr<Node> head;
public:
    LinkedStack() = default;
    LinkedStack(const LinkedStack&) = delete;
    LinkedStack& operator=(const LinkedStack&) = delete;
    bool empty() const { return !head; }
    void push(int value) {
        head = std::make_unique<Node>(value, std::move(head));
    }
    std::optional<int> peek() const {
        if (!head) return std::nullopt;
        return head->value;
    }
    std::optional<int> pop() {
        if (!head) return std::nullopt;
        auto old = std::move(head);
        head = std::move(old->next);
        return old->value;
    }
    ~LinkedStack() { while (!empty()) pop(); }
};

int main() {
    LinkedStack stack;
    for (int value : {11, 22, 33, 44}) stack.push(value);
    if (auto top = stack.peek()) std::cout << "Top: " << *top << '\n';
    while (auto value = stack.pop()) std::cout << *value << ' ';
    std::cout << "\nEmpty: " << stack.empty() << '\n';
}

تضيف push عقدة عند الرأس، لذلك لا نحتاج المرور على القائمة. عند إضافة 11 ثم 22 ثم 33 ثم 44 تصبح قيمة القمة 44، وترتيب الحذف 44 ثم 33 ثم 22 ثم 11. تعقيد كل من الإضافة والحذف وقراءة القمة O(1)، بينما تحتاج القائمة ذاكرة O(n) وتكلفة تخصيص عقدة لكل عنصر.

تملك head أول عقدة، وتملك next بقية السلسلة. تنقل std::move الملكية ولا تنسخ العقد. داخل pop نحفظ العقدة القديمة في متغير محلي، ثم ننقل رابطها وننسخ قيمتها قبل انتهاء عمرها. لا نستدعي free على ذاكرة أنشئت بـnew، ولا نعيد مؤشرًا لعقدة انتهى عمرها. يحذف destructor العقد تدريجيًا لتجنب سلسلة طويلة من الاستدعاءات المتداخلة.

تعيد pop وpeek قيمة std::nullopt عند الفراغ، ويجب فحص optional قبل استخدام النجمة لفك قيمته. مُنع نسخ الكائن في هذا المثال كي تكون سياسة الملكية واضحة. إذا كنت تحتاج مكدسًا في تطبيق عادي فابدأ بتقييم std::stack؛ تنفيذ القائمة يدويًا هنا تمرين على هياكل البيانات لا شرطًا لاستخدام المكدس.

احفظ المثال في ملف main.cpp واختر معيار C++17 في محررك. مع GCC أو Clang يمكنك الترجمة بالأمر g++ -std=c++17 -Wall -Wextra -pedantic main.cpp -o main ثم تشغيل الملف الناتج. ترجم كل مثال كبرنامج مستقل؛ لا تجمع دوال main من دروس مختلفة في ملف واحد.

الكود النصي أعلاه هو النسخة المصححة؛ قد تختلف المواد المرئية السابقة في أسماء المتغيرات أو طريقة التشغيل.