Как устроен стек (stack) в C++?

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

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

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

Пример использования std::stack:

#include <iostream>
#include <stack>

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

    s.push(10); // Стек: [10]
    s.push(20); // Стек: [10, 20]
    s.push(30); // Стек: [10, 20, 30]

    std::cout << "Верхний элемент: " << s.top() << std::endl; // 30

    s.pop(); // Удаляем 30
    std::cout << "После pop(): " << s.top() << std::endl; // 20

    std::cout << "Размер стека: " << s.size() << std::endl; // 2
    std::cout << "Стек пуст? " << (s.empty() ? "Да" : "Нет") << std::endl;

    return 0;
}

Ключевые особенности и внутреннее устройство:

1. Временная сложность: Все основные операции (push, pop, top, empty) выполняются за O(1).
2. Реализация: Можно выбрать базовый контейнер через второй шаблонный параметр:

   std::stack<int, std::vector<int>> stack_vec; // На основе vector
   std::stack<int, std::list<int>> stack_list;  // На основе list

3. Ограничения: Нет прямого доступа к элементам кроме верхнего, нет итераторов.
4. Типичное применение:
   • Управление вызовами функций (стек вызовов)
   • Алгоритмы обхода графов (DFS)
   • Парсинг выражений (проверка скобок)
   • Реализация отмены операций (undo/redo)

Ручная реализация на массиве:

class ArrayStack {
private:
    int* arr;
    int capacity;
    int topIndex;

public:
    ArrayStack(int size) : capacity(size), topIndex(-1) {
        arr = new int[capacity];
    }

    ~ArrayStack() { delete[] arr; }

    void push(int value) {
        if (topIndex >= capacity - 1) {
            throw std::overflow_error("Stack overflow");
        }
        arr[++topIndex] = value;
    }

    int pop() {
        if (isEmpty()) {
            throw std::underflow_error("Stack underflow");
        }
        return arr[topIndex--];
    }

    int top() const {
        if (isEmpty()) throw std::runtime_error("Stack is empty");
        return arr[topIndex];
    }

    bool isEmpty() const { return topIndex == -1; }
};