Coada (Queue)

Coada (Queue) este un container (la fel ca şi Stiva) bazat pe principiul first-in first-out (FIFO). Adică elementele pot fi adăugate în coadă în orice moment, dar numai cel mai vechi (cel de la bază) element poate fi eliminat în orice moment (se extrage cea mai veche informaţie adăugată). Mai simplu, elementele sunt adăugate în spate şi eliminate din faţă. Intraţi pe http://courses.cs.vt.edu/csonline/DataStructures/Lessons/QueuesImplementationView/applet.html sau http://www.concentric.net/~ttwang/java/QueueDemo.html (aveţi nevoie de Java) pentru a înţelege mai bine. Folosiţi Enqueue pentru a adăuga obiecte şi Dequeue pentru a elimina obiectul din faţă (front). Acum că aveţi o idee despre cozi, să trecem la operaţiile pe care coada le implementează. Coada este o structură de date care suportă următoarele operaţii:

• enqueue(ob): adaugă un obiect la sârşitul cozii (baza).
• dequeue(): elimină obiectul din faţa cozii (cap).
• front(): returnează o referinţă către cap fără a elimina obiectul.
• back(): returnează o referinţă către baza fără a elimina obiectul.
• size(): returnează numărul obiectelor din coadă.
• isEmpty(): returnează true dacă coada este vidă, altfel false.

Deoarece am zis că coada este un container de obiecte, acest lucru înseamnă că ar trebui să pot declara cozi de orice tip: int, char, bool, etc. sau un tip definit de utilizator. Deci voi implementa o clasă generică Coada, cu parametrul generic T.

template<typename T>
class Coada
{
public:
    Coada(); // Constructor
    ~Coada(); // Destructor
    void enqueue(const T& ob); // Adaug un element in coada
    void dequeue(); // Elimin obiectul din fata
    const T& front() const; // Returnez o referinta catre cap
    const T& back() const; // Returnez o referinta catre baza
    int size() const; // Returnez numarul de elemente
    bool isEmpty() const; // Este coada vida?
private:
    struct Element
    {
        T data;
        Element * next;
    };
    Element * cap;
    Element * baza;
    int count; // Numar elementele
};

Observaţi că la unele funcţii apare referinţa constantă. De ce fac asta? De ce nu returnez pur şi simplu un obiect T şi nu o referinţă? Datorită eficienţei. Atunci când returnez o referinţă nu se mai alocă, temporar (deci va fi dealocat; un overhead suplimentar), spaţiu pentru obiectul returnat sau pentru parametrul formal, deoarece pot accesa direct variabila referită. Referinţa este constantă tocmai pentru că nu vreau să modific din greşeală argumentul sau obiectul returnat, plus că nu aş putea transmite valori concrete (de ex: 1, 2, 'c', 4.6, etc.) funcţiei enqueue(), dacă referinţa nu ar fi constantă.

Iniţializarea Cozii

Iniţializarea cozii presupune crearea cozii vide, adică elementele cap şi baza indică NULL (nullptr). Pentru cei care folosiţi compilatoare noi, cum ar fi cel din Visual Studio, folosiţi nullptr în loc de NULL, deoarece NULL este doar un simplu macro, este 0, este un întreg şi nu reprezintă concret o adresă inexistentă. Coada este iniţializată în constructor:

template<typename T> Coada<T>::Coada()
{
    cap = baza = nullptr; // coada vida
    count = 0; // niciun element
}

Coada Vidă

Coada este vidă atunci când cap este NULL, deci algoritmul va fi următorul:

template<typename T> bool Coada<T>::isEmpty() const
{
    return cap == nullptr;
}

Calificatorul const informează compilatorul că respectiva funcţie nu modifcă obiectele stivei, nu le modifica datele membre.

Numărul de elemente dintr-o Coadă

Pur şi simplu returnăm valoarea membrului count.

template<typename T> int Coada<T>::size() const
{
    return count;
}

Adăugarea unui element în Coadă

Algoritmul este simplu. Aloc memorie pentru un obiect de tip Element -> Scriu informaţia în obiect -> Succesorul acestui obiect este baza -> Noul element devine baza. Se incrementează count. Funcţia enqueue() va implementa această operaţie.

template<typename T> void Coada<T>::enqueue(const T& ob)
{
    if(isEmpty()) // Daca coada este vida
    {
        cap = new Element;
        cap->data = ob;
        cap->next = nullptr; // Fiind singurul element, succesorul este NULL
        baza = cap;
        count = 1;
    }
    else
    {
        Element * p = new Element;
        p->data = ob;
        p->next = nullptr; // Devine noul element baza
        baza->next = p; // Fosta baza se leaga de noua baza
        baza = p; // p devine baza
        ++count;  // S-a mai adaugat un element
    }
}

Eliminarea unui element din Coadă

Se poate elimina numai elementul din faţă. Se salvează adresa capului -> Elementul următor devine cap -> Se eliberează memoria fostului cap. Se decrementează count. Funcţia dequeue() va implementa această operaţie.

template<typename T> void Coada<T>::dequeue()
{
    if(isEmpty()) throw "Eroare! Coada Vida!";
    Element * q = cap; // Salvez elementul din cap
    cap = cap->next; // Elementul urmator devine cap
    delete q;
    --count;
}

Obţinerea elementului din capul Cozii

Se returnează o referinţă constantă către cap->data.

template<typename T> const T& Coada<T>::front() const
{
    if(isEmpty()) throw "Eroare! Coada Vida!";
    return cap->data;
}

Obţinerea elementului din baza Cozii

Se returnează o referinţă constantă către baza->data.

template<typename T> const T& Coada<T>::back() const
{
    if(isEmpty()) throw "Eroare! Coada Vida!";
    return baza->data;
}

Eliberarea spaţiului de memorie ocupat de Coadă

Se distruge pe rând fiecare element al cozii. De asta se va ocupa destructorul clasei.

template<typename T> Coada<T>::~Coada()
{
    while(cap != nullptr)
    {
        Element * q = cap;
        cap = cap->next;
        delete q;
    }
}

Dacă aveţi probleme cu nullptr, atunci folosiţi NULL. De asemenea vă recomand să folosiţi Visual Studio.
În continuare vă propun să creaţi un nou fişier Coada.h (header) şi să-l adăugaţi la proiectul vostru, după care în fişierul main (unde aveţi funcţia main) să adăugaţi, la început, directiva: #include "Coada.h". Adăugaţi următorul cod în Coada.h:

template<typename T>
class Coada
{
public:
    Coada() { // Constructor
        cap = baza = nullptr; // coada vida
        count = 0; // niciun element
    }
    ~Coada(); // Destructor
    void enqueue(const T& ob); // Adaug un element in coada
    void dequeue(); // Elimin obiectul din fata
    const T& front() const { // Returnez o referinta catre cap
        if(isEmpty()) throw "Eroare! Coada Vida!";
        return cap->data;
    }
    const T& back() const { // Returnez o referinta catre baza
        if(isEmpty()) throw "Eroare! Coada Vida!";
        return baza->data;
    }
    int size() const { return count; } // Returnez numarul de elemente
    bool isEmpty() const { return cap == nullptr; } // Este coada vida?
private:
    struct Element
    {
        T data;
        Element * next;
    };
    Element * cap;
    Element * baza;
    int count; // Numar elementele
};

template<typename T> Coada<T>::~Coada()
{
    while(cap != nullptr)
    {
        Element * q = cap;
        cap = cap->next;
        delete q;
    }
}

template<typename T> void Coada<T>::enqueue(const T& ob)
{
    if(isEmpty()) // Daca coada este vida
    {
        cap = new Element;
        cap->data = ob;
        cap->next = nullptr; // Fiind singurul element, succesorul este NULL
        baza = cap;
        count = 1;
    }
    else
    {
        Element * p = new Element;
        p->data = ob;
        p->next = nullptr; // Devine noul element baza
        baza->next = p; // Fosta baza se leaga de noua baza
        baza = p; // p devine baza
        ++count;  // S-a mai adaugat un element
    }
}

template<typename T> void Coada<T>::dequeue()
{
    if(isEmpty()) throw "Eroare! Coada Vida!";
    Element * q = cap; // Salvez elementul din cap
    cap = cap->next; // Elementul urmator devine cap
    delete q;
    --count;
}

PROBLEMĂ: Într-o coadă sunt memorate numere din intervalul \([1, 10]\). Să se elimine numerele pare.
Deoarece numai informaţia din cap poate fi extrasă, pentru a ajunge la un anumit element trebuie eliminate toate elementele până la acel element. În acest caz, pentru a nu pierde informaţia din celelalte elemente (aici, numerele impare), voi descărca elementele impare într-o coadă de rezervă (temp), iar după ce voi scăpa de numerele pare, voi încărca numerele impare din coada de rezervă înapoi în coada iniţială.

#include <iostream>
#include "Coada.h"
using namespace std;

int main()
{
    Coada<int> qu, temp; 

    for(int i = 1; i <= 10; i++) // Adaug 10 numere [1, 10]
        qu.enqueue(i);

    while(!qu.isEmpty()) // Cat timp coada nu este vida
    {
        if(qu.front() % 2 == 0)
            qu.dequeue(); // Daca este par, il elimin
        else
        {
            temp.enqueue(qu.front()); // Salvez numarul impar
            qu.dequeue();
        }
    }

    // Incarc numerele impare inapoi in coada qu
    while(!temp.isEmpty())
    {
        qu.enqueue(temp.front());
        temp.dequeue();
    }

    // Afisez rezultatul
    while (!qu.isEmpty())
    {
        cout << qu.front() << ' ';
        qu.dequeue();
    }

    system("PAUSE");
    return 0;
}

Output:

1 3 5 7 9

Trebuie să ştiţi că Standard Template Library (STL) implementează o structură de tip coadă în clasa queue, ce se găseşte în headerul queue. Are aceeiaşi membri (isEmpty() este empty(), enqueue() este push(), dequeue() este pop()) ca şi clasa definită de mine, singura diferenţa fiind că operaţiile front(), back() şi pop() pentru o coadă vidă sunt nedefinite, adică nu se generează o excepţie (aşa cum am făcut eu). Deci este responsabilitatea programatorului pentru a se asigura că nu aplică acele operaţii pe o coadă vidă.

#include <queue>
using std::queue; 
queue<float> myQueue;