Pe scurt
Structurile de date liniare sunt colecții ordonate de elemente, în care fiecare element (exceptând primul și ultimul) are un predecesor și un succesor. Cele mai frecvente structuri liniare sunt vectorul, lista simplu înlănțuită, stiva și coada, fiecare având proprietăți specifice de acces și operare. În contextul Bacalaureatului, elevii trebuie să cunoască implementarea manuală cu vectori și utilizarea STL pentru aceste structuri.
Definiție și importanță
Structurile de date liniare sunt colecții ordonate de elemente, în care fiecare element (exceptând primul și ultimul) are un predecesor și un succesor. Ele sunt fundamentale în programare, deoarece modelează multe situații reale: o listă de cumpărături, o coadă la un ghișeu, o stivă de farfurii.
În informatică, cele mai frecvente structuri liniare sunt
- Vectorul (array)
- Lista simplu înlănțuită
- Stiva (stack)
- Coada (queue)
Vectorul (array)
Vectorul este o structură statică, cu dimensiune fixă, în care elementele sunt stocate în locații de memorie consecutive.
Proprietăți
- Accesul la un element se face în O(1) prin index
- Inserarea sau ștergerea la mijloc necesită deplasarea elementelor (O(n))
- În context Bac, vectorii se declară static (ex. int v[100];) și se parcurg cu for
Lista simplu înlănțuită
Lista simplu înlănțuită este o structură dinamică, formată din noduri care conțin o valoare și un pointer către următorul nod.
Proprietăți
- Inserarea/ștergerea este eficientă (O(1) după localizare)
- Accesul secvențial este O(n)
- În C++ se implementează cu clase sau cu pointeri
Exemplu de operații
- Inserarea unei note noi la început: nod nou, new_node->next = head; head = new_node
- Ștergerea unei note: găsim nodul anterior, legăm anterior->next = nod->next; delete nod
- Parcurgerea: while(head != NULL) { cout << head->nota; head = head->next; }
În Bac, se cere adesea să se scrie funcții pentru inserare, ștergere, căutare.
Stiva (stack)
Stiva (LIFO – Last In, First Out) permite operații doar la un capăt:
- push (adăugare)
- pop (eliminare)
Aplicații
- Evaluarea expresiilor
- Backtracking
- Simularea apelurilor recursive
În C++, clasa stack din STL oferă implementare rapidă.
Exemplu: Stiva pentru verificarea parantezelor
Fie expresia „( [ ( ) ] )”. Algoritmul:
- Parcurgem șirul
- Dacă găsim o paranteză deschisă („(” sau „[” sau „{”) o adăugăm în stivă
- Dacă găsim o paranteză închisă, verificăm vârful stivei: dacă se potrivesc („()”, „[]”, „{}”), eliminăm vârful; altfel, expresia este invalidă
- La final, stiva trebuie să fie goală
Cod C++ (secvență)
``
stack<char> s;
for(char c : expr) {
if(c=='(' || c=='[' || c=='{') s.push(c);
else if(!s.empty() && ((c==')' && s.top()=='(') || (c==']' && s.top()=='[') || (c=='}' && s.top()=='{'))) s.pop();
else return false;
}
return s.empty();
`
Complexitate: O(n)
Coada (queue)
Coada (FIFO – First In, First Out) operează la două capete
- enqueue (adaugă la sfârșit)
- dequeue (elimină de la început)
Aplicații
- Algoritmi BFS
- Gestionarea resurselor
Pentru Bac, elevii trebuie să cunoască implementarea manuală cu vectori (pentru stivă/coadă) folosind un indice de top, respectiv două indici (front, rear).
Exemplu: Coada pentru simularea unui sistem de printare
Avem task-uri cu timpi de procesare. Se adaugă task-uri la coadă (enqueue) și se procesează în ordinea sosirii.
Implementare simplă cu vector
`
int coada[100], front=0, rear=-1;
void enqueue(int x) {
rear++;
coada[rear]=x;
}
int dequeue() {
int val=coada[front];
front++;
return val;
}
``
Parcurgem task-urile și calculăm timpul total. Exemplu: task-uri [2,5,1] -> se procesează 2, apoi 5, apoi 1; total=8.
Concepte cheie
- Structură de date liniară – elemente ordonate, fiecare element are un predecesor și un succesor
- Vector (array) – acces direct O(1), inserare/ștergere O(n), dimensiune statică
- Listă simplu înlănțuită – inserare/ștergere O(1) după localizare, acces secvențial O(n), memorie dinamică
- Stivă (stack) – LIFO, operații push/pop, top, utilizată în backtracking, evaluare expresii
- Coadă (queue) – FIFO, operații enqueue/dequeue, utilizată în BFS, gestionare resurse
- Implementare manuală cu vectori (top, front/rear) și utilizarea STL (stack, queue) în C++
- Aplicații tipice Bac – verificare paranteze, sortare stivă, simulare coadă, parcurgeri
Verifică-te!
- Care este diferența principală între modul de operare al unei stive și al unei cozi?
- Ce complexitate are accesul la un element într-un vector, respectiv într-o listă simplu înlănțuită?
- În algoritmul de verificare a parantezelor cu ajutorul unei stive, ce condiție trebuie îndeplinită la finalul parcurgerii șirului pentru ca expresia să fie validă?