Ce este coada ?

Coada (sau “queue” in limba engleza) este o structura de date liniara ce lucreaza cu o colectie de date avand doua operatii principale:

• push(int numar) – adauga un numar in coada
• pop() – sterge ultimul element din lista (front() – returneaza valoarea acestui element – deseori functia pop() contine si functia front() integrata)

Modul in care aceasta prelucreaza elementele i-a dat denumirea de FIFO ( First In First Out = primul venit-primul servit)

Cum functioneaza coada?

Avand in vedere ca este o structura de date secventiala, operatiile push si pop se intampla numai la capetele structurii. Acest detaliu permite cozii sa fie implementata ca o lista simpla inlantuita. Nota: Coada este o structura de date cu un numar total de elemente flexibil.

Coada functioneaza pe principiul FIFO, imaginati-va o coada la intrarea intr-un club.

Primul client sosit este cel cu numarul unu, urmat de 2, 3, s.a.m.d. In ce ordine vor intra persoanele in club? In ordinea in care au venit. In momentul cand sosesc clienti noi, acestia se vor aseza in spatele numarului 5.

La ce este folosita coada?

• Servirea cererilor dintr-un sistem cu o resursa disponibila tuturor. De exemplu imprimanta, daca mai multi oameni doresc sa printeze ceva, imprimanta va servii cererile in ordinea in care au venit.
• In call center-uri. Daca suni la Fan Courier, esti plasat intr-o coada pana cand un operator poate sa vorbeasca cu tine.

Cum implementam coada?

Inainte de a implementa coada in C++ vom traduce denumirile functiilor in engleza (pentru a te familiariza cu libraria STL):

• push(int numar) – adauga un element in coada (la final – uneori aceasta functie mai este denumita si push_back() )
• pop() – sterge primul element din coada
• front() – afiseaza primul element din coada
• isEmpty() – verifica daca avem coada goala

Nota: Uneori functia pop() vine integrata cu functia front().

Varianta 1 – Utilizarea unui array (multimi)

#include    <iostream>

using namespace std;

const int LIM = 100;

bool isEmpty(int k) {
    if(k == 0)
        return true;
    return false;
}

void push(int coada[], int &k, int numar) {
    k = k + 1;
    coada[k] = numar;
}

int front(int coada[]) {
    return coada[1];
}

int pop(int coada[], int &k) {
    int rezultat = coada[1];
    for(int i = 1; i < k - 1; i++)
        coada[i] = coada[i + 1];
    k = k - 1;
    return rezultat;
}

int size(int k) {
    return k;
}

int main() {

    int coada[LIM], k = 0;

    push(coada, k, 2);
    push(coada, k, 4);
    push(coada, k, 6);
    push(coada, k, 7);
    push(coada, k, 8);
    cout << pop(coada, k);
    cout << pop(coada, k);
    cout << pop(coada, k);
    return 0;
}

Aceasta varianta incalca una din principiile fundamentale ale cozii. Este restrictionata de un numar maxim de elemente. Coada este o structura de date flexibila.

Varianta 2 – Utilizarea listelor simpu inlantuite

#include    <iostream>

using namespace std;

struct Nod {
    int data;
    Nod* next;
};

Nod* newNode(int data) {
    Nod* nodNou = new Nod();
    nodNou -> data = data;
    nodNou -> next = NULL;
    return nodNou;
}

bool isEmpty(Nod* front) {
    return front == NULL;
}

void push(Nod* &front, Nod* &rear, int data) {
    Nod* nodNou = newNode(data);
    
    if(rear != NULL)
        rear -> next = nodNou;
    
    rear = nodNou;

    if(front == NULL)
        front = nodNou;
}

int pop(Nod* &front) {
    if(isEmpty(front))
        return 0;

    Nod* tmp = front;
    front = front -> next;

    int rezultat = tmp -> data;
    delete tmp;
    return rezultat;
}

int ffront(Nod* front) {
    if(isEmpty(front))
        return 0;
    return front -> data;
}

int main() {
    Nod* front = NULL;
    Nod* rear = NULL;

    push(front, rear, 2);
    push(front, rear, 4);
    push(front, rear, 6);
    push(front, rear, 7);
    push(front, rear, 8);
    cout << pop(front);
    cout << pop(front);
    cout << pop(front);
    return 0;
}

Probleme ce utilizeaza cozile

Pentru a va familiariza cu cozile, puteti sa rezolvati problemele:

• BFS – Parcurgere in latime