Structura de date de tip coadă

Accesul la elementele unei cozi

Coada este o structură de date liniară la care accesul este îngrădit la cele două capete: un element nou se adaugă numai la un capăt, numit sfârșitul cozii, iar elementul care se scoate este numai cel de la celălalt capăt, numit începutul cozii. Elementele aflate în interior nu pot fi citite, modificate sau șterse direct.

De aici decurge regula după care funcționează: primul element intrat este și primul care iese — prescurtat FIFO, de la first in, first out. Coada modelează situațiile de așteptare la rând, în care ordinea servirii este ordinea sosirii.

Operațiile specifice în reprezentarea secvențială

Elementele se păstrează într-un vector c, iar poziția celor două capete se reține în două variabile: prim, indicele elementului de la începutul cozii, și ultim, indicele celui de la sfârșit. Coada este vidă atunci când prim > ultim.

Se pornește de la coada cu 4 elemente 7, 12, 5, 9, în care 7 este primul sosit:

cu prim = 1 și ultim = 4.

Inserarea unui element

Etapele. Se verifică dacă mai există loc în vector, adică dacă ultim este mai mic decât dimensiunea lui. Se mărește ultim cu 1, iar pe noua poziție se scrie valoarea de inserat. Variabila prim nu se modifică.

Exemplificare — se inserează valoarea 20. ultim devine 5, iar c[5] primește valoarea 20:

Coada este acum 7, 12, 5, 9, 20, cu prim = 1 și ultim = 5.

Ștergerea unui element

Etapele. Se verifică dacă coada nu este vidă, adică dacă prim ≤ ultim. Se reține valoarea aflată pe poziția prim, care este elementul scos, apoi prim se mărește cu 1. Valoarea rămasă în vector pe vechea poziție nu se șterge, dar nu mai face parte din coadă, fiindcă se află înaintea lui prim.

Exemplificare — se șterge un element din coada inițială. Se reține c[1], adică 7, iar prim devine 2:

Coada este acum 12, 5, 9, cu prim = 2 și ultim = 4.

Operațiile specifice în reprezentarea înlănțuită

Fiecare element se păstrează într-un nod alocat dinamic, cu două câmpuri: informația și adresa nodului următor. Se rețin două adrese: prim, adresa nodului de la începutul cozii, și ultim, adresa celui de la sfârșit. Legătura ultimului nod are valoarea NULL, iar coada vidă are prim = NULL.

Aceeași coadă cu 4 elemente arată astfel:

prim → [7 | •] → [12 | •] → [5 | •] → [9 | NULL] ← ultim

Inserarea unui element

Etapele. Se alocă dinamic un nod nou și i se completează câmpul de informație cu valoarea de inserat. Legătura noului nod primește valoarea NULL, fiindcă el devine ultimul. Legătura nodului indicat de ultim primește adresa noului nod, iar apoi ultim primește el însuși această adresă. Dacă coada era vidă, se completează amândouă adresele, prim și ultim, cu adresa noului nod.

Exemplificare — se inserează valoarea 20. Se creează nodul cu informația 20 și legătura NULL; legătura nodului cu informația 9 arată acum spre el, iar ultim primește adresa lui:

prim → [7 | •] → [12 | •] → [5 | •] → [9 | •] → [20 | NULL] ← ultim

Ștergerea unui element

Etapele. Se verifică dacă prim este diferit de NULL. Se reține într-o variabilă auxiliară adresa primului nod și informația din el, care este elementul scos. prim primește adresa nodului următor, citită din legătura primului nod, iar nodul rămas fără legături se eliberează. Dacă după această operație prim a devenit NULL, coada s-a golit, deci și ultim trebuie făcut NULL.

Exemplificare — se șterge un element din coada inițială. Se reține informația 7, prim primește adresa nodului cu informația 12, iar nodul cu 7 se eliberează:

prim → [12 | •] → [5 | •] → [9 | NULL] ← ultim

Problema propusă

Enunț. La o imprimantă de rețea sosesc cereri de tipărire, care se rezolvă în ordinea sosirii. Se citesc de la tastatură un număr natural m (m ≤ 1000) și apoi m comenzi, fiecare de una dintre formele: A x, prin care documentul cu numărul x este trimis la imprimantă, sau T, prin care imprimanta tipărește primul document aflat în așteptare. Se cere să se afișeze, câte unul pe linie, numerele documentelor tipărite, în ordinea în care sunt tipărite; dacă o comandă T sosește când nu mai există documente în așteptare, se afișează mesajul nimic de tiparit.

Exemplu: pentru m = 6 și comenzile A 101, A 102, T, A 103, T, T se afișează, pe linii separate, 101, 102, 103.

Descrierea soluției în limbaj natural. Documentele trimise la imprimantă așteaptă și sunt servite în ordinea sosirii, deci se comportă exact ca o coadă: comanda A este inserarea unui element, iar comanda T este ștergerea. Nicio altă operație nu este cerută — nu se caută un document anume, nu se șterge din mijloc — așa că îngrădirea accesului la cele două capete nu deranjează, iar structura potrivită este coada.

Se folosește reprezentarea secvențială, cu un vector și cei doi indici. Numărul comenzilor fiind cel mult 1000, tot atâtea inserări pot avea loc, deci vectorul se declară cu 1000 de poziții și nu se umple niciodată.

Se citesc comenzile una câte una. Pentru o comandă A se citește și numărul documentului și se inserează în coadă. Pentru o comandă T se verifică întâi dacă coada este vidă: dacă este, se afișează mesajul cerut, altfel se scoate primul element și se afișează.

Implementarea soluției.

#include <iostream>
using namespace std;

const int N = 1001;

int c[N];                 // coada, in reprezentare secventiala
int prim = 1, ultim = 0;  // coada este vida cat timp ultim < prim

void adauga(int x) {
    ultim++;
    c[ultim] = x;
}

int scoate() {
    int x = c[prim];
    prim++;
    return x;
}

bool esteVida() {
    return prim > ultim;
}

int main() {
    int m;
    cin >> m;

    for (int i = 1; i <= m; i++) {
        char comanda[3];
        cin >> comanda;

        if (comanda[0] == 'A') {
            int x;
            cin >> x;
            adauga(x);
        } else {
            if (esteVida())
                cout << "nimic de tiparit" << endl;
            else
                cout << scoate() << endl;
        }
    }

    return 0;
}

Verificarea pe exemplul din enunț.

O a șaptea comandă T ar găsi coada vidă și ar afișa nimic de tiparit.