1
1. Ce este o stiva?
O stiva (engl. stack) este o structura de date liniara care respecta principiul LIFO: Last In, First Out — ultimul element adaugat este primul care poate fi scos.
Analogie sigura — stiva de farfurii curate:
Pui o farfurie pe stiva (push). Pui inca una deasupra (push). Cand ai nevoie, iei mereu de deasupra (pop) — niciodata de la baza.
Acelasi principiu apare in natura digitala: butonul Undo din editoare, apelurile de functii (call stack), expresiile cu paranteze.
30 ← varf (top)
20
10 ← baza
Stiva de mai sus contine elementele 10, 20, 30 (in aceasta ordine push). Urmatorul pop va returna 30.
2
2. Operatiile de baza
Stiva are 4 operatii fundamentale, toate cu complexitate O(1):
- push(x) — adauga elementul x pe varful stivei
- pop() — scoate si returneaza elementul din varf (stiva nu trebuie sa fie goala)
- top() — returneaza elementul din varf fara a-l scoate
- is_empty() — returneaza True daca stiva este goala
Complexitate O(1)
Toate cele 4 operatii ruleaza in timp constant O(1) — indiferent de cate elemente are stiva. Acest lucru este posibil deoarece lucram mereu cu un singur capat: varful.
| Operatie | Ce face | Stiva inainte | Stiva dupa | Returneaza |
|---|---|---|---|---|
push(5) | Adauga 5 pe varf | [10, 20] | [10, 20, 5] | - |
pop() | Scoate varful | [10, 20, 5] | [10, 20] | 5 |
top() | Citeste varful | [10, 20] | [10, 20] | 20 |
is_empty() | Verifica daca e goala | [10, 20] | [10, 20] | False |
3
3. Implementare cu lista Python
In Python, lista poate juca rolul de stiva fara nicio structura suplimentara. Varful stivei este sfarsitul listei (indexul -1). Aceasta asigura O(1) pentru append si pop.
Implementare cu functii simple:
# Implementare stiva cu lista Python stiva = [] # push - adaugam elemente stiva.append(10) stiva.append(20) stiva.append(30) print("Stiva dupa 3 push-uri:", stiva) print("Top (varful stivei):", stiva[-1]) # pop - scoatem elementul din varf extras = stiva.pop() print("Pop a returnat:", extras) print("Stiva dupa pop:", stiva)
Output real (rulat cu python):
Stiva dupa 3 push-uri: [10, 20, 30] Top (varful stivei): 30 Pop a returnat: 30 Stiva dupa pop: [10, 20]
Functii cu verificare de erori:
def push(s, valoare): s.append(valoare) def pop(s): if not is_empty(s): return s.pop() raise IndexError("Stiva este goala!") def top(s): if not is_empty(s): return s[-1] raise IndexError("Stiva este goala!") def is_empty(s): return len(s) == 0 # Utilizare stiva = [] push(stiva, 5) push(stiva, 12) push(stiva, 7) print("Stiva:", stiva) print("Top:", top(stiva)) print("Pop:", pop(stiva)) print("Stiva dupa pop:", stiva) print("Este goala?", is_empty(stiva))
Output real (rulat cu python):
Stiva: [5, 12, 7] Top: 7 Pop: 7 Stiva dupa pop: [5, 12] Este goala? False
⚠ Eroare frecventa
Nu folosi lista.insert(0, x) pentru push! Acel apel are complexitate O(n) deoarece deplaseaza toate elementele. Varful stivei trebuie sa fie la sfarsitul listei, nu la inceput.
4
4. Trasarea executiei pas cu pas
La subiectele de tip BAC, vei fi intrebat sa urmaresti o secventa de operatii si sa determini starea stivei sau ce returneaza anumite apeluri. Metoda: traseaza stiva ca o lista si actualizeaz-o la fiecare pas.
# Urmarirea executiei - trasare pas cu pas stiva = [] operatii = [ ("push", 1), ("push", 2), ("push", 3), ("pop", None), ("push", 4), ("pop", None), ("pop", None), ] print(f"{'Operatie':<15} {'Stiva dupa':<25} {'Returnat'}") print("-" * 50) for op, val in operatii: if op == "push": stiva.append(val) print(f"push({val}) {str(stiva):<25} -") else: ret = stiva.pop() print(f"pop() {str(stiva):<25} {ret}")
Output real (rulat cu python):
Operatie Stiva dupa Returnat -------------------------------------------------- push(1) [1] - push(2) [1, 2] - push(3) [1, 2, 3] - pop() [1, 2] 3 push(4) [1, 2, 4] - pop() [1, 2] 4 pop() [1] 2
Tabel de trasare (format BAC):
| Pas | Operatie | Stiva (baza → varf) | Returnat |
|---|---|---|---|
| 1 | push(1) | [1] | - |
| 2 | push(2) | [1, 2] | - |
| 3 | push(3) | [1, 2, 3] | - |
| 4 | pop() | [1, 2] | 3 |
| 5 | push(4) | [1, 2, 4] | - |
| 6 | pop() | [1, 2] | 4 |
| 7 | pop() | [1] | 2 |
5
5. Clasa Stiva in Python (OOP)
O implementare mai robusta incapsuleaza stiva intr-o clasa. Datele sunt ascunse (atribut privat
_date); utilizatorul interactioneaza doar prin metodele publice.
# Clasa Stiva - implementare OOP class Stiva: def __init__(self): self._date = [] # atribut privat def push(self, valoare): self._date.append(valoare) def pop(self): if self.este_goala(): raise IndexError("Stiva este goala!") return self._date.pop() def top(self): if self.este_goala(): raise IndexError("Stiva este goala!") return self._date[-1] def este_goala(self): return len(self._date) == 0 def dimensiune(self): return len(self._date) def __repr__(self): return f"Stiva({self._date})" # Test s = Stiva() s.push(100) s.push(200) s.push(300) print("Stiva:", s) print("Dimensiune:", s.dimensiune()) print("Top:", s.top()) print("Pop:", s.pop()) print("Stiva dupa pop:", s)
Output real (rulat cu python):
Stiva: Stiva([100, 200, 300]) Dimensiune: 3 Top: 300 Pop: 300 Stiva dupa pop: Stiva([100, 200])
6
6. Clasa Stiva in C++ EXCLUSIV INTENSIV
⚡ Sectiune exclusiva pentru intensiv informatica
La profilul intensiv vei implementa aceeasi logica in C++. Utilizam std::vector<int> ca structura interna (echivalent listei Python). C++ ofera si std::stack din STL — prezentat mai jos ca referinta.
Implementare cu clasa proprie (vector intern):
#include <iostream> #include <vector> #include <stdexcept> using namespace std; class Stiva { private: vector<int> date; public: void push(int valoare) { date.push_back(valoare); } int pop() { if (esteGoala()) throw runtime_error("Stiva este goala!"); int val = date.back(); date.pop_back(); return val; } int top() const { if (esteGoala()) throw runtime_error("Stiva este goala!"); return date.back(); } bool esteGoala() const { return date.empty(); } int dimensiune() const { return (int)date.size(); } }; int main() { Stiva s; s.push(100); s.push(200); s.push(300); cout << "Dimensiune: " << s.dimensiune() << endl; cout << "Top: " << s.top() << endl; cout << "Pop: " << s.pop() << endl; cout << "Dimensiune dupa pop: " << s.dimensiune() << endl; cout << "Top dupa pop: " << s.top() << endl; return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
Dimensiune: 3 Top: 300 Pop: 300 Dimensiune dupa pop: 2 Top dupa pop: 200
Alternativa STL — std::stack (pentru uz rapid in concursuri):
#include <iostream> #include <stack> using namespace std; int main() { stack<int> s; s.push(10); s.push(20); s.push(30); cout << "Dimensiune: " << s.size() << endl; cout << "Top: " << s.top() << endl; s.pop(); // pop() NU returneaza valoarea in STL! cout << "Dupa pop, top: " << s.top() << endl; cout << "Este goala? " << (s.empty() ? "da" : "nu") << endl; return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
Dimensiune: 3 Top: 30 Dupa pop, top: 20 Este goala? nu
⚠ Atentie STL: pop() nu returneaza valoarea!
In std::stack, pop() sterge varful dar nu il returneaza. Daca ai nevoie de valoare, mai intai top(), apoi pop(): int v = s.top(); s.pop();