🔥 أحدث الأخبار

موقع يهتم بكل ماهو جديد في عالم التكنولوجيا والرياضة

كورس C++ المتوسط – الحلقة التاسعة: Doubly Linked List و Stack

عبودي لتقنية والمعلومات
(0)

 

كورس C++ المتوسط – الحلقة التاسعة: Doubly Linked List و Stack

#برمجة

مقدمة

مرحباً بك في الحلقة التاسعة من المستوى المتوسط في C++.

في الحلقة السابقة تعلمنا:

  • Linked List
  • Node
  • الإضافة والحذف
  • البحث داخل القوائم المرتبطة
  • إدارة البيانات الديناميكية

اليوم سنتعلم هيكلين مهمين جداً يستخدمان في البرامج الحقيقية:

Doubly Linked List

و

Stack

ويستخدمان في:

  • المتصفحات
  • المحررات النصية
  • الألعاب
  • أنظمة Undo و Redo
  • إدارة العمليات داخل البرامج

أولاً: ما هي Doubly Linked List؟

في الحلقة السابقة كانت العقدة تحتوي على:

struct Node
{
    int data;
    Node* next;
};

أي أن كل عقدة تعرف فقط العقدة التالية.

الشكل

10 ---> 20 ---> 30 ---> NULL

المشكلة

إذا كنت عند العقدة:

20

لا يمكنك العودة إلى:

10

لأنك لا تملك مؤشراً للخلف.

الحل

نستخدم:

Doubly Linked List

الشكل

NULL <- 10 <-> 20 <-> 30 -> NULL

كل عقدة تحتوي:

  • البيانات
  • المؤشر التالي
  • المؤشر السابق

إنشاء العقدة

struct Node
{
    int data;
    Node* next;
    Node* prev;
};

إنشاء عقدتين

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* next;
    Node* prev;
};

int main()
{
    Node* first = new Node();
    Node* second = new Node();

    first->data = 10;
    second->data = 20;

    first->next = second;
    first->prev = nullptr;

    second->prev = first;
    second->next = nullptr;

    cout << second->prev->data;

    delete first;
    delete second;

    return 0;
}

الناتج

10

المرور للأمام

Node* temp = first;

while(temp != nullptr)
{
    cout << temp->data << endl;

    temp = temp->next;
}

المرور للخلف

إذا كان لدينا مؤشر على آخر عنصر:

Node* temp = last;

while(temp != nullptr)
{
    cout << temp->data << endl;

    temp = temp->prev;
}

الناتج

30
20
10

إضافة عنصر في البداية

Node* newNode = new Node();

newNode->data = 5;

newNode->next = first;
newNode->prev = nullptr;

first->prev = newNode;

first = newNode;

إضافة عنصر في النهاية

Node* newNode = new Node();

newNode->data = 40;

newNode->next = nullptr;

last->next = newNode;

newNode->prev = last;

last = newNode;

حذف عنصر

الميزة القوية في Doubly Linked List أن الحذف أسهل.

مثال:

10 <-> 20 <-> 30

نريد حذف:

20

الكود

node20->prev->next = node20->next;
node20->next->prev = node20->prev;

delete node20;

مميزات Doubly Linked List

✔ التنقل للأمام والخلف

✔ حذف أسرع

✔ مرونة أكبر

عيوبها

❌ تستهلك ذاكرة أكثر

❌ تنفيذها أصعب قليلاً

ثانياً: Stack

ما هو Stack؟

Stack هو هيكل بيانات يعمل بمبدأ:

Last In First Out

اختصاراً:

LIFO

مثال من الحياة

كومة أطباق:

Plate 3
Plate 2
Plate 1

أول طبق سيخرج هو آخر طبق تم وضعه.

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

العملية الوظيفة
push إضافة عنصر
pop حذف العنصر العلوي
top الحصول على العنصر العلوي
empty التحقق إذا كان فارغاً

استخدام Stack الجاهز

أضف المكتبة:

#include <stack>

إنشاء Stack

stack<int> numbers;

إضافة عناصر

numbers.push(10);
numbers.push(20);
numbers.push(30);

الشكل

30
20
10

معرفة العنصر العلوي

cout << numbers.top();

الناتج

30

حذف العنصر العلوي

numbers.pop();

يصبح

20
10

معرفة عدد العناصر

cout << numbers.size();

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

if(numbers.empty())
{
    cout << "Empty";
}

مثال كامل

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<int> numbers;

    numbers.push(10);
    numbers.push(20);
    numbers.push(30);

    cout << "Top: " << numbers.top() << endl;

    numbers.pop();

    cout << "Top After Pop: "
         << numbers.top();

    return 0;
}

تطبيق عملي: عكس نص

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    string text = "HELLO";

    stack<char> s;

    for(char c : text)
    {
        s.push(c);
    }

    while(!s.empty())
    {
        cout << s.top();

        s.pop();
    }

    return 0;
}

الناتج

OLLEH

أين يستخدم Stack؟

في:

  • Undo / Redo
  • History المتصفح
  • تحليل الأكواد البرمجية
  • استدعاء الدوال
  • الألعاب

مثال Undo

عندما تكتب:

Hello

ثم:

Hello World

ثم تضغط Undo.

يتم الرجوع للحالة السابقة باستخدام Stack.

مقارنة Linked List و Stack

Linked List Stack
وصول مرن الوصول للأعلى فقط
حذف وإضافة في أي مكان حذف وإضافة من الأعلى
بنية بيانات عامة بنية متخصصة

أخطاء شائعة

❌ استخدام:

top()

على Stack فارغ.

❌ نسيان:

empty()

قبل الوصول للعناصر.

❌ الخلط بين Queue و Stack.

تمارين

التمرين 1

أنشئ Stack يحتوي:

10
20
30

واطبع العنصر العلوي.

التمرين 2

احذف عنصرين باستخدام pop.

التمرين 3

اعرض عدد العناصر.

التمرين 4

اكتب برنامجاً يعكس كلمة باستخدام Stack.

التمرين 5

أنشئ Doubly Linked List تحتوي:

5 <-> 10 <-> 15

واطبعها للأمام والخلف.

ملخص الحلقة التاسعة

تعلمنا:

  • Doubly Linked List
  • prev و next
  • التنقل في الاتجاهين
  • Stack
  • push
  • pop
  • top
  • empty
  • تطبيقات عملية

في الحلقة العاشرة من المستوى المتوسط سنتعلم:

🔥 Queue و Priority Queue

وسنبني:

  • نظام انتظار العملاء
  • إدارة المهام
  • محاكاة أنظمة الحجز والطوابير

ثم نكون قد أكملنا جزءاً كبيراً من هياكل البيانات الأساسية في C++. 🚀


تعليقات

إرسال تعليق

💬 🙋🏻‍♂️