Structuri de Date Liniare Implementate Dinamic – Coada 11
1. Obiectivele lecției:
- Să înțeleagă conceptul de coadă și principiul său de funcționare.
- Să învețe cum să implementeze o coadă utilizând alocarea dinamică a memoriei.
- Să implementeze operații comune pe cozi: enqueue, dequeue, peek, isEmpty.
2. Ce este o coadă?
- Definiție:
O coadă este o structură de date liniară care urmează principiul FIFO (First In, First Out), ceea ce înseamnă că primul element introdus este primul care se scoate. - Operații comune:
- Enqueue: Adăugarea unui element la sfârșitul cozii.
- Dequeue: Eliminarea elementului din fața cozii.
- Peek: Accesarea elementului din fața cozii fără a-l elimina.
- isEmpty: Verificarea dacă coada este goală.
- Aplicații practice:
- Gestionarea cozii de imprimare.
- Planificarea proceselor în sistemele de operare.
- Simulări (ex.: linii de așteptare, sisteme bancare).
3. Avantaje și dezavantaje
Avantaje | Dezavantaje |
Structură simplă și ușor de implementat. | Inserarea și ștergerea sunt limitate la capete. |
Eficientă pentru gestionarea operațiilor FIFO. | Acces aleator nu este posibil. |
Poate fi implementată dinamic. | Necesită gestionarea pointerilor pentru dinamism. |
4. Implementarea unei cozi folosind liste simplu înlănțuite
Structura unui nod
- Structura nodului pentru coadă:
struct Nod {
int valoare; // Informația stocată
Nod* urmator; // Pointer către următorul nod
};
- Pointeri pentru gestionarea cozii:
- Front: Indică primul element al cozii.
- Rear: Indică ultimul element al cozii.
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 coadă
- Enqueue (Adăugarea unui element):
void enqueue(Nod*& front, Nod*& rear, int valoare) {
Nod* nod = creeazaNod(valoare);
if (rear == nullptr) { // Coada este goală
front = rear = nod;
} else {
rear->urmator = nod;
rear = nod;
}
}
- Dequeue (Eliminarea elementului din față):
void dequeue(Nod*& front, Nod*& rear) {
if (front == nullptr) { // Coada este goală
cout << „Coada este goală. Nu se poate elimina elementul.” << endl;
return;
}
Nod* temp = front;
front = front->urmator;
if (front == nullptr) { // Dacă coada devine goală
rear = nullptr;
}
delete temp;
}
- Peek (Accesarea elementului din față):
int peek(Nod* front) {
if (front == nullptr) {
cout << „Coada este goală.” << endl;
return -1; // Valoare simbolică pentru eroare
}
return front->valoare;
}
- isEmpty (Verificarea dacă coada este goală):
bool isEmpty(Nod* front) {
return front == nullptr;
}
3. Parcurgerea cozii
void parcurgeCoada(Nod* front) {
if (front == nullptr) {
cout << „Coada este goală.” << endl;
return;
}
Nod* temp = front;
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 enqueue(Nod*& front, Nod*& rear, int valoare) {
Nod* nod = creeazaNod(valoare);
if (rear == nullptr) { // Coada este goală
front = rear = nod;
} else {
rear->urmator = nod;
rear = nod;
}
}
void dequeue(Nod*& front, Nod*& rear) {
if (front == nullptr) { // Coada este goală
cout << „Coada este goală. Nu se poate elimina elementul.” << endl;
return;
}
Nod* temp = front;
front = front->urmator;
if (front == nullptr) { // Dacă coada devine goală
rear = nullptr;
}
delete temp;
}
int peek(Nod* front) {
if (front == nullptr) {
cout << „Coada este goală.” << endl;
return -1; // Valoare simbolică pentru eroare
}
return front->valoare;
}
bool isEmpty(Nod* front) {
return front == nullptr;
}
void parcurgeCoada(Nod* front) {
if (front == nullptr) {
cout << „Coada este goală.” << endl;
return;
}
Nod* temp = front;
while (temp != nullptr) {
cout << temp->valoare << ” „;
temp = temp->urmator;
}
cout << endl;
}
int main() {
Nod* front = nullptr;
Nod* rear = nullptr;
enqueue(front, rear, 10);
enqueue(front, rear, 20);
enqueue(front, rear, 30);
cout << „Coada după adăugări: „;
parcurgeCoada(front);
cout << „Elementul din fața cozii: ” << peek(front) << endl;
dequeue(front, rear);
cout << „Coada după eliminarea elementului din față: „;
parcurgeCoada(front);
cout << „Coada este goală? ” << (isEmpty(front) ? „Da” : „Nu”) << endl;
return 0;
}
5. Utilizări practice ale cozii
- Planificarea proceselor:
Cozile sunt utilizate pentru gestionarea proceselor în ordine de sosire. - Aplicații grafice:
Cozile sunt utilizate pentru parcurgerea pe niveluri (Breadth-First Search – BFS). - Aplicații în rețele:
Gestionarea pachetelor de date în comunicațiile de rețea.
6. Activități practice pentru elevi
- Implementați o funcție care verifică dacă două cozi sunt identice.
- Scrieți un program care inversează elementele unei cozi utilizând o stivă.
- Realizați o funcție care simulează un sistem de coadă de așteptare pentru un ATM.
7. Scheme logice
- Enqueue:
- Creează nod -> Conectează nodul la sfârșitul cozii -> Actualizează rear.
- Dequeue:
- Verifică dacă coada este goală -> Elimină nodul din față -> Actualizează front și, eventual, rear.
8. Concluzie
- Cozile sunt structuri de date esențiale pentru gestionarea operațiilor FIFO.
- Implementarea lor dinamică oferă flexibilitate în gestionarea dimensiunii.
- Practica ajută la înțelegerea utilizării și implementării eficiente a acestei structuri.