Что такое стек как структура данных?

Стек — это абстрактный тип данных, работающий по принципу LIFO (Last In, First Out): последний добавленный элемент извлекается первым. Основные операции:

• push — добавление элемента на вершину стека.
• pop — удаление элемента с вершины.
• top (или peek) — получение элемента с вершины без удаления.

Реализация и использование в C++: В стандартной библиотеке C++ стек реализован как адаптер контейнера (обычно поверх std::deque или std::vector) в заголовочном файле <stack>.

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    // Добавление элементов
    s.push(10);
    s.push(20);
    s.push(30);
    // Стек: [10, 20, 30] (30 — вершина)

    std::cout << "Вершина стека: " << s.top() << std::endl; // 30

    s.pop(); // Удаляем 30
    std::cout << "Вершина после pop: " << s.top() << std::endl; // 20

    // Проверка на пустоту
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    // Вывод: 20 10
    return 0;
}

Типичные сценарии использования:

• Управление вызовами функций и рекурсией (стек вызовов).
• Алгоритмы обхода графов (DFS).
• Парсинг выражений (проверка корректности скобок).
• Механизм отмены операций (undo).