Operații cu coada — push, pop, front

De ce contează?

Știi deja regula cozii: primul venit, primul servit. Acum înveți butoanele concrete cu care o comanzi în C++ — cum adaugi un client la rând, cum vezi cine urmează și cum îl servești. Patru-cinci operații, atât îți trebuie.

Coada din STL

C++ îți oferă std::queue din antetul <queue> — nu trebuie să-ți construiești singur structura. Operațiile esențiale:

Operație	Ce face
`q.push(x)`	adaugă `x` la spate
`q.pop()`	scoate elementul din față (NU întoarce nimic)
`q.front()`	citește elementul din față
`q.back()`	citește ultimul adăugat
`q.empty()`	`true` dacă e goală
`q.size()`	câte elemente are

Observația-cheie

Atenție la pop(): are tip void, doar elimină. Dacă vrei valoarea servită, o citești cu front() înainte de a face pop(). Sunt două operații separate.

Algoritmul pas cu pas

Adăugăm 10, 20, 30 și servim toată coada în ordine:

q	10	20	30
	front		back

După push(10), push(20), push(30): front=10, back=30. Servirea va da 10, 20, 30.

push(10) -> [10]
push(20) -> [10 20]
push(30) -> [10 20 30]
front()  -> 10
pop()    -> [20 30]
front()  -> 20

Implementare C++

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

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);

    cout << q.front() << endl;   // 10 (cine urmeaza)
    cout << q.size() << endl;    // 3

    while (!q.empty()) {         // serveste toata coada
        cout << q.front() << " ";// citeste inainte de pop
        q.pop();                 // scoate din fata
    }
    // 10 20 30
    return 0;
}

Coada implementată cu vector (cum funcționează pe dedesubt)

Ca să înțelegi structura, o poți simula cu un vector și doi indici, st (față) și dr (spate):

int coada[1000];
int st = 0, dr = 0;          // coada goala cand st == dr

void push(int x) { coada[dr++] = x; }   // adauga la spate
int front()      { return coada[st]; }  // citeste fata
void pop()       { st++; }               // avanseaza fata
bool empty()     { return st == dr; }

Indiciu

Varianta cu vector explică de ce pop() e O(1): nu mutăm elementele, doar avansăm indicele st. Coada „înaintează” prin vector.

Complexitate

Operație	Timp	Spațiu
`push`, `pop`, `front`, `empty`, `size`	O(1)	O(1)
Procesarea întregii cozi	O(n)	O(n)

Greșeli frecvente

Greșeli reale:

Crezi că pop() întoarce valoarea. Nu — e void. Citește cu front() întâi, apoi pop().
Apelezi front()/pop() pe coadă goală. Comportament nedefinit. Verifică !q.empty().
La varianta cu vector, dimensiune prea mică. dr crește la fiecare push; dacă faci multe push-uri, vectorul fix se umple. Folosește coadă circulară sau std::queue.
Confunzi front() cu back(). front = cine urmează (cel mai vechi), back = ultimul intrat.

Recapitulare

std::queue: push (spate), pop (față, void), front/back, empty, size — toate O(1).
pop() nu întoarce nimic: citește cu front() înainte de a scoate.
Pe dedesubt, o coadă pe vector avansează cu doi indici; verifică mereu empty înainte de acces.