Pe scurt
Structurile de date liniare (stivă, coadă, listă) organizează datele într-o succesiune logică, fiecare având reguli specifice de acces și operare. Stiva funcționează după principiul LIFO (Last In, First Out), coada după FIFO (First In, First Out), iar lista permite operații flexibile de inserare, ștergere și căutare, putând fi implementată static sau dinamic.
Stiva (Stack) – principiul LIFO
Stiva este o structură de tip LIFO (Last In, First Out), unde ultimul element adăugat este primul scos.
Operații de bază:
- push – adaugă un element în vârf
- pop – elimină elementul din vârf
- top – returnează elementul din vârf fără a-l elimina
- isEmpty – verifică dacă stiva este goală
Implementări:
- Statică – cu un tablou de dimensiune fixă și un indicator de vârf
- Dinamică – cu liste înlănțuite
Exemplu – Stivă statică cu vector:
- Se consideră o stivă implementată cu un vector
v[100] și un indice varf inițial 0
- Operații:
push(10) (v[varf]=10; varf++), push(20), pop() (varf--), top() (v[varf-1])
- După
push(10), push(20): stiva = [10,20]; după pop() rămâne [10]; top() returnează 10
Complexitate: operațiile pop și push sunt O(1)
Coada (Queue) – principiul FIFO
Coada respectă principiul FIFO (First In, First Out): primul element intrat este primul scos.
Operații de bază:
- enqueue – adaugă la sfârșit
- dequeue – elimină din față
- front – accesează primul element
- isEmpty – verifică dacă coada este goală
Implementări uzuale:
- Circulară – folosind un tablou și indici de început-sfârșit
- Dinamică – cu liste dublu înlănțuite
Exemplu – Coada circulară:
- Coadă implementată cu un vector de 5 elemente, indici
fata=0, spate=0 (coada goală)
- Operații:
enqueue(3) → v[spate]=3; spate=(spate+1)%5; enqueue(5); dequeue() → x=v[fata]; fata=(fata+1)%5
- Dacă mai adăugăm 7, 8, 9, ajungem la
spate>fata doar prin modulo
- Verificăm coadă plină când
(spate+1)%5 == fata
Lista (List) – colecție ordonată de elemente
Lista reprezintă o colecție ordonată de elemente, cu operații de inserare, ștergere, căutare și acces secvențial sau direct (după index).
Tipuri principale:
- Listă simplu înlănțuită – fiecare nod conține date și un pointer către următorul nod
- Listă dublu înlănțuită – pointeri atât către următorul, cât și către precedentul
Operații esențiale:
- Inserarea la început, la sfârșit sau într-o poziție intermediară
- Ștergerea unui nod cu pointeri adecvați
- Parcurgerea (iterarea)
Exemplu – Listă simplu înlănțuită:
- Definim
struct Node{ int info; Node* next; }
- Inserare la început:
Node* p=new Node; p->info=7; p->next=head; head=p;
- Ștergere element cu valoare 7: se parcurg nodurile cu un pointer anterior și curent; când
curent->info==7, se modifică anterior->next = curent->next și se șterge curent
Complexitate:
- Inserarea la începutul unei liste simplu înlănțuite – O(1)
- Ștergerea unui nod intermediar necesită parcurgerea listei până la predecesor – O(n)
Aplicații avansate
- Stiva – evaluarea expresiilor aritmetice (notație poloneză)
- Coada – parcurgerea în lățime (BFS) în grafuri
- Listele – implementarea tabelelor de dispersie cu înlănțuire
Concepte cheie
- LIFO vs FIFO
- Operații: push, pop, enqueue, dequeue
- Implementare statică (vector) vs dinamică (liste înlănțuite)
- Listă simplu și dublu înlănțuită
- Complexitate O(1) pentru operațiile de bază ale stivei și cozii în implementarea statică
Verifică-te!
- Care este diferența fundamentală între principiul de funcționare al stivei și al cozii?
- Ce complexitate temporală are operația de ștergere a unui nod intermediar dintr-o listă simplu înlănțuită și de ce?
- Cum se verifică dacă o coadă circulară implementată cu vector este plină?