Алгоритм 1

Рекурсия, стек (Stack), очередь (Queue), поиск в глубину (DFS)

В информатике рекурсия (Recursion), стек (Stack) и очередь (Queue) являются основными структурами данных. Кроме того, алгоритмы, такие как поиск в глубину (DFS), используют эти структуры. В этой статье рассматриваются следующие темы:

• Понятие рекурсии и пример
• Стек (Stack) и его операции
• Очередь (Queue) и отличие от стека
• Использование стека в алгоритме DFS

---

1. Рекурсия (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);

}

---

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) — это алгоритм обхода графа, который сначала исследует один путь до конца, а затем возвращается и проверяет другие пути.

Пример 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 использует стек для обхода графа.

Эти концепции важны для изучения алгоритмов и структур данных. Практикуйтесь в их использовании!