Structuri de Date Liniare Implementate Dinamic – Stiva 10
1. Obiectivele lecției:
- Să înțeleagă conceptul de stivă și utilizările sale.
- Să învețe cum să implementeze o stivă utilizând alocarea dinamică a memoriei.
- Să implementeze operații comune pe stive: push, pop, peek și isEmpty.
2. Ce este o stivă?
- Definiție:
O stivă este o structură de date liniară care urmează principiul LIFO (Last In, First Out), ceea ce înseamnă că ultimul element introdus este primul care se scoate. - Operații comune:
- Push: Adăugarea unui element în stivă.
- Pop: Eliminarea elementului de la vârful stivei.
- Peek: Accesarea elementului de la vârful stivei fără a-l elimina.
- isEmpty: Verificarea dacă stiva este goală.
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Structură simplă și ușor de implementat. | Accesibilitate limitată (doar vârful stivei). |
| Eficientă pentru gestionarea problemelor LIFO. | Necesită mai multe operații pentru acces aleator. |
| Utilă în aplicații precum recursivitatea sau backtracking. |
4. Implementarea unei stive folosind liste simplu înlănțuite
Structura unui nod
- Structura nodului pentru stivă:
struct Nod {
int valoare; // Informația stocată
Nod* urmator; // Pointer către următorul nod
};
- Pointerul către vârful stivei:
Nod* top = nullptr;
1. Crearea unui nod
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
return nod;
}
2. Operații comune pe stivă
- Push (Adăugarea unui element):
void push(Nod*& top, int valoare) {
Nod* nod = creeazaNod(valoare);
nod->urmator = top;
top = nod;
}
- Pop (Eliminarea elementului de la vârf):
void pop(Nod*& top) {
if (top == nullptr) {
cout << „Stiva este goală. Nu se poate elimina elementul.” << endl;
return;
}
Nod* temp = top;
top = top->urmator;
delete temp;
}
- Peek (Accesarea elementului de la vârf):
int peek(Nod* top) {
if (top == nullptr) {
cout << „Stiva este goală.” << endl;
return -1; // Valoare simbolică pentru eroare
}
return top->valoare;
}
- isEmpty (Verificarea dacă stiva este goală):
bool isEmpty(Nod* top) {
return top == nullptr;
}
3. Parcurgerea stivei
void parcurgeStiva(Nod* top) {
if (top == nullptr) {
cout << „Stiva este goală.” << endl;
return;
}
Nod* temp = top;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
4. Exemplu complet
#include <iostream>
using namespace std;
struct Nod {
int valoare;
Nod* urmator;
};
Nod* creeazaNod(int valoare) {
Nod* nod = new Nod();
nod->valoare = valoare;
nod->urmator = nullptr;
return nod;
}
void push(Nod*& top, int valoare) {
Nod* nod = creeazaNod(valoare);
nod->urmator = top;
top = nod;
}
void pop(Nod*& top) {
if (top == nullptr) {
cout << „Stiva este goală. Nu se poate elimina elementul.” << endl;
return;
}
Nod* temp = top;
top = top->urmator;
delete temp;
}
int peek(Nod* top) {
if (top == nullptr) {
cout << „Stiva este goală.” << endl;
return -1; // Valoare simbolică pentru eroare
}
return top->valoare;
}
bool isEmpty(Nod* top) {
return top == nullptr;
}
void parcurgeStiva(Nod* top) {
if (top == nullptr) {
cout << „Stiva este goală.” << endl;
return;
}
Nod* temp = top;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
int main() {
Nod* top = nullptr;
push(top, 10);
push(top, 20);
push(top, 30);
cout << „Stiva după adăugări: „;
parcurgeStiva(top);
cout << „Elementul de la vârf: ” << peek(top) << endl;
pop(top);
cout << „Stiva după eliminarea elementului de la vârf: „;
parcurgeStiva(top);
cout << „Stiva este goală? ” << (isEmpty(top) ? „Da” : „Nu”) << endl;
return 0;
}
5. Utilizări practice ale stivei
- Evarea expresiilor aritmetice:
Utilizată în evarea expresiilor postfixate sau conversia expresiilor infixate. - Controlul recursivității:
Stiva este utilizată intern pentru a gestiona apelurile recursive. - Operații de backtracking:
Găsirea soluțiilor prin explorarea căilor posibile și revenirea (ex.: labirinturi). - Parantezare corectă:
Verificarea dacă o expresie conține paranteze deschise și închise în mod corect.
6. Activități practice pentru elevi
- Implementați o funcție care verifică dacă o expresie aritmetică are paranteze corecte utilizând o stivă.
- Realizați o funcție care calculează factorialul unui număr utilizând o stivă în loc de recursivitate.
- Implementați un algoritm care convertește o expresie infixată într-o expresie postfixată utilizând o stivă.
7. Scheme logice
- Push:
- Creează un nod -> Conectează nodul la vârful stivei -> Actualizează top.
- Pop:
- Verifică dacă stiva este goală -> Elimină nodul de la vârf -> Actualizează top.
- Peek:
- Returnează valoarea din nodul de la vârf fără a-l elimina.
8. Concluzie
- Stiva este o structură de date esențială în informatică, cu multiple aplicații practice.
- Implementarea sa folosind alocarea dinamică oferă flexibilitate în gestionarea datelor.
- Practica ajută la înțelegerea conceptelor și la utilizarea eficientă a acestei structuri.