Stiva

Stiva este o structură LIFO („ultimul intrat, primul ieșit”). Adăugăm și eliminăm numai la vârful ei. Dacă introducem A, apoi B, apoi C, prima valoare extrasă este C. În Python, o listă implementează direct operațiile: s = ["A", "B", "C"], s[-1] citește C, iar s.pop() elimină și întoarce C.

Stiva este o structură de date liniară cu acces la un singur capăt, numit vârf. Ordinea de acces este LIFO: ultimul element introdus este primul scos. Operațiile fundamentale sunt: introducerea unui element în vârf (push), eliminarea elementului din vârf (pop), citirea vârfului fără eliminare (top) și testul de stivă goală. În implementarea cu tablou se păstrează indicele vârfului vf: stiva goală are vf = 0, introducerea crește indicele și scrie elementul, iar eliminarea scade indicele. Citirea sau eliminarea cere ca stiva să nu fie goală (vf > 0), iar introducerea cere să existe loc în tablou. Toate operațiile costă un număr constant de pași, iar $k$ elemente ocupă spațiu proporțional cu $k$. În C++, std::stack oferă push, top, pop și empty; pop() nu întoarce elementul, deci valoarea se citește înainte cu top(). În Python, o listă joacă rolul stivei: append introduce, pop() elimină și întoarce vârful, iar s[-1] îl citește. Stiva apelurilor de funcții are aceeași ordine LIFO: ultimul apel început se încheie primul.

Exemplul 1 — stiva cu tablou.

#include <iostream>
using namespace std;
int main() {
    int s[10], vf = 0;
    s[++vf] = 2; s[++vf] = 5; s[++vf] = 7;
    if (vf > 0) {
        int scos = s[vf];
        --vf;
        if (vf > 0) cout << scos << " " << s[vf];
        else cout << scos;
    }
    return 0;
}

După cele trei inserări, vf = 3 și s[3] = 7. Se salvează 7 în scos, vf scade la 2 și se citește noul vârf, s[2] = 5. Ieșirea este 7 5. O nouă extragere ar scoate 5 și ar lăsa 2 în vârf.

Exemplul 2 — verificarea parantezelor. Un șir de paranteze rotunde este corect dacă fiecare paranteză închisă are o pereche deschisă și la sfârșit nu rămân paranteze deschise. Se parcurge șirul: o paranteză deschisă se introduce în stivă, iar una închisă scoate din stivă; dacă stiva este goală când trebuie scoasă o paranteză, șirul este greșit. Pentru (()()) stiva ajunge la dimensiunea 1, 2, 1, 2, 1, 0 și este goală la sfârșit: șirul este corect. Pentru (() stiva rămâne cu un element, deci șirul este greșit; pentru ())( a treia paranteză încearcă să scoată dintr-o stivă goală, deci șirul este greșit. Rezultatele pentru cele trei șiruri sunt corect, greșit, greșit.

Exemplul 3 — inversarea unui text (Python).

s = []
for ch in "mare":
    s.append(ch)
rezultat = ""
while s:
    rezultat += s.pop()
print(rezultat)

Literele sunt introduse în ordinea m, a, r, e și scoase în ordinea inversă, deci se afișează eram. Condiția while s este adevărată cât timp lista nu este goală, adică este testul de stivă goală.

Urmărește conținutul stivei și valoarea lui vf după fiecare operație, nu doar rezultatul final. Elementul scos este cel din vârf, iar eliminarea nu șterge valoarea din memorie, ci doar scade vf. Dacă o secvență scoate dintr-o stivă goală, rezultatul nu este definit și subiectele nu cer acest caz decât ca eroare. Distinge top, care citește, de pop, care elimină.

Exemplul 4 — urmărirea unui fragment. Ce se afișează în urma executării secvenței de mai jos?

int s[10], vf = 0;
s[++vf] = 3;
s[++vf] = 5;
--vf;
s[++vf] = 7;
int a = s[vf--];
int b = s[vf--];
cout << a << b << vf;

• a) 750
• b) 730
• c) 537
• d) 731

Răspunsul corect este b). După primele două inserări stiva conține 3 și 5, cu vf = 2. Instrucțiunea --vf elimină 5 și lasă vf = 1. Apoi 7 este introdus pe poziția 2, deci stiva conține 3 și 7. În int a = s[vf--] se citește vârful, 7, apoi vf scade la 1; în int b = s[vf--] se citește 3, iar vf ajunge la 0. Se afișează 7, 3 și 0. Varianta a) presupune că 5 a rămas în stivă.

Greșeli frecvente

• Greșit: stiva este o structură FIFO.
  Corect: este LIFO, iar ultimul element introdus este primul scos.
• Greșit: în C++, pop() din std::stack întoarce elementul eliminat.
  Corect: elimină vârful fără să-l întoarcă; valoarea se citește înainte cu top().
• Greșit: se poate scoate dintr-o stivă fără a testa dacă este goală.
  Corect: testul vf > 0 sau !empty() este obligatoriu.

Înainte și după