queue — adaptorul FIFO din STL

De ce contează?

Gândește-te la o bandă rulantă de la casa de marcat: produsele intră la un capăt și ies fix în ordinea în care au fost puse. Tu, casierul, nu poți să bagi mâna în mijloc și să iei al treilea produs — vezi doar primul care vine. Cam asta îți oferă std::queue: o interfață deliberat îngustă peste o structură mai bogată.

Ce este un adaptor de container și de ce există

Ai învățat deja conceptul de coadă (FIFO) la structuri liniare. În STL, coada nu e o structură scrisă de la zero, ci un adaptor de container: o folie subțire care se așază peste un container existent și îi expune doar operațiile FIFO.

Implicit, std::queue se sprijină pe un deque (coadă cu două capete), care știe deja să adauge și să scoată eficient la ambele capete. De ce un adaptor și nu o clasă proprie? Pentru că adaptorul nu reinventează nimic, doar ascunde ce nu are sens pentru o coadă: nu există acces cu [], nu există iteratori, nu poți insera la mijloc. Interfața restrânsă garantează disciplina FIFO.

Operațiile expuse, toate O(1):

push(x) — adaugă x la spate;
pop() — scoate elementul din față (nu returnează nimic);
front() — citește elementul din față (următorul scos);
back() — citește ultimul adăugat;
size() — câte elemente sunt;
empty() — true dacă e goală.

Exemplu pas cu pas

Pornim de la o coadă goală și executăm: push 3, push 7, push 2, pop, push 9.

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

queue	7	2	9
	front		back

După secvență: front (iese la pop) este 7, back (ultimul intrat) este 9.

Observă: pop() scoate, dar nu îți dă valoarea. Dacă ai nevoie de ea, citește-o cu front() înainte de a face pop().

Implementare C++

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

int main() {
    queue<int> q;            // adaptor peste deque, implicit

    q.push(3);
    q.push(7);
    q.push(2);
    cout << q.front() << "\n";   // 3  (urmatorul scos)
    cout << q.back()  << "\n";   // 2  (ultimul adaugat)
    cout << q.size()  << "\n";   // 3

    q.pop();                     // scoate 3, nu returneaza nimic
    cout << q.front() << "\n";   // 7

    q.push(9);                   // coada: 7 2 9
    cout << q.back()  << "\n";   // 9

    // golire tipica: cat timp nu e goala, ia din fata
    while (!q.empty()) {
        cout << q.front() << " ";  // 7 2 9
        q.pop();
    }
    cout << "\n";
    cout << q.empty() << "\n";    // 1 (true, coada e goala)
    return 0;
}

Bucla while (!q.empty()) este modelul standard de procesare: citești elementul din față, îl folosești, apoi pop(). Tot acest tipar stă la baza parcurgerii BFS — dar pe aceea o detaliem separat.

Complexitate

Operație	Timp	Spațiu
push / pop	O(1)	—
front / back	O(1)	—
size / empty	O(1)	—
coadă cu n elemente	—	O(n)

Observația-cheie

std::queue și std::stack sunt amândoi adaptori și au interfețe aproape identice ca formă — diferă doar capătul de unde scoți. La stivă citești cu top() și scoți tot de sus (LIFO); la coadă citești cu front() și scoți din față (FIFO). Aceeași secvență de push-uri, scoasă diferit, dă rezultate diferite.

Greșeli frecvente

Greșeli frecvente de concurs:

front() sau pop() pe coadă goală: comportament nedefinit (poate da crash sau gunoi). Testează mereu !q.empty() întâi.
Te aștepți ca pop() să returneze valoarea: la std::queue, pop() returnează void. Citește valoarea cu front() înainte de pop.
Cauți iteratori sau q[i]: nu există. Adaptorul nu expune acces aleatoriu; ca să vezi tot conținutul, trebuie să-l scoți element cu element (sau să copiezi coada întâi, dacă vrei s-o păstrezi).
Confuzia front cu back: front este cel care iese, back este cel care tocmai a intrat. Le inversezi și citești capătul greșit.

Vizualizare

Urmărește cum elementele intră la spate (push) și ies din față (pop), respectând ordinea FIFO:

Indiciu

Folosește ← / → ca să avansezi pas cu pas. Fii atent: front-ul se schimbă abia după pop, nu după push.

Recapitulare

std::queue este un adaptor peste deque: expune doar push, pop, front, back, size, empty — toate O(1).
Interfața e îngustă intenționat: fără iteratori, fără []. Asta forțează disciplina FIFO.
pop() scoate fără să returneze; citește cu front() întâi și verifică !q.empty() înainte de orice acces.