Stivă, coadă și heap: stack, queue, priority_queue

Stiva, coada și coada de priorități aleg diferit următorul element de prelucrat. Stiva folosește ultimul element introdus, coada pe primul, iar coada de priorități pe cel cu prioritatea cea mai mare conform comparatorului. Această alegere influențează algoritmul, nu doar sintaxa programului.

În biblioteca standard, std::stack, std::queue și std::priority_queue sunt adaptoare de containere. Ele oferă operațiile potrivite modelului, fără să expună o parcurgere obișnuită prin iteratori.

Cum funcționează

Stiva respectă regula LIFO: last in, first out. push adaugă la vârf, top citește vârful, iar pop îl elimină. Ea apare în apelurile recursive, verificarea parantezelor și explorarea în adâncime. Când vrem să refacem o ordine în sens invers, stiva este adesea un model natural. Totuși, recursia include și starea apelurilor, nu numai o colecție de valori.

Coada respectă FIFO: first in, first out. push adaugă la sfârșit, front citește începutul, iar pop elimină începutul. Ea păstrează ordinea sosirii și este structura naturală pentru BFS pe un graf neponderat. back citește ultimul element, fără să schimbe ordinea de eliminare. Citirea și eliminarea sunt operații distincte: pop nu întoarce valoarea eliminată.

O coadă de priorități nu păstrează ordinea inserării. Cu setările implicite, priority_queue oferă maximul prin top. Pentru minim folosim comparatorul std::greater. Implementarea standard uzuală organizează datele ca heap într-un container cu acces aleator. Un heap binar este un arbore binar complet: toate nivelurile sunt pline, cu posibila excepție a ultimului, completat de la stânga la dreapta. În reprezentarea de la indicele zero, copiii lui i sunt 2i+1 și 2i+2, când există.

Proprietatea de max-heap spune că părintele nu este mai mic decât copiii săi. Ea garantează maximul la rădăcină, dar nu sortează toate pozițiile. Inserarea repară drumul în sus, iar eliminarea rădăcinii înlocuiește vârful cu ultimul element și repară în jos. Programul citește 1 <= n <= 100000 de valori și le introduce în toate cele patru structuri pentru a compara ordinea eliminării. Într-o aplicație alegem numai structura necesară.

Exemplu urmărit pas cu pas

Pentru 4,1,3, stiva produce 3,1,4, iar coada 4,1,3. Coada de priorități implicită produce 4,3,1, iar varianta cu minim 1,3,4.

Dacă introducem încă un 4, containerele păstrează și acea apariție. Spre deosebire de set, acestea nu elimină automat dublurile. Pentru obiecte cu aceeași prioritate, priority_queue nu promite păstrarea ordinii inițiale; dacă aceasta contează, includem un criteriu de departajare, precum numărul de ordine.

Implementare C++17

#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::stack<int> s;
    std::queue<int> q;
    std::priority_queue<int> mx;
    std::priority_queue<int, std::vector<int>, std::greater<int>> mn;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        s.push(x);
        q.push(x);
        mx.push(x);
        mn.push(x);
    }
    while (!s.empty()) {
        std::cout << s.top();
        s.pop();
        std::cout << (s.empty() ? '\n' : ' ');
    }
    while (!q.empty()) {
        std::cout << q.front();
        q.pop();
        std::cout << (q.empty() ? '\n' : ' ');
    }
    while (!mx.empty()) {
        std::cout << mx.top();
        mx.pop();
        std::cout << (mx.empty() ? '\n' : ' ');
    }
    while (!mn.empty()) {
        std::cout << mn.top();
        mn.pop();
        std::cout << (mn.empty() ? '\n' : ' ');
    }
}

De ce funcționează și cât costă

Fiecare adaptor menține invariantul său: vârful stivei este cea mai recentă inserare rămasă, începutul cozii cea mai veche, iar rădăcina heap-ului are prioritatea extremă. Repetarea accesului urmat de eliminare produce ordinea corespunzătoare.

Cu containerele implicite, operațiile de bază ale stivei și cozii sunt constante. priority_queue oferă acces la vârf O(1), iar inserarea și eliminarea necesită O(log n) comparații; o realocare a vectorului suport poate avea cost suplimentar amortizat. Memoria totală este O(n).

Greșeli frecvente

Verifică empty înainte de top, front sau pop. Nu confunda un heap cu un vector sortat. Nu presupune că o coadă de priorități este potrivită pentru BFS neponderat doar fiindcă include cuvântul coadă. Comparatorul trebuie să definească o ordine strictă.

Exersează

Ce structură păstrează ordinea cererilor sosite și ce structură alege mereu sarcina cu cost minim?

Rezolvare explicată: O coadă FIFO păstrează ordinea sosirii. O coadă de priorități configurată pentru minim alege costul minim; pentru egalități trebuie stabilită separat ordinea dorită.

Continuă să înveți

BFS, arbori și Dijkstra.

Întrebări frecvente

Ce diferență există între stack și queue?

Stack elimină ultima valoare introdusă, iar queue pe prima. Alegerea determină ordinea explorării sau procesării.

De ce pop nu se folosește ca valoare?

În aceste adaptoare, pop doar elimină. Citește întâi top sau front, apoi elimină elementul dacă ai nevoie de valoarea lui.

Cum obțin minimul într-un priority_queue?

Folosește un comparator precum std::greater împreună cu tipul containerului suport. top va oferi atunci cel mai mic element.

Heap-ul este sortat?

Nu. Relația este între fiecare părinte și copiii săi. Frații și subarborii nu sunt ordonați global.

Un arbore binar complet este mereu heap?

Nu. Complet descrie forma arborelui. Pentru heap mai trebuie respectată proprietatea de ordine dintre părinte și copii.