Что такое стек?

Стек: структура данных LIFO

Стек (Stack) — это абстрактная структура данных, которая работает по принципу LIFO (Last In, First Out — "последний вошел, первый вышел"). Это означает, что элемент, добавленный последним, извлекается первым.

Основные операции

Стек поддерживает две основные операции:

• push(value) — добавление элемента на вершину стека (O(1))
• pop() — удаление и возврат элемента с вершины (O(1))

Дополнительно:

• top() / peek() — просмотр верхнего элемента без удаления (O(1))
• isEmpty() — проверка пустоты стека (O(1))
• size() — количество элементов (O(1))

Реализация на C++

#include <stack>
#include <iostream>
using namespace std;

int main() {
    stack<int> s;
    
    // push операции
    s.push(10);
    s.push(20);
    s.push(30);
    
    // peek и pop
    cout << s.top() << endl; // 30
    s.pop();
    cout << s.top() << endl; // 20
    
    // проверка размера
    cout << "Размер: " << s.size() << endl; // 2
    cout << "Пусто: " << s.empty() << endl; // false
    
    return 0;
}

Практические примеры использования

• Парсинг выражений — проверка сбалансированных скобок
• Откат операций — реализация функции "Undo"
• Глубокий поиск (DFS) — граф и дерево обход
• Обработка вызовов функций — стек вызовов в программе
• Вычисление постфиксных выражений — обратная польская нотация

Стек вызовов (Call Stack)

В программах существует стек вызовов — часть памяти, где хранятся:

• Адреса возврата из функций
• Локальные переменные
• Параметры функций

При вызове функции создается frame (кадр), при возврате он удаляется со стека. Это критично для понимания памяти и переполнения стека (stack overflow).

Различие от очереди (Queue)

Отличие от очереди (Queue, FIFO):

• Стек: последний вошел → первый вышел (вершина)
• Очередь: первый вошел → первый вышел (начало и конец)

Сложность операций

Все основные операции работают за O(1) в среднем случае, что делает стек очень эффективной структурой данных для большинства приложений backend-разработчика.