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

Question

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

Тип вопроса: Алгоритмы и структуры данных Вероятность: 25% Категория: C/C++ Разработчик

Ответ

Стек — это абстрактный тип данных, работающий по принципу 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).

Ответ 18+ 🔞

А, стек, говоришь? Ну это ж классика, ёпта! Представь себе стопку тарелок на раздаче в столовке — ту, куда повариха с таким ебать-колотить лицом швыряет грязные. Какую тарелку ты возьмёшь первой? Ту, что сверху, которая прилетела последней. Вот и весь принцип: последний зашёл — первый вышел. LIFO, блядь. Хуй с горы, если по-нашему.

Основные движухи там всего три, запомнить проще простого:

push — запихнуть элемент наверх. Как ту самую тарелку.
pop — снять этот верхний элемент и выкинуть. Ну или использовать, не суть.
top — посмотреть, что там наверху лежит, но не трогать. Подсмотреть, так сказать.

В плюсах это дело живёт в <stack> и сделано так, что под капотом оно обычно на deque или vector ездит. Тебе об этом думать не надо, просто пользуйся.

Вот смотри, как это выглядит в коде. Ничего сложного, честно.

#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) — без стека там вообще никуда.
Проверка скобок в выражении — овердохуища полезная штука. Открывающую скобку — push, закрывающую — pop и проверяем, совпадает ли. Если в конце стек пустой — красота.
Механизм "Отменить" (undo) — каждое действие пушат в стек, а когда юзер орёт "верните как было!", делают pop.

Вот и вся магия. Ничего мудрёного, но без этого — никуда.