Aplicații specifice ale stivei

De ce contează?

Citești o carte și pui semne de carte de fiecare dată când deschizi o paranteză din poveste (un flashback, o digresiune). Când se închide, scoți ultimul semn pus. Creierul tău folosește o stivă ca să țină minte „unde am rămas" — și la fel fac multe programe.

Când să te gândești la o stivă

Stiva e unealta potrivită când:

contează cel mai recent element încă „deschis" / nerezolvat;
trebuie să inversezi o ordine;
trebuie să revii pe pași (înapoi, anulare).

Observația-cheie

Semnalul mental: „am nevoie să mă întorc la ultimul lucru pe care l-am început și nu l-am terminat". Acel „ultimul nerezolvat" e exact vârful unei stive.

Aplicația 1: inversarea unei secvențe

Pui totul cu push, scoți totul cu pop → ordine inversă:

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

int main() {
    int v[5] = {1, 2, 3, 4, 5};
    stack<int> s;
    for (int i = 0; i < 5; i++) s.push(v[i]);
    while (!s.empty()) {
        cout << s.top() << " ";   // 5 4 3 2 1
        s.pop();
    }
    cout << "\n";
    return 0;
}

Aplicația 2: stiva apelurilor (recursivitate)

Fiecare apel recursiv se pune pe stiva apelurilor; când o funcție se termină, se scoate de sus. Recursivitatea este o stivă administrată automat de calculator. De aceea o recursivitate prea adâncă dă stack overflow — stiva apelurilor se umple.

Aplicația 3: evaluarea expresiilor

La evaluarea expresiilor cu paranteze și operatori, o stivă ține operanzii sau operatorii încă neprocesați. Când întâlnești un operator, scoți de pe stivă operanzii de care ai nevoie. Forma postfixată (poloneză inversă) se evaluează direct cu o singură stivă.

Aplicația 4: anularea (Undo)

Fiecare acțiune a utilizatorului se pune pe o stivă. La Undo, scoți vârful (ultima acțiune) și o anulezi. Comportamentul „anulează cea mai recentă" e LIFO pur.

Tiparul comun

Aproape toate aplicațiile urmează același schelet:

stack<...> s;
for (fiecare element din intrare) {
    if (elementul "deschide" ceva) s.push(...);
    else if (elementul "inchide" ceva) {
        // foloseste / verifica s.top(), apoi s.pop()
    }
}

Vizualizare

Urmărește comportamentul LIFO comun tuturor aplicațiilor: elementele intră cu push și ies cu pop mereu de la vârf, în ordine inversă față de cum au fost adăugate:

Greșeli frecvente

Capcane la aplicațiile stivei:

Folosești stiva când ai nevoie de acces aleator: dacă trebuie să atingi elemente din mijloc, stiva nu e potrivită — folosește un vector.
Uiți să verifici empty() înainte de top()/pop(): în aplicații (paranteze, expresii) stiva se poate goli neașteptat. Verifică mereu.
Confuzi stiva cu coada: pentru „primul venit, primul servit" (procesare în ordine) ai nevoie de coadă, nu de stivă.
Recursivitate prea adâncă: stiva apelurilor are limită. Pentru adâncimi mari, transformă recursivitatea într-o stivă explicită.

Recapitulare

Stiva se potrivește când contează cel mai recent element nerezolvat, când inversezi o ordine sau revii pe pași.
Aplicații clasice: inversare, stiva apelurilor (recursivitate), evaluarea expresiilor, Undo.
Tiparul comun: push la „deschidere", verifici top() și pop() la „închidere" — mereu cu empty() verificat.