الگوریتم

بازگشت، پشته (Stack)، صف (Queue)، جستجوی عمقی (DFS)

در علوم کامپیوتر، بازگشت (Recursion)، پشته (Stack) و صف (Queue) از ساختارهای داده‌ای اساسی هستند. همچنین، الگوریتم‌هایی مانند جستجوی عمقی (DFS) از این ساختارها استفاده می‌کنند. در این مقاله، مفاهیم زیر توضیح داده می‌شوند:

• مفهوم بازگشت و مثال
• پشته (Stack) و عملیات آن
• صف (Queue) و تفاوت آن با پشته
• نحوه استفاده از پشته در DFS

---

۱. بازگشت (Recursion)

بازگشت چیست؟

بازگشت یک تکنیک برنامه‌نویسی است که در آن یک تابع خودش را فراخوانی می‌کند. دو مفهوم اساسی در بازگشت وجود دارند:

• شرط پایه (Base Case): شرطی که اجرای بازگشت را متوقف می‌کند.
• فراخوانی بازگشتی (Recursive Case): حالتی که تابع خود را دوباره فراخوانی می‌کند.

مثال: محاسبه فاکتوریل

تعریف فاکتوریل:

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

پیاده‌سازی فاکتوریل در ++C:

int factorial(int n) {

    if (n == 0) return 1; 

    return n * factorial(n - 1);

}

---

۲. پشته (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;

}

---

۳. صف (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() (ابتدای صف)
نحوه پردازش	آخرین عنصر وارد شده، اول خارج می‌شود.	اولین عنصر وارد شده، اول خارج می‌شود.

---

۴. جستجوی عمقی (DFS)

DFS چیست؟

جستجوی عمقی (Depth-First Search - DFS) یک الگوریتم جستجو در گراف است که ابتدا یک مسیر را تا انتها دنبال می‌کند و سپس مسیرهای دیگر را بررسی می‌کند.

مثال 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 پیروی می‌کند.
• DFS از پشته برای پیمایش گراف استفاده می‌کند.

این مفاهیم برای یادگیری الگوریتم‌ها و ساختمان داده‌ها ضروری هستند. حتماً آن‌ها را تمرین کنید!