Ce este coada/queue si cum functioneaza? Tutorial clasa a 10-a

Observație

Imediat putem observa următorul lucru: primul element adăugat este şi primul care urmează să fie eliminat, deoarece ordinea de adăugare este identică cu cea de eliminare – astfel coada este o structură de tip FIFO – The First In is the First Out. Stiva, pe de altă parte, este LIFO, adică Last In First Out.

Implementarea statică

Implementarea statică se bazează pe un simplu vector, coada[] şi doi indici, st şi dr, unde st va reține indicele primului element al vectorului, iar dr va reține indicele ultimului element al vectorului. În următoarea secvența de cod am descris cele mai elementare aspecte de folosirea cozii:

#include <iostream>

using namespace std;

//de declarat la început.//pentru mai multe detalii: https://100din100.netlify.app
//dimensiunea maximă a cozii este de 1000, atenție la memorie!//pentru mai multe detalii: https://100din100.netlify.app
int coada[1000], st = 1, dr = 0; //declararea cozii şi a indicilor//pentru mai multe detalii: https://100din100.netlify.app

int lungime_coada() {
    //returnează lungimea cozii, cu clasica formulă de mate//pentru mai multe detalii: https://100din100.netlify.app
    return dr - st + 1;
}

int este_vida_coada() {
    //returnează 1 dacă coada este vidă,//pentru mai multe detalii: https://100din100.netlify.app
    //sau 0 în caz contrar//pentru mai multe detalii: https://100din100.netlify.app
    if(st <= dr) return 0; //lungimea este mai mare decât 0, aşadar nu este vidă coada.//pentru mai multe detalii: https://100din100.netlify.app
    else return 1; //lungimea este egală cu 0, aşadar coada este vidă.//pentru mai multe detalii: https://100din100.netlify.app
}

void initializare_coada() {
    //facem coada vidă prin setarea lungimii cozii = 0.//pentru mai multe detalii: https://100din100.netlify.app
    //astfel, lungime-coada() va returna 0 - 1 + 1 = 0.//pentru mai multe detalii: https://100din100.netlify.app
    st = 1;
    dr = 0;
}

void push_coada(int element) {
    //vom adăuga element la coadă//pentru mai multe detalii: https://100din100.netlify.app
    dr = dr + 1; //creşte lungimea cozii//pentru mai multe detalii: https://100din100.netlify.app
    coada[dr] = element; //noului element îi setăm valoarea dorită//pentru mai multe detalii: https://100din100.netlify.app
}

void pop_coada() {
    //eliminarea primului element al şirului,//pentru mai multe detalii: https://100din100.netlify.app
    //incrementând st.//pentru mai multe detalii: https://100din100.netlify.app
    st = st + 1;
}

int front_coada() {
    //returnează primul element, adică cel de pe poziția st//pentru mai multe detalii: https://100din100.netlify.app
    return coada[st];
}

int main()
{
    initializare_coada();
    cout<<lungime_coada()<<endl; //afişează 0//pentru mai multe detalii: https://100din100.netlify.app
    cout<<este_vida_coada()<<endl; //afişează 1//pentru mai multe detalii: https://100din100.netlify.app
    push_coada(1);
    push_coada(2);
    push_coada(3);
    cout<<lungime_coada()<<endl; //afişează 3//pentru mai multe detalii: https://100din100.netlify.app
    cout<<este_vida_coada()<<endl; //afişează 0//pentru mai multe detalii: https://100din100.netlify.app
    pop_coada(); //elimină 1//pentru mai multe detalii: https://100din100.netlify.app
    cout<<front_coada()<<endl; //afişează 2//pentru mai multe detalii: https://100din100.netlify.app
    push_coada(4);
    cout<<front_coada()<<endl; //afişează 2//pentru mai multe detalii: https://100din100.netlify.app
    return 0;
}

Avantaje. Operațiile sunt uşor de implementat şi sunt rapide.

Dezavantaje. Dacă se fac multe operații de pop, se risipă multă memorie (mereu s-ar putea economisi st memorie).

Implementarea cozii din STL

Implementarea cozii din STL are deja funcțiile predefinite şi se poate utiliza uşor, însă, poate fi mai greu de înțeles. Coada se află în biblioteca <queue>. Iată cum ar arăta noua coadă (aceleaşi exemple):

#include <iostream>
#include <queue>

using namespace std;

//de declarat la început.//pentru mai multe detalii: https://100din100.netlify.app
queue<int> coada; //declararea cozii. nu este nevoie de indici.//pentru mai multe detalii: https://100din100.netlify.app

int lungime_coada() {
    //returnează lungimea cozii, cu clasica formulă de mate//pentru mai multe detalii: https://100din100.netlify.app
    return coada.size();
}

int este_vida_coada() {
    //returnează 1 dacă coada este vidă,//pentru mai multe detalii: https://100din100.netlify.app
    //sau 0 în caz contrar.//pentru mai multe detalii: https://100din100.netlify.app
    //ne folosim de funcția deja scrisă.//pentru mai multe detalii: https://100din100.netlify.app
    if(coada.empty()) return 1;
    else return 0;
}

void initializare_coada() {
    //eliminăm toate elementele cozii. se poate şi cu swap//pentru mai multe detalii: https://100din100.netlify.app
    while(este_vida_coada() == 0) coada.pop();
}

void push_coada(int element) {
    //vom adăuga element la coadă//pentru mai multe detalii: https://100din100.netlify.app
    coada.push(element);
}

void pop_coada() {
    //eliminarea primului element al şirului.//pentru mai multe detalii: https://100din100.netlify.app
    coada.pop();
}

int front_coada() {
    //returnează primul element//pentru mai multe detalii: https://100din100.netlify.app
    return coada.front();
}

int main()
{
    initializare_coada();
    cout<<lungime_coada()<<endl; //afişează 0//pentru mai multe detalii: https://100din100.netlify.app
    cout<<este_vida_coada()<<endl; //afişează 1//pentru mai multe detalii: https://100din100.netlify.app
    push_coada(1);
    push_coada(2);
    push_coada(3);
    cout<<lungime_coada()<<endl; //afişează 3//pentru mai multe detalii: https://100din100.netlify.app
    cout<<este_vida_coada()<<endl; //afişează 0//pentru mai multe detalii: https://100din100.netlify.app
    pop_coada(); //elimină 1//pentru mai multe detalii: https://100din100.netlify.app
    cout<<front_coada()<<endl; //afişează 2//pentru mai multe detalii: https://100din100.netlify.app
    push_coada(4);
    cout<<front_coada()<<endl; //afişează 2//pentru mai multe detalii: https://100din100.netlify.app
    return 0;
}

Avantaje. Operațiile sunt deja scrise. Lungimea maximă a cozii nu este fixă.

Dezavantaje. Se consumă mai multă memorie pentru fiecare element în parte.