stack — adaptorul LIFO din STL

De ce contează?

Imaginează-ți un distribuitor de pahare de unică folosință din perete: împingi un pahar nou în tub și el alunecă deasupra; când iei unul, iei tot de sus. Tubul nu îți dă voie să umbli la mijloc — îți oferă doar capătul de sus. Așa lucrează și std::stack: îți ascunde tot, mai puțin vârful.

Ce este `std::stack` și de ce e un adaptor

Știi deja conceptul de stivă (LIFO — ultimul intrat, primul ieșit) și o aplicație clasică, verificarea parantezelor. Aici ne uităm la unealta din STL care îți oferă acest comportament gata făcut: std::stack.

std::stack nu este un container nou — este un adaptor de container. Asta înseamnă că nu stochează el însuși datele, ci „împachetează” un alt container și îi restrânge interfața doar la operațiile LIFO. Implicit, containerul de dedesubt este un std::deque.

De ce un adaptor și nu o structură separată? Pentru că nu vrei să reinventezi stocarea: deque știe deja să crească și să adauge/scoată eficient de la un capăt. stack doar ascunde tot ce nu ține de LIFO și îți lasă o interfață mică și sigură. Tocmai pentru că restrânge accesul, stack nu are iteratori și nu poate fi parcurs cu begin()/end().

Interfața completă e mică:

push(x) — pune x pe vârf;
top() — întoarce o referință la vârf (nu scoate);
pop() — scoate vârful (nu returnează valoarea);
size() — câte elemente sunt;
empty() — întoarce true dacă stiva e goală.

Exemplu pas cu pas

Pornim cu o stivă goală de întregi și executăm: push 3, push 7, push 2, pop, push 9.

push 3 → [3], vârf = 3
push 7 → [3, 7], vârf = 7
push 2 → [3, 7, 2], vârf = 2
pop → scoate vârful (2) → [3, 7], vârf = 7
push 9 → [3, 7, 9], vârf = 9

stack	3	7	9
			top

Doar vârful (9) e accesibil. push adaugă aici, pop scoate de aici.

Implementare C++

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> st;             // adaptor peste deque, implicit

    st.push(3);
    st.push(7);
    st.push(2);

    cout << st.top() << "\n";  // 2  (varful, fara sa scoata)
    st.pop();                  // scoate 2; nu returneaza nimic
    cout << st.top() << "\n";  // 7

    st.push(9);                // stiva: 3 7 9
    cout << st.size() << "\n"; // 3

    // golim stiva element cu element (singurul mod de a o parcurge)
    while (!st.empty()) {
        cout << st.top() << " ";  // 9 7 3  (de la varf spre baza)
        st.pop();
    }
    cout << "\n";

    cout << st.empty() << "\n"; // 1  (acum e goala)
    return 0;
}

Rezultatul afișat:

Observă ultima buclă: pentru că nu există iteratori, „parcurgerea” unei stive înseamnă de fapt să o golești cu top() + pop(), iar elementele ies în ordine inversă față de cum au intrat.

Complexitate

Operație	Timp	Spațiu
push / pop / top	O(1) amortizat	—
size / empty	O(1)	—
Stocarea a n elemente	—	O(n)

Observația-cheie

top() întoarce o referință, deci o poți și modifica direct: st.top() += 1; mărește vârful fără să-l scoți. pop(), în schimb, întoarce void — îți dă doar acțiunea, nu și valoarea.

Greșeli frecvente

Greșeli frecvente cu std::stack:

pop() după care vrei valoarea: pop() nu returnează nimic. Citește întâi cu top(), apoi pop() — niciodată invers.
top() sau pop() pe stivă goală: comportament nedefinit (poate da crash sau gunoi). Testează mereu !st.empty() înainte.
Cauți iteratori: for (auto x : st) sau st.begin() nu compilează — adaptorul nu expune iteratori. Singura cale de parcurgere e golirea cu top()/pop().
Crezi că pop() îți dă elementul scos: în alte limbaje da, în C++ nu. E o sursă tipică de bug-uri când portezi cod.

Vizualizare

Urmărește cum push urcă un element pe vârf și pop îl coboară — atinse doar de la capătul de sus:

Indiciu

Folosește ← / → pentru a derula pas cu pas și fii atent: la fiecare moment, singurul element evidențiat este vârful — exact ce-ți expune top().

Recapitulare

std::stack este un adaptor peste deque (implicit), nu un container nou — restrânge interfața la LIFO și de aceea nu are iteratori.
Interfața e mică: push, top, pop, size, empty; top() citește, pop() doar scoate (întoarce void).
Verifică mereu !st.empty() înainte de top()/pop(), iar pentru a parcurge stiva, golește-o cu top() + pop() (ies în ordine inversă).

Ce este std::stack și de ce e un adaptor