خوارزمية

التكرار، المكدس (Stack)، الطابور (Queue) والبحث المتعمق (DFS)

في علم الحاسوب، يعتبر التكرار، والمكدسات (Stacks)، والطوابير (Queues) من الهياكل الأساسية التي تُستخدم بشكل شائع في خوارزميات مثل البحث المتعمق (DFS). سنتناول في هذه المقالة:

• مفهوم التكرار
• المكدس وعملياته
• الطابور والفرق بينه وبين المكدس
• كيف يعتمد DFS على التكرار

---

1. التكرار: مفهوم أساسي

ما هو التكرار؟

التكرار هو استدعاء الدالة لنفسها لحل مشكلة أصغر. ويتكون من:

• الحالة الأساسية – التي توقف التكرار.
• الحالة التكرارية – حيث تستدعي الدالة نفسها.

مثال: حساب المضروب (Factorial)

يُعرّف المضروب كالتالي:

n! = n × (n-1) × (n-2) × ... × 1

تنفيذ التكرار في C++:

int factorial(int n) {

    if (n == 0) return 1; 

    return n * factorial(n - 1);

}

2. المكدس (Stack): بنية LIFO

ما هو المكدس؟

المكدس هو بنية بيانات تتبع مبدأ LIFO (Last In, First Out)، أي أن آخر عنصر يُضاف هو أول عنصر يُزال.

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

• push(x) – يضيف عنصرًا إلى الأعلى.
• pop() – يزيل العنصر العلوي.
• top() – يعرض العنصر العلوي دون إزالته.

مثال بلغة C++:

#include <stack>

#include <iostream>

using namespace std;

int main() {

    stack<int> s;  

    s.push(1);   

    s.push(2);   

    s.push(3);   

    cout << s.top() << endl; // 3

    s.pop();  

    cout << s.top() << endl; // 2

    return 0;

}

---

3. الطابور (Queue): بنية FIFO

ما هو الطابور؟

الطابور هو بنية بيانات تتبع مبدأ FIFO (First In, First Out)، أي أن العنصر الذي يُضاف أولًا هو أول عنصر يُزال.

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

• push(x) – يضيف عنصرًا في النهاية.
• pop() – يزيل العنصر الأول.
• front() – يعرض العنصر الأول دون إزالته.

مثال بلغة C++:

#include <queue>

#include <iostream>

using namespace std;

int main() {

    queue<int> q;

    q.push(1);

    q.push(2);

    q.push(3);

    cout << q.front() << endl; // 1

    q.pop();  

    cout << q.front() << endl; // 2

    return 0;

}

المقارنة بين المكدس والطابور

الميزة	المكدس (LIFO)	الطابور (FIFO)
إضافة عنصر	push(x) في الأعلى	push(x) في النهاية
إزالة عنصر	pop() يزيل العلوي	pop() يزيل الأول
الترتيب	الأخير يدخل، الأول يخرج	الأول يدخل، الأول يخرج

---

4. البحث المتعمق (DFS)

ما هو DFS؟

البحث المتعمق (Depth-First Search, DFS) هو خوارزمية تُستخدم لاستكشاف الرسوم البيانية حيث يتم استكشاف كل فرع بالكامل قبل العودة إلى الفرع السابق.

مثال لمسار البحث المتعمق:

        1

       / \

      2   7

     / \   \

    3   6   11

   / \   \

  4   5   8

         / \

        9   10

تنفيذ DFS بلغة C++:

void dfs(int node) {

    visited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {

            dfs(neighbor);

        }

    }

}

---

الخاتمة

• التكرار يساعد في حل المشاكل المعقدة.
• المكدس يعمل بمبدأ LIFO ويستخدم في التكرار.
• الطابور يعمل بمبدأ FIFO ويُستخدم في البحث العرضي (BFS).
• DFS يعتمد على المكدس وهو خوارزمية بحث أساسية.

هذه المفاهيم أساسية في الخوارزميات وهياكل البيانات. جرب تنفيذها بنفسك!