Stiva — ultimul intrat, primul ieșit

De ce contează?

Gândește-te la un teanc de farfurii. Pui farfurii noi deasupra și tot de deasupra iei când ai nevoie. Nu poți scoate farfuria de jos fără să le ridici pe cele de deasupra. Asta este o stivă: ultimul pus, primul luat.

Ce este o stivă?

O stivă (stack) este o structură în care adaugi și scoți elemente doar de la un capăt, numit vârf. Respectă principiul LIFO — Last In, First Out: ultimul element intrat e primul care iese.

Operațiile sunt trei, toate O(1):

push — pune un element pe vârf;
pop — scoate elementul din vârf;
top — citește vârful fără să-l scoți.

stiva	3	7	2	9
				varf

Vârful e ultimul element pus (9). push/pop lucrează doar aici.

Cum funcționează, pas cu pas

Pornim cu stiva goală și executăm: push 3, push 7, push 2, pop, push 9.

push 3 → [3]
push 7 → [3, 7]
push 2 → [3, 7, 2]
pop → scoate 2 → [3, 7]
push 9 → [3, 7, 9]

Observația-cheie

Nu ai acces la mijloc. Singurul element „vizibil” e vârful. Dacă vrei al doilea element, trebuie să scoți întâi vârful.

Stiva din STL

În C++ folosești stack din <stack> — nu o implementezi de mână:

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

int main() {
    stack<int> st;
    st.push(3);
    st.push(7);
    st.push(2);
    cout << st.top() << "\n";   // 2 (varful)
    st.pop();                   // scoate 2
    cout << st.top() << "\n";   // 7
    cout << st.size() << "\n";  // 2
    cout << st.empty() << "\n"; // 0 (nu e goala)
    return 0;
}

Aplicație clasică: paranteze corecte

O stivă rezolvă elegant verificarea parantezelor. La fiecare ( pui pe stivă; la fiecare ) trebuie să existe o paranteză deschisă de scos.

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

bool parantezeCorecte(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') {
            st.push(c);                    // deschidem
        } else if (c == ')') {
            if (st.empty()) return false;  // inchidem ce nu s-a deschis
            st.pop();                      // potrivim o pereche
        }
    }
    return st.empty();                     // toate au fost inchise
}

int main() {
    cout << parantezeCorecte("(()())") << "\n";  // 1
    cout << parantezeCorecte("(()")    << "\n";  // 0
    cout << parantezeCorecte("())(")   << "\n";  // 0
    return 0;
}

De ce merge? Ultima paranteză deschisă trebuie închisă prima — fix ordinea LIFO. La final, o stivă goală înseamnă că fiecare ( și-a găsit ).

Complexitate

Operație	Timp	Spațiu
push / pop / top / empty	O(1)	—
Verificare paranteze (n caractere)	O(n)	O(n)

Greșeli frecvente

Greșeli frecvente de concurs:

top() / pop() pe stivă goală: comportament nedefinit. Testează !st.empty().
pop() întoarce valoarea? NU — pop() doar scoate. Citește cu top() ÎNAINTE de pop().
Confuzia cu coada: stiva e LIFO, nu FIFO. Dacă ordinea iese „pe dos” față de cum te aștepți, ai confundat structurile.
Uiți verificarea finală: la paranteze, (() trece de buclă, dar stiva rămâne nevidă → răspuns greșit dacă nu testezi st.empty() la final.

Vizualizare

Urmărește push și pop pe vârful stivei:

Indiciu

Observă că toate operațiile ating doar vârful. Folosește ← / → pentru a vedea cum crește și scade stiva pas cu pas.

Recapitulare

Stiva e LIFO: push/pop/top lucrează doar pe vârf, toate O(1).
Citește vârful cu top() înainte de pop() — pop() nu returnează valoarea.
Modelul natural pentru ordine inversă: paranteze, evaluări, „undo”.