Structurile de date liniare sunt fundamentele organizării informației în programare, unde elementele sunt aranjate secvențial, fiecare având un predecesor și un succesor (cu excepția primului și ultimului). În contextul liceului și al examenului de Bacalaureat, aceste structuri sunt esențiale pentru rezolvarea problemelor de algoritmică.
- Vectorii (tablouri unidimensionale) sunt cele mai simple structuri liniare, cu acces direct prin indice (O(1)). În C/C++ și Pseudocod, vectorii au dimensiune fixă declarată static. Operațiile de bază includ citirea, scrierea, parcurgerea (cu for/while), căutarea secvențială (O(n)) sau binară (pe vectori sortați, O(log n)), și sortarea (bubble sort, selection sort, sau algoritmi mai eficienți precum quicksort, dar la Bac se cer algoritmi simpli).
- Listele liniare sunt structuri dinamice (implementate cu pointeri în C/C++ sau cu referințe în pseudocod). Spre deosebire de vectori, listele permit inserarea și ștergerea eficientă (O(1) la început/sfârșit dacă avem pointeri) dar accesul este secvențial (O(n)). La BAC, listele sunt tratate conceptual, cu operații de adăugare (la început, sfârșit, după un element), ștergere, căutare și traversare. Se studiază liste simplu și dublu înlănțuite; structura tip nod conține o informație utilă și unul sau doi pointeri către vecini.
- Stivele (stack) sunt structuri LIFO (Last In, First Out). Se implementează static (cu vector și un indice vârf) sau dinamic (cu liste). Operațiile principale: push (adaugă în vârf), pop (elimină din vârf), top (accesează vârful fără a-l șterge), isEmpty (verifică dacă e goală). Aplicații tipice: evaluarea expresiilor postfixate, parcurgerea în adâncime (DFS), gestionarea apelurilor recursive, verificarea parantezelor. La BAC apare frecvent la probleme de simulare și backtracking.
- Cozile (queue) sunt structuri FIFO (First In, First Out). Implementare statică (cu vector circular pentru eficiență) sau dinamică (cu listă). Operații: enqueue (adaugă la sfârșit), dequeue (elimină din față), front (accesează primul element), rear (accesează ultimul), isEmpty. Aplicații: parcurgerea în lățime (BFS), gestionarea taskurilor, simulări cu cozi de așteptare. La Bac, se cer implementări simple, fără erori de depășire.
În rezolvarea problemelor de Bac, elevii trebuie să recunoască tipul de structură potrivit: vector pentru acces aleator, listă pentru inserări/ștergeri frecvente, stivă pentru procesare în ordine inversă, coadă pentru procesare în ordinea sosirii. Complexitățile temporale și spațiale sunt evaluate. Se recomandă utilizarea pseudocodului în exerciții, iar în C/C++ se implementează cu structuri și funcții dedicate.
Exemple
- Exemplul 1 (Vectori - căutarea binară): Se citește un vector V cu n elemente sortate crescător și o valoare x. Să se determine dacă x apare în V, iar dacă da, să se afișeze poziția. Rezolvare: Se folosește algoritmul de căutare binară (divide et impera). Se inițializează st=1, dr=n. Cât timp st<=dr, se calculează mij=(st+dr)/2. Dacă V[mij]==x, se afișează mij și se oprește. Dacă V[mij]<x, st=mij+1; altfel dr=mij-1. Dacă nu se găsește, se afișează mesajul 'Nu exista'. Complexitate O(log n).
- Exemplul 2 (Stivă - verificare paranteze): Se dă un șir de caractere ce conține paranteze rotunde, pătrate și acolade. Să se verifice dacă șirul este corect (fiecare paranteză deschisă se închide corespunzător cu aceeași paranteză închisă, la momentul potrivit). Rezolvare: Se parcurge șirul caracter cu caracter. Dacă întâlnim o paranteză deschisă ( ori [ ori {, se face push în stivă. Dacă întâlnim o paranteză închisă ), se verifică dacă stiva nu este goală și vârful este (; atunci se face pop. Similar pentru ] cu [ și } cu {. Dacă nu corespunde, sau la final stiva nu este goală, șirul este incorect. Complexitate O(n).
- Exemplul 3 (Coadă - simulare coadă de așteptare): Se citește o secvență de comenzi: 'E x' (enqueue, adaugă x la coadă), 'D' (dequeue, elimină primul element), 'P' (printează primul element). Să se proceseze comenzile și să se afișeze rezultatele. Rezolvare: Se implementează o coadă statică circulară cu un vector de dimensiune maximă (de ex. 1000) și doi indici: front și rear. La 'E x', verificăm dacă coada nu este plină (rear+1 == front la mod circular), apoi rear = (rear+1)%N, și inserăm. La 'D', verificăm dacă coada nu este goală (front != rear), apoi front = (front+1)%N. La 'P', afișăm elementul din front. Se simulează toate comenzile.
Concepte cheie: Acces direct vs. acces secvențial (vector vs. listă), Principiul LIFO (Last In, First Out) - stiva, Principiul FIFO (First In, First Out) - coada, Implementarea statică și dinamică a stivelor și cozilor, Operații fundamentale: push, pop, enqueue, dequeue, front, rear, Complexități temporale O(1) pentru inserare/ștergere la capete (stivă, coadă, listă), Aplicații curente: evaluare expresii, parcurgeri DFS/BFS, simulări