Noțiunea de deque — coadă cu două capete

De ce contează?

Imaginează-ți un tunel de metrou cu uși la ambele capete. Pasagerii pot urca și coborî și prin față, și prin spate. O coadă obișnuită are o singură ușă de intrare și una de ieșire; deque-ul le are pe toate patru. De aici și flexibilitatea lui.

Ce este un deque

Un deque (citit „dec”, de la Double-Ended Queue — coadă cu două capete) este o structură în care poți adăuga și scoate la ambele capete: și în față, și la spate. E o coadă mai generală.

Cele patru operații de capăt:

push_front / pop_front — la față;
push_back / pop_back — la spate.

Observația-cheie

Deque-ul le cuprinde pe celelalte: folosit doar cu push_back + pop_front e o coadă (FIFO); folosit doar cu push_back + pop_back e o stivă (LIFO). De aceea îl numim o structură „universală” pentru capete.

Cum se comportă

Pornim de la [20 30] și adăugăm la ambele capete:

deque	20	30
	fata	spate

Deque cu două elemente. Ambele capete sunt deschise.

deque	10	20	30	40
	push_front			push_back

push_front(10) adaugă în stânga, push_back(40) în dreapta — simultan posibil.

Tabel de operații

Operație	Ce face
`push_front(x)`	adaugă `x` în față
`push_back(x)`	adaugă `x` la spate
`pop_front()`	scoate din față
`pop_back()`	scoate din spate
`front()` / `back()`	citește capătul respectiv
`empty()` / `size()`	starea structurii

Unde ajută cele două capete

Istoric navigabil (înainte/înapoi), unde adaugi și scoți de la ambele capete.
Fereastră glisantă cu maxim/minim — scoți din față elementele expirate și din spate pe cele „învinse” (vei vedea la aplicații).
Oriunde ai nevoie când de FIFO, când de LIFO, fără a schimba structura.

Vizualizare

Urmărește cum elementele intră și ies pe la ambele capete, spre deosebire de coada cu un singur sens:

Greșeli frecvente

Confuzii la început:

Folosești deque ca să accesezi mijlocul. Operațiile rapide sunt la capete; pentru acces la mijloc, un vector e mai potrivit.
Confunzi pop_front cu pop_back. Capete diferite, rezultate diferite — verifică exact ce capăt cere problema.
Uiți că pop_* nu întoarce valoarea (ca la std::queue): citește cu front()/back() întâi.
Crezi că deque e mereu mai bun ca o coadă. Dacă ai nevoie doar de FIFO, queue e mai simplu și mai clar.

Recapitulare

Deque = coadă cu două capete: adaugi și scoți și în față, și la spate.
Generalizează coada (FIFO) și stiva (LIFO), după ce operații folosești.
Operațiile rapide sunt la capete; pentru acces la mijloc folosește un vector.