Coada — primul intrat, primul ieșit

De ce contează?

Stai la coadă la magazin: cine ajunge primul e servit primul, iar noii veniți se așază la spate. Nimeni nu sare în față. Exact așa funcționează structura de date numită coadă.

Ce este o coadă?

O coadă (queue) este o structură cu două capete: adaugi la spate și scoți din față. Respectă FIFO — First In, First Out: primul intrat e primul ieșit.

Operațiile, toate O(1):

push — adaugă la spate;
pop — scoate din față;
front — citește elementul din față (următorul care iese);
back — citește ultimul adăugat.

coada	3	7	2	9
	fata			spate

Scoți din față (3), adaugi la spate (după 9). Ordinea se păstrează.

Cum funcționează, pas cu pas

Coadă goală, executăm: push 3, push 7, push 2, pop, push 9.

push 3 → [3]
push 7 → [3, 7]
push 2 → [3, 7, 2]
pop → scoate 3 (din față) → [7, 2]
push 9 → [7, 2, 9]

Observația-cheie

Diferența-cheie față de stivă: la stivă scoți ce ai pus ultima (LIFO), la coadă scoți ce ai pus prima (FIFO). Aceeași secvență de operații dă rezultate diferite.

Coada din STL

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(3);
    q.push(7);
    q.push(2);
    cout << q.front() << "\n";  // 3 (urmatorul iesit)
    cout << q.back()  << "\n";  // 2 (ultimul adaugat)
    q.pop();                    // scoate 3
    cout << q.front() << "\n";  // 7
    cout << q.size()  << "\n";  // 2
    return 0;
}

Aplicație: BFS, schema de bază

Coada este motorul parcurgerii în lățime (BFS). Pui startul în coadă, apoi repetat scoți un element și adaugi vecinii nevizitați:

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    bool vizitat[100] = {false};

    q.push(0);              // pornim din nodul 0
    vizitat[0] = true;
    while (!q.empty()) {
        int nod = q.front();
        q.pop();            // procesam nodul curent
        cout << nod << " ";
        // for fiecare vecin v al lui nod:
        //     if (!vizitat[v]) { vizitat[v] = true; q.push(v); }
    }
    return 0;
}

De ce FIFO dă „lățime”? Pentru că nodurile descoperite primele (cele apropiate de start) sunt și procesate primele — explorarea avansează nivel cu nivel.

Complexitate

Operație	Timp	Spațiu
push / pop / front / back / empty	O(1)	—
BFS pe graf cu V noduri, E muchii	O(V + E)	O(V)

Greșeli frecvente

Greșeli frecvente de concurs:

front() / pop() pe coadă goală: comportament nedefinit. Testează !q.empty().
Confuzia front cu back: front iese, back tocmai a intrat.
Marcarea vizitării prea târziu: în BFS marchează vizitat[v]=true când îl pui în coadă, nu când îl scoți — altfel adaugi același nod de mai multe ori.
Stivă în loc de coadă: dacă în BFS folosești o stivă, obții o parcurgere „în adâncime”, nu în lățime.

Vizualizare

Urmărește cum intră elemente la spate și ies din față:

Indiciu

Compară mental cu stiva: aici ce intră primul iese primul. Folosește ← / → pentru a urmări ordinea.

Recapitulare

Coada e FIFO: adaugi la spate, scoți din față, toate O(1).
front() e următorul scos, back() e ultimul adăugat.
Structura naturală pentru BFS — explorare nivel cu nivel.