Operații cu deque — ambele capete în C++

De ce contează?

Ai înțeles ideea de deque: două capete deschise. Acum vezi exact ce butoane apeși în C++. Sunt aceleași ca la coadă, dar dublate — câte unul pentru fiecare capăt — plus un bonus: poți chiar să te uiți direct la al i-lea element.

Deque-ul din STL

std::deque din antetul <deque> îți dă toate operațiile de capăt în O(1), plus acces prin index:

Operație	Ce face
`d.push_back(x)` / `d.push_front(x)`	adaugă la spate / în față
`d.pop_back()` / `d.pop_front()`	scoate din spate / din față (void)
`d.front()` / `d.back()`	citește capetele
`d[i]`	acces direct la elementul `i`
`d.empty()` / `d.size()`	starea structurii

Observația-cheie

Bonusul față de queue și stack: d[i] îți dă orice element în O(1). Deque-ul e și coadă, și stivă, și „mini-vector” cu inserare rapidă la ambele capete.

Algoritmul pas cu pas

d	2	1	3
	0	1	2
	front		back

După push_back(1), push_front(2), push_back(3): front=2, back=3, iar d[0]=2.

push_back(1)   -> [1]
push_front(2)  -> [2 1]
push_back(3)   -> [2 1 3]
front() = 2    back() = 3    d[1] = 1
pop_front()    -> [1 3]

Implementare C++

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

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

    cout << d.front() << " " << d.back() << endl; // 2 3
    cout << d[1] << endl;                          // 1 (acces direct)

    d.pop_front();               // [1 3]
    cout << d.front() << endl;   // 1

    while (!d.empty()) {
        cout << d.front() << " ";
        d.pop_front();
    }
    // 1 3
    return 0;
}

Complexitate

Operație	Timp	Spațiu
`push_`, `pop_`, `front`, `back`	O(1)	O(1)
`d[i]` (acces prin index)	O(1)	O(1)
Inserare/ștergere la mijloc	O(n)	—

Greșeli frecvente

Greșeli reale:

pop_front()/pop_back() cred că întorc valoarea — sunt void. Citește întâi.
Apel pe deque gol. front()/pop_*() pe deque gol = comportament nedefinit. Verifică empty().
Inserezi la mijloc des, crezând că e O(1). Doar capetele sunt O(1); la mijloc e O(n).
Folosești deque când ajungea un vector. Dacă adaugi doar la spate și accesezi prin index, vector e mai simplu și mai rapid în practică.

Recapitulare

std::deque: push_front/back, pop_front/back (void), front/back, d[i] — toate O(1).
Citește valoarea cu front()/back() înainte de pop_*; verifică empty().
Capetele sunt O(1); mijlocul e O(n) — alege deque doar când ai nevoie de ambele capete.