Контейнерні адаптери: std::stack, std::queue, std::priority_queue

1. Навіщо потрібні контейнерні адаптери

Якщо чесно, перше запитання новачка цілком природне: «Чому не можна просто взяти std::vector і робити все вручну? Навіщо мені якийсь std::stack?» І воно справді слушне: у ньому відчувається інженерна підозріливість, а в програмуванні вона рятує частіше, ніж кава.

Відповідь приблизно така: іноді нам потрібна не просто «коробка для зберігання», а контракт щодо способу доступу. Тобто важливо не лише де лежать елементи, а й якими операціями слід користуватися, щоб алгоритм залишався зрозумілим.

Наприклад, якщо за змістом задачі треба першою скасувати останню додану дію, це стек. Можна симулювати стек на основі vector, але адаптер stack робить дві корисні речі: по-перше, показує намір — читач коду одразу розуміє, що тут LIFO; по-друге, не дає вам «випадково» полізти всередину й зламати сенс структури.

Важливо також розуміти, що контейнерні адаптери — це частина стандартної бібліотеки, і до них висувають окремі вимоги та ведуть окремі обговорення на рівні комітету (WG21). Наприклад, зміни й уточнення, повʼязані зі stack/queue, періодично потрапляють до редакторських звітів та обговорень LWG.

Що таке «контейнерний адаптер» простими словами

Уявіть, що у вас є склад (контейнер), а вам потрібно організувати пункт видачі з жорсткими правилами. Склад може бути великим, із багатьма дверима, але пункт видачі каже: «Ми видаємо лише через одне віконце». Ось і є адаптер: «віконце» з правилами.

Технічно ідея така: адаптер зберігає всередині певний контейнер (зазвичай deque або vector), але назовні надає обмежений набір операцій. І це обмеження — не недолік, а перевага: воно захищає структуру даних від неправильного використання.

У трьох адаптерів, які ми сьогодні розбираємо, є три «моделі поведінки»:

• stack — LIFO (last in, first out): останнім поклали — першим дістали.
• queue — FIFO (first in, first out): першим прийшов — першим обслужили.
• priority_queue — «завжди віддавай найкращий»: найкращий за заданим правилом опиняється зверху.

А тепер важливий нюанс, який згодом позбавить багатьох проблем: адаптери майже завжди не дають ітераторів, тобто «пройтися range-for і подивитися всі елементи» не можна. І знову ж таки, не тому, що розробники STL щось забули, а тому, що вони свідомо не хочуть, щоб ви робили обхід там, де концептуально правильніше діставати елементи по одному.

2. std::stack: модель LIFO

Коли ви вперше бачите стек, він здається надто простим: «Ну… це як стопка тарілок». Так, саме так. І в програмуванні ця «стопка тарілок» трапляється постійно: скасування дій (undo), обробка вкладеності (дужки), повернення з функцій (стек викликів — ми про нього вже говорили), відкат кроків алгоритму.

В інтерфейсі std::stack є головне тріо: push(), top(), pop(). Плюс службові empty() і size(). І ось тут ховається класична пастка новачка: pop() нічого не повертає. Це зроблено навмисно, щоб у вас не виникало спокуси писати код, який випадково звертається до вже видаленого елемента. Тому правило просте: спочатку top(), потім pop().

Міні-приклад: стек чисел

#include <stack>
#include <iostream>

int main() {
    std::stack<int> st;
    st.push(10);
    st.push(20);

    std::cout << st.top() << '\n'; // 20
    st.pop();
    std::cout << st.top() << '\n'; // 10
}

Зверніть увагу: якщо ви спробуєте зробити int x = st.pop();, компілятор цілком слушно обуриться, бо pop() — це void.

Безпека: спочатку empty()

Якщо стек порожній, top() — це вже вихід за межі контракту. У STL це зазвичай призводить до невизначеної поведінки: або до падіння, або до дивних ефектів — тобто до класики жанру «працювало ж учора».

#include <stack>
#include <iostream>

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

    if (!st.empty()) {
        std::cout << st.top() << '\n';
        st.pop();
    } else {
        std::cout << "Стек порожній\n"; // Стек порожній
    }
}

3. std::queue: модель FIFO

Черга в житті — річ не надто приємна, але в коді вона часто робить поведінку системи зрозумілішою. FIFO особливо корисна, коли у вас є «вхідні події» й «обробка в порядку надходження»: запити користувача, завдання на друк, повідомлення з мережі. Це ми обговорюватимемо значно пізніше, але черга як структура даних потрібна вже зараз.

Інтерфейс std::queue влаштований так, щоб ви мислили двома кінцями: у «хвіст» додаємо (push()), з «голови» забираємо (front() + pop()). Для налагодження або рідкісних сценаріїв можна подивитися back() — тобто хто останній у черзі.

І знову важливе: pop() нічого не повертає — із тих самих міркувань безпеки, що й у стека.

Міні-приклад: черга рядків

#include <queue>
#include <string>
#include <iostream>

int main() {
    std::queue<std::string> q;
    q.push("перший");
    q.push("другий");

    std::cout << q.front() << '\n'; // перший
    q.pop();
    std::cout << q.front() << '\n'; // другий
}

«Зняти елемент» правильно: два кроки

Ось шаблон, який варто запамʼятати як базовий прийом:

#include <queue>

int main() {
    std::queue<int> q;
    q.push(7);

    if (!q.empty()) {
        int x = q.front();
        q.pop();
        (void)x;
    }
}

Якщо ви пишете обробник «поки черга не порожня», цей шаблон стане вашим найкращим другом.

4. std::priority_queue: черга з пріоритетом

Після FIFO черга з пріоритетом спочатку здається чимось не зовсім чесним: «Чому цей проліз без черги?» Бо в нього пріоритет. У коді це трапляється в планувальниках задач, в обробці термінових подій, у виборі наступного завдання для виконання, а інколи й в алгоритмах — наприклад, коли потрібно постійно брати мінімальний або максимальний елемент.

std::priority_queue — теж адаптер: він приховує внутрішню реалізацію й дає вам операції «додай елемент» і «дай найкращий елемент». Під «найкращим» зазвичай мається на увазі максимальний елемент: за замовчуванням угорі — максимум. Важливо: це не означає, що вся структура «повністю відсортована». Гарантія стосується лише top().

Тема priority_queue регулярно зʼявляється в обговореннях стандартної бібліотеки, зокрема через питання до конструкторів і специфікацій. Це ще раз підкреслює, що структура популярна, важлива й не така вже тривіальна всередині.

Міні-приклад: за замовчуванням угорі максимум

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(5);
    pq.push(42);

    std::cout << pq.top() << '\n'; // 42
    pq.pop();
    std::cout << pq.top() << '\n'; // 10
}

«Угорі мінімум»: змінюємо правило

У стандартній бібліотеці є готовий компаратор std::greater<T>. З ним «найкращим» стає мінімальний елемент, бо правило порівняння змінюється.

#include <queue>
#include <vector>
#include <functional>
#include <iostream>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(10);
    pq.push(5);
    pq.push(42);

    std::cout << pq.top() << '\n'; // 5
}

Синтаксис виглядає складніше, ніж є насправді. Тут просто написано: зберігаємо int, усередині використовуємо vector<int>, а «хто найкращий» визначаємо через greater<int>.

5. Корисні нюанси та візуальні моделі

Шпаргалка: stack vs queue vs priority_queue

Коли конструкцій стає багато, мозок починає вимагати шпаргалку. Це нормально: мозок не зобовʼязаний памʼятати все, він зобовʼязаний уміти швидко це відновити.

std::stack<T>

push(x)

top()

pop()

std::queue<T>

push(x)

front()

pop()

std::priority_queue<T>

push(x)

top()

pop()

Зауважте, що в усіх трьох є спільне правило безпеки: перед top()/front() варто перевірити, чи не порожньо (empty()), бо ці функції припускають, що елемент існує.

Чому в адаптерів немає ітераторів

На перших порах відсутність ітераторів дратує. Дуже хочеться написати for (auto x : st) і подивитися вміст. Але в цьому й полягає педагогічний сенс контейнерних адаптерів: вони змушують вас мислити операціями, а не «просто колекцією».

Стек і черга добрі саме тоді, коли вам не потрібно довільно заглядати всередину. Якщо вам увесь час хочеться «подивитися середину» або «видалити третій елемент», це сигнал, що модель даних вибрано неправильно: можливо, вам потрібен звичайний контейнер (deque, vector, list) або інша структура.

Іноді люди намагаються «обходити» адаптери: роблять копію й дістають елементи по одному, друкуючи їх. Це допустимо для налагодження, але в робочому коді часто означає, що структуру використовують не за призначенням. До того ж копіювання може бути дорогим, а головне — ви втрачаєте чіткість: читачеві доводиться розуміти, який саме прийом ви зараз застосовуєте і навіщо.

Маленькі схеми: LIFO і FIFO

Щоб закріпити модель, корисно бодай раз побачити її як потік дій, а не як набір «методів із підручника».

flowchart LR
    A[додати 1] --> B[додати 2] --> C[додати 3]
    C --> D[дістати -> 3]
    D --> E[дістати -> 2]
    E --> F[дістати -> 1]

Це стек: прийшли 1, 2, 3 — пішли 3, 2, 1.

flowchart LR
    A[додати 1] --> B[додати 2] --> C[додати 3]
    C --> D[дістати -> 1]
    D --> E[дістати -> 2]
    E --> F[дістати -> 3]

Це черга: прийшли 1, 2, 3 — пішли 1, 2, 3.

А ось priority_queue відрізняється тим, що порядок «виходу» залежить від правила «хто найкращий». Якщо правило — «більше число краще», то вийдуть 42, потім 10, потім 5, як у прикладі вище. За іншого компаратора порядок буде іншим.

6. Міні-диспетчер задач: приклад застосування адаптерів

Щоб адаптери не залишилися відірваними від практики, давайте продовжимо тему навчального застосунку. Припустімо, у нас є простий консольний диспетчер задач. Раніше ми могли зберігати задачі в std::vector, шукати їх, сортувати тощо. А сьогодні додамо три корисні можливості: undo, чергу вхідних задач, чергу термінових задач. Це реалістично й добре показує, чому адаптер — це «контейнер + намір».

Припустімо, задача виглядає так (ми вже знайомі зі struct із попередніх занять):

#include <string>

struct Task {
    std::string title;
    int priority = 0; // більше = важливіше
};

Undo як stack: скасовуємо останню дію

Undo логічно реалізувати стеком: остання зміна — перша на скасування.

#include <stack>
#include <string>

struct Action {
    std::string description;
};

int main() {
    std::stack<Action> undo;
    undo.push({"Додано завдання 'Купити молоко'"});
    undo.push({"Видалено завдання 'Прочитати книжку'"});

    Action last = undo.top();
    undo.pop();
    (void)last;
}

Так, тут дія поки що умовна — це просто текст. Але ідея зрозуміла: ви не «переглядаєте історію», а знімаєте її шар за шаром.

Вхідні задачі як queue: обробляємо в порядку надходження

Якщо задачі приходять як події, наприклад користувач швидко додав кілька пунктів, ми можемо поставити їх у FIFO-чергу на обробку.

#include <queue>
#include <string>

struct Task {
    std::string title;
    int priority = 0;
};

int main() {
    std::queue<Task> inbox;
    inbox.push({"Помити посуд", 1});
    inbox.push({"Оплатити рахунки", 2});

    Task t = inbox.front();
    inbox.pop();
    (void)t;
}

Термінові задачі як priority_queue: завжди беремо найважливішу

Якщо у нас є «звичайні» й «термінові» задачі, термінові зручно тримати окремо. Для початку нехай угорі буде максимум priority. Для цього потрібен компаратор.

#include <queue>
#include <vector>
#include <string>

struct Task {
    std::string title;
    int priority = 0;
};

struct ByPriority {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority; // у кого priority більше, той "кращий"
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, ByPriority> urgent;
    urgent.push({"Виправити критичну помилку", 100});
    urgent.push({"Рефакторинг коду", 10});

    Task best = urgent.top();
    urgent.pop();
    (void)best;
}

Тут важливо не стільки запамʼятати priority_queue<...> цілком, скільки вловити ідею: «усередині лежить контейнер, назовні доступний інтерфейс, а правило „хто кращий“ — це частина типу».

7. Типові помилки під час роботи з stack/queue/priority_queue

Помилка № 1: очікувати, що pop() повертає значення.
Після vector::pop_back() новачки іноді за інерцією намагаються написати x = pop(). В адаптерів stack/queue/priority_queue метод pop() повертає void. Правильний шаблон завжди двокроковий: спочатку top() або front(), потім pop(). Якщо ви переплутаєте, компілятор вас зупинить, але краще одразу виробити цю звичку, щоб код читався передбачувано.

Помилка № 2: викликати top()/front() на порожньому адаптері.
Адаптери не зобовʼязані «рятувати» вас під час виконання. Якщо структура порожня, звернення до top() або front() — це порушення контракту. Тому або ви перевіряєте empty(), або проєктуєте код так, щоб порожнеча була неможливою за логікою, і це прямо видно з контексту.

Помилка № 3: намагатися обійти адаптер за допомогою range-for і «подивитися все».
У stack, queue, priority_queue немає ітераторів — і це частина ідеї. Якщо вам постійно потрібен обхід, значить, потрібен інший контейнер або додаткова структура для перегляду чи логування. Спроби «дістати внутрішній контейнер» заради обходу зазвичай перетворюють код на крихкий трюк, який складно підтримувати.

Помилка № 4: використовувати адаптер там, де потрібен довільний доступ або видалення «з середини».
Стек і черга — це структури з дуже конкретною філософією. Якщо логіка програми вимагає «видали елемент за індексом» або «встав між другим і третім», то адаптер лише заважатиме. У такій ситуації краще чесно вибрати vector/deque/list і працювати з ними напряму, замість того щоб боротися з інтерфейсом, який спеціально зроблено «вузьким».

Помилка № 5: неправильно розуміти компаратор у priority_queue і дивуватися, «чому угорі не те».
У priority_queue компаратор задає правило, за яким визначається «найкращий» елемент. Якщо ви переплутаєте знак порівняння, то вгорі опиниться не найважливіший, а найменш важливий — і це особливо неприємно, бо код компілюватиметься й працюватиме, просто «дивно». Тому компаратор варто писати максимально прямолінійно й перевіряти на маленькому прикладі з 2–3 елементами, як у наших міні-фрагментах.