|

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ă?

  1. 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.
  2. 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ă.
  3. 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

AvantajeDezavantaje
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

  1. Structura nodului pentru coadă:

struct Nod {

    int valoare;  // Informația stocată

    Nod* urmator; // Pointer către următorul nod

};

  1. 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ă

  1. 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;

    }

}

  1. 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;

}

  1. 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;

}

  1. 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

  1. Planificarea proceselor:
    Cozile sunt utilizate pentru gestionarea proceselor în ordine de sosire.
  2. Aplicații grafice:
    Cozile sunt utilizate pentru parcurgerea pe niveluri (Breadth-First Search – BFS).
  3. Aplicații în rețele:
    Gestionarea pachetelor de date în comunicațiile de rețea.

6. Activități practice pentru elevi

  1. Implementați o funcție care verifică dacă două cozi sunt identice.
  2. Scrieți un program care inversează elementele unei cozi utilizând o stivă.
  3. Realizați o funcție care simulează un sistem de coadă de așteptare pentru un ATM.

7. Scheme logice

  1. Enqueue:
    • Creează nod -> Conectează nodul la sfârșitul cozii -> Actualizează rear.
  2. 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.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *