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

А, стек, говоришь? Ну это ж классика, ёпта, как бутерброд с колбасой в мире структур данных. Представь себе стопку тарелок, блядь, или патроны в магазине автомата — какой положил последним, тот и забираешь первым. Это и есть LIFO, или, как я люблю говорить, «последний зашёл — первый вышел, иди нахуй».

Основные движухи у стека:

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

Вот, смотри, как этим пользоваться в C++:

#include <iostream>
#include <stack>

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

    s.push(10); // Засунули 10
    s.push(20); // Засунули 20
    s.push(30); // Засунули 30. Теперь наверху 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 — делаются за O(1). То есть моментально, нихуя не думая. Красота.
2. Внутренности: По умолчанию эта std::stack — просто хитрая жопа, которая сидит на deque. Но можно сказать ей: «Слушай, давай на векторе» или «Давай на списке». Вторым параметром шаблона.

   std::stack<int, std::vector<int>> stack_vec; // Теперь на векторе
   std::stack<int, std::list<int>> stack_list;  // А теперь на списке, ядрёна вошь

3. Ограничения: Сюда нельзя воткнуть палец посередине и что-то выковырять. Только верхушку. Итераторов нет, нихуя. Принцип «не суй нос, куда не просят».
4. Где это нужно: Ну, везде, блядь! Стек вызовов функций, когда одна вызывает другую — это же чистый LIFO. Обход графов в глубину (DFS). Проверка, правильно ли расставлены скобки в выражении. Или вот «отмена» в фотошопе — последнее действие отменяешь первым.

А если вдруг захотелось сделать свой, на массиве, вот тебе голая правда:

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; } // Если индекс -1, значит, нихуя нет
};

Вот и вся магия. Просто, как три копейки, но без этого нихуя не работает. Главное — не переполнить и не пытаться вытащить из пустого, а то будет тебе underflow, и программа накрылась медным тазом.