Deque — coadă cu două capete

De ce contează?

Imaginează-ți un tunel prin care poți să intri și să ieși pe ambele capete. Poți adăuga sau scoate oameni și din față, și din spate, la fel de ușor. Asta este un deque: o coadă deschisă la ambele capete.

Ce este un deque?

Un deque (double-ended queue, „dec”) este o structură care permite adăugare și scoatere la ambele capete în O(1). E o generalizare: poate imita și o stivă, și o coadă.

Operații, toate O(1):

push_front / pop_front — la început;
push_back / pop_back — la final;
front / back — citește capetele.

deque	3	7	2	9
	front			back

Adaugi/scoți liber la ambele capete — front și back, fiecare O(1).

Deque din STL

#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
    cout << d.back()  << "\n";  // 2
    d.pop_front();     // [7, 2]
    d.pop_back();      // [7]
    cout << d.size() << "\n";   // 1
    return 0;
}

Observația-cheie

deque din STL permite și acces aleatoriu (d[i]), spre deosebire de queue și stack. Dar puterea lui specifică e lucrul la ambele capete.

Aplicația-vedetă: maximul pe fereastră glisantă

Vrei maximul fiecărei ferestre de lungime k dintr-un vector. Naiv: O(n · k). Cu un deque monoton scazi la O(n): ții în deque indici ale căror valori sunt descrescătoare; frontul e mereu maximul ferestrei.

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

int main() {
    int v[] = {1, 3, -1, 3, 5, 3, 6, 7};
    int n = 8, k = 3;
    deque<int> d;   // tine INDICI, valori descrescatoare

    for (int i = 0; i < n; i++) {
        // scoate din spate indicii cu valoare mai mica (inutili)
        while (!d.empty() && v[d.back()] <= v[i]) d.pop_back();
        d.push_back(i);
        // scoate din fata indicele iesit din fereastra
        if (d.front() <= i - k) d.pop_front();
        // fereastra completa -> frontul e maximul
        if (i >= k - 1) cout << v[d.front()] << " ";
    }
    // 3 3 5 5 6 7
    return 0;
}

De ce e O(n)? Fiecare index intră și iese din deque cel mult o dată, deci toate operațiile însumate sunt liniare.

Complexitate

Operație	Timp	Spațiu
push/pop la oricare capăt	O(1)	—
Maxim pe fereastră glisantă (n elemente)	O(n)	O(k)

Greșeli frecvente

Greșeli frecvente de concurs:

Ții valori în loc de indici: fără indici nu poți elimina elementele ieșite din fereastră.
Comparație greșită la curățarea spatelui: <= vs < schimbă comportamentul la valori egale; pentru maxim, <= elimină duplicatele vechi corect.
pop pe deque gol: testează !d.empty() întâi.
Fereastra raportată prea devreme: afișezi maximul abia când i >= k - 1 (prima fereastră completă).

Vizualizare

Urmărește operațiile la ambele capete ale structurii:

Indiciu

Observă cum push_front și push_back lucrează independent. Folosește ← / → pentru a urmări fiecare capăt.

Deque monoton — fereastră glisantă

Aceeași structură, folosită ca deque monoton, dă maximul fiecărei ferestre în O(n).