Invatare Atomica

Stiva — Structura LIFO

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei intelege ce este o stiva (structura LIFO), vei invata operatiile fundamentale push / pop / top si vei implementa o stiva folosind lista Python (si, la nivel intensiv, o clasa C++).

Dupa aceasta lectie vei putea:

  • Sa definesti stiva si sa explici principiul LIFO
  • Sa descrii si sa aplici operatiile push, pop, top, is_empty
  • Sa implementezi o stiva cu lista Python si sa urmaresti executia pas cu pas
  • Sa identifici complexitatea O(1) a fiecarei operatii
  • Sa scrii o clasa Stiva completa in Python si (exclusiv intensiv) in C++
  • Sa rezolvi exercitii de tip BAC cu stive

Incearca singur!

Provocare:

Ai o stiva goala. Aplici operatiile: push(3), push(7), push(1), pop(), push(5), pop(). Ce element ramane in varful stivei la final? Scrie raspunsul tau inainte sa citesti lectia.

💡 Ai nevoie de un indiciu?

Traseaza pas cu pas stiva ca o lista verticala. Varful este intotdeauna ultimul element adaugat care nu a fost inca scos.

push adauga pe varf, pop scoate de pe varf — LIFO = Last In, First Out.

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
1push(1)[1]-
2push(2)[1, 2]-
3push(3)[1, 2, 3]-
4pop()[1, 2]3
5push(4)[1, 2, 4]-
6pop()[1, 2]4
7pop()[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();

Exercitii practice

Exercitiul 1 (Nivel minim) — Trasare manuala

Dati o stiva initial goala, urmariti urmatoarea secventa de operatii si completati tabelul de trasare:

push(5), push(3), push(8), pop(), push(2), top()

Completati: Ce returneaza top() la final? Care este continutul final al stivei (de la baza la varf)?

Vezi rezolvarea

Trasare pas cu pas (stiva se scrie de la baza spre varf):

  1. push(5) -> stiva = [5]
  2. push(3) -> stiva = [5, 3]
  3. push(8) -> stiva = [5, 3, 8]
  4. pop() scoate varful -> returneaza 8, stiva = [5, 3]
  5. push(2) -> stiva = [5, 3, 2]
  6. top() citeste varful fara sa il scoata -> returneaza 2, stiva ramane [5, 3, 2]

Raspunsuri: top() returneaza 2. Continutul final al stivei, de la baza la varf, este 5, 3, 2.

Exercitiul 2 (Nivel standard) — Inversarea unui sir

Folosind o stiva, scrie un program Python care citeste un cuvant de la utilizator si il afiseaza in ordine inversa. De exemplu, pentru "ABCDE" va afisa "EDCBA".

Indiciu: push fiecare caracter, apoi pop pana cand stiva este goala.

Vezi rezolvarea

Rezolvare cu stiva (lista Python), exact metoda din lectie: push fiecare caracter, apoi pop pana se goleste.

cuvant = input("Introdu un cuvant: ")
stiva = []
for caracter in cuvant:
    stiva.append(caracter) # push
rezultat = ""
while stiva:
    rezultat += stiva.pop() # pop de pe varf
print(rezultat)

Pentru "ABCDE": push pune A, B, C, D, E pe stiva (E ajunge in varf). Pop scoate mereu ultimul intrat: E, D, C, B, A -> rezultatul afisat este "EDCBA". Functioneaza pentru ca principiul LIFO inverseaza automat ordinea intrarii.

Exercitiul 3 (Nivel performanta) — Verificare paranteze balansate

Scrie o functie Python paranteze_ok(sir) care primeste un sir de caractere continand doar paranteze rotunde ( ) si returneaza True daca toate parantezele sunt corect balansate, False altfel.

Exemple: "(()())" → True | "(()" → False | ")()" → False

Bonus intensiv C++: Extinde solutia pentru a verifica paranteze mixte: ( ) [ ] { }.

Vezi rezolvarea

Schita de rezolvare (nu solutia gata scrisa - completeaz-o singur, ai deja algoritmul de trasare din lectie ca model):

  1. Porneste cu o stiva goala.
  2. Parcurge sir caracter cu caracter.
  3. Daca vezi ( -> push pe stiva.
  4. Daca vezi ) -> verifica intai daca stiva e goala (atunci e nepotrivire, returnezi False imediat); altfel pop.
  5. La final, functia e echilibrata doar daca stiva a ramas goala.

Capcane: nu uita cazul )() unde primul caracter e deja o inchidere fara pereche - trebuie verificat stiva goala INAINTE de pop, altfel functia crapa. Cazul (() pare corect pana la capat, dar stiva nu e goala la sfarsit.

Criterii de evaluare: functia trateaza toate cele 3 exemple date corect; verifica explicit stiva goala inainte de pop; foloseste doar operatii O(1) (push/pop), nu cauta in sir cu index.

Bonus C++ (paranteze mixte): nu a fost predat in aceasta lectie. Ideea (fara cod gata): stiva retine caracterul deschis; la o inchidere, verifici ca perechea de pe varf corespunde exact tipului de paranteza inchisa (ca in mapa perechi din lectia 2, care rezolva exact acest caz).

Ce ai invatat astazi

  • Stiva = structura LIFO (Last In, First Out)
  • Operatii: push(x), pop(), top(), is_empty() — toate O(1)
  • Implementare in Python cu lista: append = push, pop(-1) = pop, [-1] = top
  • Clasa Stiva in Python (incapsulare OOP, atribut privat _date)
  • Trasarea pas cu pas a operatiilor pe stiva (format BAC)
  • [Intensiv] Clasa Stiva in C++ cu vector<int> si std::stack din STL

Vrei mai mult?

Provocare: Foloseste clasa Stiva din lectie ca sa construiesti un "istoric Undo" cu capacitate maxima 5. Cand faci al 6-lea push si stiva e deja plina, trebuie sa arunci afara starea cea mai VECHE (cea de la baza), nu cea de la varf. Scrie codul si testeaza cu 7 push-uri consecutive - urmareste ce ramane in stiva dupa fiecare pas.

De ce? Toate operatiile stivei sunt O(1) atata timp cat lucram doar cu varful (indexul -1 in Python). Ce s-ar intampla cu complexitatea push si pop daca ai lucra la celalalt capat, indexul 0?

Deschidere: Fiecare apel de functie dintr-un program (inclusiv recursivitatea) foloseste un stack real, gestionat de sistemul de operare: la fiecare apel se face push cu adresa de intoarcere, la fiecare return se face pop. Cand recursivitatea nu se opreste, stiva se umple si apare eroarea "stack overflow".

Urmatoarea lectie

Continua cu aplicatiile stivei: verificare paranteze, evaluare expresii postfix si legatura cu recursivitatea.

Continua →