deque — container cu acces la ambele capete

De ce contează?

Gândește-te la o coadă la casă unde noii veniți pot intra și prin față, și prin spate, iar tu, ca observator, poți să te uiți direct la a treia persoană din rând fără să o numeri pe rând. Aceasta este puterea unui deque din STL: lucrezi la ambele capete, dar vezi și interiorul instantaneu.

Ce este `std::deque` și de ce există

Un deque (double-ended queue) este un container STL care îți dă două lucruri deodată:

adăugare și scoatere la ambele capete în O(1);
acces aleatoriu la orice poziție cu d[i], ca la un vector.

De ce contează combinația asta? Pentru că stack și queue sunt doar adaptoare: îți ascund interiorul și te lasă să atingi un singur capăt. Un vector, în schimb, are d[i], dar adaugă ieftin numai la sfârșit — un push_front simulat cu insert la poziția 0 mută toate elementele, deci O(n).

deque rezolvă exact acest gol: e singurul container standard care oferă simultan push_front rapid și indexare directă.

Exemplu pas cu pas

Pornim de la un deque gol și urmărim cum se schimbă conținutul:

deque	3	7	2
	front		back

Front și back sunt cele două capete active. Indexarea d[i] îți dă orice celulă din interior.

push_back(7) pe gol → [7]
push_front(3) → [3, 7]
push_back(2) → [3, 7, 2]
d[1] citește direct elementul din mijloc → 7
pop_front() scoate primul → [7, 2]

Observă că am atins ambele capete și am citit interiorul fără să mut nimic — la un vector, push_front(3) ar fi cerut deplasarea tuturor elementelor existente.

Implementare C++

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

int main() {
    deque<int> d;
    d.push_back(7);     // [7]
    d.push_front(3);    // [3, 7]
    d.push_back(2);     // [3, 7, 2]

    cout << d.front() << "\n";   // 3  (capatul din fata)
    cout << d.back()  << "\n";   // 2  (capatul din spate)
    cout << d[1]      << "\n";   // 7  (acces aleatoriu, ca la vector)
    cout << d.size()  << "\n";   // 3

    d.pop_front();      // [7, 2]
    d.pop_back();       // [7]

    // parcurgere cu iteratori (range-based for)
    for (int x : d) {
        cout << x << " ";        // 7
    }
    cout << "\n";

    // parcurgere clasica cu indici
    for (int i = 0; i < (int)d.size(); i++) {
        cout << d[i] << " ";     // 7
    }
    return 0;
}

Complexitate

Operație	Timp
`push_front` / `push_back`	O(1)
`pop_front` / `pop_back`	O(1)
`front` / `back`	O(1)
`d[i]` (acces aleatoriu)	O(1)
`insert` / `erase` la mijloc	O(n)
parcurgere cu iteratori (n elemente)	O(n)

Observația-cheie

Regula de alegere: dacă adaugi mereu doar la sfârșit, vector e suficient și puțin mai rapid în practică. Alegi deque doar când chiar ai nevoie de push_front/pop_front rapid împreună cu acces la interior.

Greșeli frecvente

Greșeli frecvente cu deque:

pop_front/pop_back nu returnează valoarea: trebuie să citești întâi cu front()/back(), abia apoi scoți.
pop pe deque gol: e comportament nedefinit; verifică mereu !d.empty() înainte.
Folosești deque doar pentru push_back: irosești memorie și viteză față de vector, care e mai potrivit acolo.
Te bazezi pe adrese stabile: spre deosebire de vector, deque nu garantează că elementele stau contiguu în memorie, deci nu pasa &d[0] ca pe un pointer la un bloc continuu.

Vizualizare

Urmărește cum cele două capete lucrează independent, iar interiorul rămâne accesibil pe tot parcursul:

Indiciu

Folosește ← / → pentru a derula operațiile pas cu pas și observă cum push_front și push_back cresc deque-ul în direcții opuse.

Recapitulare

deque din STL combină lucrul la ambele capete (O(1)) cu acces aleatoriu d[i] — ceva ce nici vector, nici queue/stack nu îți dau împreună.
Alege-l când ai nevoie de push_front/pop_front rapid; altfel vector rămâne alegerea simplă.
Pe baza lui se construiește tehnica deque monoton (maximul pe fereastră glisantă), tratată separat — aici am stat pe container și interfața lui.

Ce este std::deque și de ce există