Coada

Coada este o structură FIFO („primul intrat, primul ieșit”). Dacă Ana, Dan și Ioana intră în această ordine într-o coadă, Ana este servită prima. Păstrăm un indice prim pentru primul element și un indice ultim pentru ultimul; adăugarea se face după ultim, iar eliminarea avansează prim. În Python, o listă poate arăta ideea: q = ["Ana", "Dan", "Ioana"], q[0] este „Ana”, iar q.pop(0) elimină și returnează „Ana”. Pentru cozi lungi, collections.deque oferă extragere eficientă de la început.

Coada este o structură de date liniară cu două capete: elementele se adaugă la sfârșit și se elimină de la început. Ordinea de acces este FIFO: primul element introdus este primul scos. Operațiile fundamentale sunt introducerea la sfârșit (push), eliminarea de la început (pop), citirea primului element (front) și testul de coadă goală. În implementarea cu tablou se păstrează doi indici: prim pentru primul element și ultim pentru ultimul; coada goală are prim = 1 și ultim = 0. Introducerea mărește ultim și scrie elementul, iar eliminarea mărește prim. Citirea sau eliminarea cer ca prim <= ultim. Numărul elementelor este ultim - prim + 1. Varianta liniară nu refolosește pozițiile eliberate; la capacitatea $C$, o coadă circulară actualizează indicii cu (indice + 1) % C. În C++, std::queue oferă push, front, pop și empty; în Python, collections.deque oferă append și popleft în timp constant, spre deosebire de list.pop(0), care mută toate elementele. Coada este structura parcurgerii în lățime a unui graf: vârfurile descoperite intră în coadă și sunt procesate în ordinea descoperirii.

Exemplul 1 — coada cu deque (Python).

from collections import deque
q = deque()
for x in (2, 5, 7):
    q.append(x)
if q:
    scos = q.popleft()
    print(scos, q[0] if q else "coadă goală")

După cele trei inserări, coada este [2, 5, 7]. Extragerea întoarce 2, apoi primul element este 5; ieșirea este 2 5. Ambele operații durează un număr constant de pași.

Exemplul 2 — coada cu tablou (C++).

#include <iostream>
using namespace std;
int main() {
    int c[10], prim = 1, ultim = 0;
    c[++ultim] = 2; c[++ultim] = 5; c[++ultim] = 7;
    if (prim <= ultim) {
        int scos = c[prim];
        ++prim;
        if (prim <= ultim) cout << scos << " " << c[prim];
        else cout << scos;
    }
    return 0;
}

După inserări, (prim, ultim) = (1, 3). Se salvează 2 în scos, prim avansează la 2 și se citește 5 numai după verificarea că poziția mai există. Ieșirea este 2 5. Numărul elementelor rămase este $3-2+1=2$.

Exemplul 3 — coada circulară. Cu capacitatea 4, elementele sunt memorate în pozițiile 0..3, iar poziția unui element nou este (prim + n) % 4, unde n este numărul elementelor. Se introduc 1, 2, 3 (pozițiile 0, 1, 2), se scot două elemente (prim devine 2), apoi se introduc 4, 5, 6 în pozițiile 3, 0 și 1. Tabloul conține acum 5 6 3 4, coada are 4 elemente, iar primul element este 3. Pozițiile din fața lui prim au fost refolosite, ceea ce coada liniară nu permite.

Notează la fiecare operație perechea (prim, ultim) și conținutul activ, adică elementele de la prim la ultim. Elementele scoase rămân în tablou, dar nu mai fac parte din coadă. Diferența dintre stivă și coadă se vede la scoatere: stiva scoate ultimul intrat, coada pe primul. La coada circulară, urmărește și poziția în care se scrie un element nou.

Exemplul 4 — urmărirea unui fragment. Ce se afișează în urma executării secvenței de mai jos?

int c[10], prim = 1, ultim = 0;
c[++ultim] = 4;
c[++ultim] = 8;
c[++ultim] = 6;
prim++;
c[++ultim] = 9;
prim++;
cout << c[prim] << ' ' << ultim - prim + 1;

• a) 4 2
• b) 6 2
• c) 6 4
• d) 9 2

Răspunsul corect este b). După trei inserări, coada conține 4, 8, 6 pe pozițiile 1–3. Primul prim++ elimină 4, deci prim = 2. Se adaugă 9 pe poziția 4. Al doilea prim++ elimină 8, deci prim = 3 și coada conține 6 și 9. Primul element este c[3] = 6, iar numărul de elemente este $4-3+1=2$. Varianta d) citește ultimul element, nu primul.

Coada goală. Scoaterea dintr-o coadă goală este o eroare: în implementarea cu tablou, condiția prim > ultim trebuie verificată înainte de orice pop, iar în Python popleft() aplicat unui deque gol produce IndexError. De aceea ciclurile de prelucrare au forma „cât timp coada nu este goală”.

Greșeli frecvente

• Greșit: într-o coadă se scoate ultimul element introdus.
  Corect: se scoate primul element introdus.
• Greșit: după eliminarea unui element, valoarea lui este ștearsă din tablou.
  Corect: prim avansează, iar elementul nu mai face parte din coadă.
• Greșit: list.pop(0) este la fel de rapidă ca deque.popleft().
  Corect: pop(0) mută toate elementele rămase.

Înainte și după