Informatică Programare
Structuri de date coada si stiva exercitii
Structurile de date coadă și stivă sunt colecții de elemente cu reguli specifice de acces: coada folosește principiul FIFO (primul intrat, primul ieșit), iar stiva folosește LIFO (ultimul intrat, primul ieșit). Acestea sunt fundamentale în algoritmi și programare, utilizate în scenarii precum gestionarea comenzilor sau evaluarea expresiilor. De exemplu, o coadă poate modela o linie de așteptare, iar o stivă poate gestiona apelurile de funcții.
Operații de bază pentru coadă și stivă
- Pentru coadă (FIFO) Enqueue (adaugă) la sfârșit și dequeue (elimină) de la început; poți verifica dacă este goală sau plină.
- Pentru stivă (LIFO) Push (adaugă) în vârf și pop (elimină) din vârf; poți accesa elementul din vârf fără a-l elimina cu top.
- Exemplu numeric pentru coadă Dacă adaugi elementele 5, 3, 7 în ordine, la eliminare vei obține 5, apoi 3, apoi 7.
- Exemplu numeric pentru stivă Dacă adaugi elementele 5, 3, 7 în ordine, la eliminare vei obține 7, apoi 3, apoi 5.
Exercițiu rezolvat: Verificarea parantezelor cu o stivă
- 1 Pasul 1: Inițializarea stivei Folosește o stivă de caractere pentru a stoca parantezele deschise întâlnite într-o expresie.
- 2 Pasul 2: Parcurgerea expresiei Citește fiecare caracter din șirul "(a+b)*(c-d)"; la '(' push, la ')' pop dacă stiva nu e goală.
- 3 Pasul 3: Verificarea corectitudinii Dacă la sfârșit stiva este goală, expresia are paranteze corect închise; altfel, există o eroare.
- 4 Pasul 4: Exemplu numeric Pentru "(())", push pentru primele două '(', pop pentru ')', iar la sfârșit stiva e goală, deci corect.
- 5 Pasul 5: Implementare în C++ Folosește <stack> din STL: stack<char> stiva; stiva.push('('); stiva.pop();
Încearcă să implementezi manual o coadă sau stivă folosind array-uri înainte de a utiliza containerele STL.