Structuri de date liniare (vectori, liste, stive, cozi)

Structurile de date liniare sunt fundamentale în informatică, organizând elementele într-o succesiune ordonată, fiecare element având unul sau doi vecini. În acestă lecție pentru liceu (clasele 9-12), vom analiza patru tipuri principale: vectori, liste (simple și dublu înlănțuite), stive și cozi.

Vectorul (array) este cea mai simplă structură, cu elemente stocate în zone consecutive de memorie, accesibile direct prin index. Este rapid la citire/scriere O(1), dar inserarea și ștergerea sunt lente (O(n)). Se utilizează când dimensiunea este cunoscută fix sau se permite realocare.

Lista înlănțuită constă din noduri, fiecare conținând o valoare și un pointer către următorul nod (listă simplu înlănțuită) sau și către precedentul (dublu înlănțuită). Inserarea/ștergerea la început sau la final este O(1), dar căutarea și accesul prin index sunt O(n). Este utilă când se fac multe modificări dinamice.

Stiva (stack) respectă principiul LIFO (Last In, First Out). Operațiile principale sunt push (adaugă în vârf), pop (elimină din vârf) și top (citește vârful). Se implementează frecvent cu vector sau listă înlănțuită. Aplicații: evaluarea expresiilor, funcții recursive, backtracking.

Coada (queue) respectă principiul FIFO (First In, First Out). Operațiile sunt enqueue (adaugă la sfârșit), dequeue (elimină de la început) și front (citește primul element). Se implementează circular (cu vector) sau cu liste. Aplicații: gestionarea resurselor, parcurgerea în lățime (BFS), buffer-e.

La Bacalaureat, elevii trebuie să știe să implementeze aceste structuri în C/C++ (sau pseudocod), să analizeze complexitatea operațiilor și să aleagă structura potrivită în funcție de cerințe. Exercițiile tipice includ simularea procesării unei secvențe, evaluarea unei expresii postfixate sau inversarea unei liste.

Teorie avansată: diferența dintre stivă și coadă la nivel de memorie, utilizarea stivei în apelurile recursive (stack frame), optimizarea cozii circulare pentru a evita realocările, implementarea listelor generice (template) și avantajele listelor dublu înlănțuite față de cele simple.

Exemple

• Exemplul 1 (Bacalaureat – stivă): Să se evalueze expresia postfixată „5 3 + 8 *” folosind o stivă. Rezolvare: Inițial stiva e goală. Citim 5 → push(5). Citim 3 → push(3). Citim + → pop(3), pop(5), calculez 5+3=8, push(8). Citim 8 → push(8). Citim * → pop(8), pop(8), calculez 8*8=64, push(64). Rezultat final: 64. Explicație: se parcurge expresia, operand se adaugă în stivă, operator se aplică ultimelor două elemente.
• Exemplul 2 (Bacalaureat – coadă): Se dă o coadă inițială [1,2,3]. Se efectuează operațiile: enqueue(4), dequeue(), enqueue(5), dequeue(). Care este starea finală? Rezolvare: Inițial front=1, rear=3. enqueue(4) → coada [1,2,3,4]. dequeue() → elimină 1, rămâne [2,3,4]. enqueue(5) → [2,3,4,5]. dequeue() → elimină 2, rămâne [3,4,5]. Răspuns final: [3,4,5]. Explicație: FIFO – primul intrat, primul ieșit.
• Exemplul 3 (Bacalaureat – listă înlănțuită): Se dă o listă simplu înlănțuită cu nodurile: 10 → 20 → 30. Să se insereze valoarea 15 după nodul cu valoarea 10. Rezolvare: Se creează un nod nou cu valoarea 15. Pointerul nodului nou se leagă la următorul nod (care conține 20). Pointerul nodului 10 se leagă la nodul nou. Rezultă: 10 → 15 → 20 → 30. Explicație: inserarea într-o listă simplă necesită actualizarea a două legături.

Concepte cheie: Structură liniară de date, LIFO vs FIFO, Complexitatea operațiilor (O(1), O(n)), Implementare cu vectori și liste înlănțuite, Stivă și coadă în evaluarea expresiilor, Parcurgerea și manipularea listelor înlănțuite