De ce contează?
Un chelner ține minte comenzile încă neaduse la mese. Când vine un fel de mâncare, îl duce la cea mai recentă comandă potrivită și o bifează. Stiva e exact acest carnețel de „comenzi nerezolvate" — ții ce ai început și nu ai terminat, până apare ce le rezolvă.
Ideea care leagă toate problemele cu stivă
Privite separat, parantezele, recursivitatea și „următorul element mai mare" par fără legătură. Au însă același miez:
Stiva reține elementele deschise / nerezolvate, în ordinea în care au apărut, până când întâlnești ceva care le închide.
Când apare „rezolvatorul", el acționează asupra celui mai recent element nerezolvat — vârful. De aici LIFO.
Întreabă-te mereu: ce înseamnă aici „nerezolvat"? și ce element îl rezolvă? Dacă răspunsul e „cel mai recent deschis se închide primul", problema e o stivă.
Aceeași schemă, trei probleme
| Problemă | Ce e „nerezolvat" (pe stivă) | Ce îl „rezolvă" (pop) |
|---|---|---|
| paranteze corecte | paranteză deschisă | paranteza închisă care i se potrivește |
| următorul mai mare | element fără vecin mai mare la dreapta | un element mai mare care apare |
| recursivitate | apel de funcție neîncheiat | revenirea (return) din apel |
În toate, scheletul codului e identic: pui pe stivă când „deschizi", verifici/scoți vârful când „închizi".
Scheletul comun
stack<...> s;
for (fiecare element) {
// cat timp varful e "rezolvat" de elementul curent:
while (!s.empty() && seRezolva(s.top(), element)) {
// foloseste s.top() (raspuns, verificare)
s.pop();
}
if (elementul "deschide" ceva) s.push(element);
}
// ce ramane pe stiva = nerezolvat la final (paranteze lipsa, -1 la next-greater)Diferă doar seRezolva și ce faci la pop — restul e mereu la fel.
Cum recunoști o problemă de stivă
- Procesezi elementele în ordine, o singură trecere.
- Unele elemente „așteaptă" un partener viitor.
- Partenerul rezolvă cel mai recent element care aștepta.
Dacă bifezi aceste trei, gândește stivă.
Stiva monotonă (următorul mai mare/mic) e doar acest tipar cu o condiție de „rezolvare" bazată pe comparație. Odată ce vezi scheletul comun, problemele aparent grele devin variații pe aceeași temă.
Capcane când modelezi cu stivă:
- Nu identifici clar „nerezolvatul": dacă nu poți spune ce ține stiva, probabil structura nu e potrivită.
- Folosești stiva când rezolvarea nu e LIFO: dacă partenerul rezolvă cel mai vechi element care așteaptă (nu cel mai recent), ai nevoie de coadă, nu de stivă.
- Uiți elementele rămase: ce e pe stivă la final nu a fost rezolvat — tratează-l (eroare la paranteze,
-1la next-greater). - Pui prea mult pe stivă: ține doar ce e strict necesar (de obicei indici sau parteneri deschiși), nu tot vectorul.
Recapitulare
- Toate problemele cu stivă au același miez: stiva ține elementele nerezolvate până apare ce le închide.
- Rezolvarea acționează mereu asupra vârfului (cel mai recent nerezolvat) — de aceea ordinea e LIFO.
- Recunoști tiparul când procesezi în ordine, unele elemente așteaptă un partener, iar partenerul rezolvă cel mai recent element în așteptare.