Стек, очередь, дек и очередь с приоритетом

Все четыре можно заменить вектором — и почти всегда это будет работать. Смысл в другом: чем меньше операций структура обязана поддерживать, тем эффективнее она устроена внутри.

Стек

Добавить в конец, удалить с конца, посмотреть на последний. Всё за $O(1)$.

stack<int> s;
s.push(5);
int top = s.top();
s.pop();          // ничего не возвращает

Обратите внимание: pop() удаляет, но не возвращает значение. Сначала top(), потом pop().

Смотреть на произвольный элемент нельзя, проходиться по стеку нельзя, сортировать нельзя. Именно поэтому он экономнее вектора по памяти — внутри он лежит блоками, а не одним куском, и не хранит запаса под рост.

На практике стек в олимпиадном коде обычно заменяют вектором: тот умеет всё то же плюс push_back, а разница в скорости невелика. Настоящий стек берут, когда память впритык.

Очередь

Добавить в конец, удалить из начала, посмотреть на оба конца.

queue<int> q;
q.push(5); q.push(3); q.push(1);
q.front();   // 5 — кто пришёл раньше всех
q.back();    // 1 — кто пришёл позже всех
q.pop();     // удаляет из начала

Стек — «последним пришёл, первым вышел», очередь — «первым пришёл, первым вышел».

Вектор так не умеет: удаление из начала сдвигает весь хвост и стоит $O(n)$. Очередь делает это за константу.

Главное применение — обход в ширину. Там очередь появляется не по вкусу, а по необходимости: именно она обеспечивает обход по слоям.

Дек

Добавлять и удалять с обоих концов, плюс обращаться по индексу. Всё за $O(1)$.

deque<int> d;
d.push_back(1); d.push_front(2);
d.pop_back(); d.pop_front();
d[0];        // да, по индексу тоже можно

Универсальнее вектора, и за универсальность приходится платить: доступ по индексу у дека медленнее, потому что данные лежат блоками и адрес считается в два шага. Если операции только с конца — вектор быстрее.

Зато дек — единственный контейнер, который нужен для очереди с минимумом: там элементы выбрасываются и с хвоста (при добавлении нового), и с головы (при выходе из окна).

Очередь с приоритетом

Добавить элемент, посмотреть на максимум, удалить максимум. Добавление и удаление за $O(\log n)$, просмотр за $O(1)$.

priority_queue<int> q;
q.push(1); q.push(4); q.push(2);
q.top();     // 4
q.pop();     // удаляет максимум

// по возрастанию — минимум сверху
priority_queue<int, vector<int>, greater<int>> minq;

Дубликаты хранятся. Это не множество: если положить 5 5 3 5, размер будет 4, и top() вернёт пятёрку трижды подряд. Путать её с set — распространённая ошибка, и она меняет ответ, а не скорость.

Внутри — куча, та самая, из которой получается пирамидальная сортировка. Отсюда и ограничения: удалить произвольный элемент нельзя, найти элемент нельзя, пройтись по всем нельзя.

Взамен она заметно быстрее set при тех же логарифмах: у кучи меньше константа и лучше расположение в памяти.

Где нужна: алгоритм Дейкстры, слияние многих отсортированных списков, планировщики — везде, где на каждом шаге берётся минимум из меняющегося набора.

Сводка

	Добавить	Удалить	Доступ	Обход
vector	в конец	из конца	по индексу	да
stack	в конец	из конца	только вершина	нет
queue	в конец	из начала	оба конца	нет
deque	с обоих концов	с обоих	по индексу	да
priority_queue	любой	максимум	только максимум	нет