Coada (Queue)

O coadă este o structură de date care funcționează pe principiul FIFO - First In, First Out (primul intrat, primul ieșit).

Imaginează-ți o coadă la magazin: cine vine primul e servit primul. Elementele noi se adaugă la spate și se scot de la față.

Operații fundamentale

Operație	Ce face	Complexitate
`push(x)`	Adaugă elementul `x` la sfârșitul cozii	O(1)
`pop()`	Scoate elementul de la începutul cozii	O(1)
`front()`	Returnează elementul din față fără a-l scoate	O(1)
`empty()`	Verifică dacă coada e goală	O(1)

Exemplu vizual

push(3)    push(7)    push(2)    pop()      push(5)

[3]        [3 7]      [3 7 2]    [7 2]      [7 2 5]
 ↑          ↑          ↑          ↑           ↑
front      front      front      front       front

La pop(), se scoate 3 (primul intrat). Rămâne 7 în față.

Implementare pe vector

int coada[100001];
int st = 1, dr = 0;  // st = primul element, dr = ultimul

void push(int x) {
    dr++;
    coada[dr] = x;
}

void pop() {
    if (st <= dr)
        st++;
}

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

bool empty() {
    return st > dr;
}

int size() {
    return dr - st + 1;
}

st indică primul element, dr ultimul. Coada e goală când st > dr.

Observație: la această implementare, pozițiile eliberate de pop() nu se reutilizează. Pentru coada circulară (reutilizare) avem nevoie de %, dar pentru concursuri, varianta simplă e suficientă dacă dimensionăm vectorul corect.

Stivă vs Coadă

Stivă (LIFO):          Coadă (FIFO):

  push → [vârf]          [față] → pop
  pop  ← [vârf]          [spate] ← push

Adaugă și scoate        Adaugă la spate,
din același capăt        scoate din față

	Stivă	Coadă
Principiu	LIFO	FIFO
Adaugă	în vârf	la spate
Scoate	din vârf	din față
Analogie	teanc de farfurii	coadă la magazin
Folosită la	DFS, paranteze, expresii	BFS, Lee, procesare secvențială

Problema clasică: BFS revizitat

Am folosit deja coada la algoritmul lui Lee și Flood Fill. Acum înțelegem de ce: BFS explorează nodurile nivel cu nivel - exact comportamentul FIFO al cozii.

// BFS pe matrice - coada gestionează ordinea explorării
int qx[10001], qy[10001];
int st = 0, dr = -1;

// Push start
dr++; qx[dr] = sx; qy[dr] = sy;

while (st <= dr) {
    int x = qx[st]; int y = qy[st]; st++; // pop

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (valid(nx, ny)) {
            dr++; qx[dr] = nx; qy[dr] = ny; // push
        }
    }
}

Problema: primul element care nu se mai repetă

Primim un flux de numere. După fiecare număr, afișăm primul element care apare o singură dată (de la stânga la dreapta). Dacă nu există, afișăm -1.

Flux: 1 2 1 3 2 3 4
Răspuns după fiecare: 1 1 2 2 -1 -1 4

Ideea

Menținem o coadă cu candidații. Un vector de frecvență ne spune câte apariții are fiecare valoare. Scoatem din coada din față tot ce are frecvența > 1.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int coada[100001];
int st, dr;
int fr[100001];
int n;

int main()
{
    fin >> n;
    st = 1; dr = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        fr[x]++;

        // Adăugăm în coadă
        dr++;
        coada[dr] = x;

        // Scoatem din față elementele cu frecvență > 1
        while (st <= dr && fr[coada[st]] > 1)
            st++;

        if (st > dr)
            fout << -1 << " ";
        else
            fout << coada[st] << " ";
    }

    return 0;
}

date.in:

7
1 2 1 3 2 3 4

date.out:

1 1 2 2 -1 -1 4

Problema: simulare coadă de așteptare

n persoane cu timp de servire. Câte persoane așteaptă mai mult de T secunde?

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int timpServire[10001];
int n, T;

int main()
{
    fin >> n >> T;
    for (int i = 1; i <= n; i++)
        fin >> timpServire[i];

    int timpTotal = 0;
    int cnt = 0;

    for (int i = 1; i <= n; i++) {
        if (timpTotal > T)
            cnt++;
        timpTotal = timpTotal + timpServire[i];
    }

    fout << cnt;

    return 0;
}

Greșeli frecvente

1. Pop pe coadă goală

st++; // dacă st > dr, coada e goală - nu mai avem ce scoate

Verifică if (st <= dr) înainte.

2. Dimensiunea cozii greșit calculată

int size = dr; // GREȘIT - nu ține cont de st
int size = dr - st + 1; // CORECT

3. Confuzia stivă / coadă

Stiva: adaugă și scoate din același capăt (vârf)
Coada: adaugă la un capăt (spate), scoate din celălalt (față)

Ce să reții

Coada funcționează FIFO: primul intrat, primul ieșit.
Operații O(1): push (la spate), pop (din față), front, empty.
Implementare pe vector cu doi indici: st (față) și dr (spate).
Folosită la: BFS, Lee, procesare secvențială, simulări.
Stiva = LIFO (teanc), Coada = FIFO (rând).

Probleme