Deque (coadă cu două capete)

Un deque (Double-Ended Queue, pronunțat “dec”) este o structură de date care permite adăugarea și eliminarea elementelor de la ambele capete - atât din față cât și din spate.

Este o combinație între stivă și coadă.

Operații fundamentale

Exemplu vizual

push_back(3):    [3]
push_back(7):    [3, 7]
push_front(1):   [1, 3, 7]
push_back(9):    [1, 3, 7, 9]
pop_front():     [3, 7, 9]
pop_back():      [3, 7]

front = 3, back = 7

Implementare pe vector

Folosim un vector mare cu un offset la mijloc, ca să putem crește în ambele direcții:

int dq[200001];
int st, dr; // st = primul element, dr = ultimul

void init() {
    st = 100001;
    dr = 100000;
}

void push_back(int x) {
    dr++;
    dq[dr] = x;
}

void push_front(int x) {
    st--;
    dq[st] = x;
}

void pop_back() {
    if (st <= dr) dr--;
}

void pop_front() {
    if (st <= dr) st++;
}

int front() {
    return dq[st];
}

int back() {
    return dq[dr];
}

bool empty() {
    return st > dr;
}

int size() {
    return dr - st + 1;
}

Pornim cu st și dr la mijlocul vectorului - astfel avem loc să creștem în ambele direcții.

Problema principală: minimul pe fereastră glisantă în O(n)

Aceasta este problema pentru care deque-ul este cel mai cunoscut. Am văzut-o la Sliding Window - acolo o rezolvam în O(n*K). Cu deque, o rezolvăm în O(n).

Problema

Avem un vector cu n elemente și un număr K. Pentru fiecare fereastră de K elemente consecutive, găsim minimul.

Vector: 3 1 4 1 5 9 2 6    K = 3

Ferestre:
[3 1 4] → min = 1
[1 4 1] → min = 1
[4 1 5] → min = 1
[1 5 9] → min = 1
[5 9 2] → min = 2
[9 2 6] → min = 2

Ideea

Menținem un deque cu indicii elementelor candidate la minim. Deque-ul este mereu crescător după valori (cel mai mic e în față).

La fiecare pas: 1. Scoatem din față indicii care au ieșit din fereastră 2. Scoatem din spate indicii cu valori mai mari sau egale decât elementul curent (nu vor fi niciodată minim) 3. Adăugăm indicele curent la spate 4. Minimul ferestrei curente e v[front()]

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int dq[100001]; // deque cu indici
int st, dr;
int n, k;

int main()
{
    fin >> n >> k;
    for (int i = 1; i <= n; i++)
        fin >> v[i];

    st = 1; dr = 0;

    for (int i = 1; i <= n; i++) {
        // Scoatem indicii care au ieșit din fereastră
        while (st <= dr && dq[st] < i - k + 1)
            st++;

        // Scoatem din spate elementele mai mari (nu vor fi minim)
        while (st <= dr && v[dq[dr]] >= v[i])
            dr--;

        // Adăugăm indicele curent
        dr++;
        dq[dr] = i;

        // Afișăm minimul ferestrei (după ce avem primele K elemente)
        if (i >= k)
            fout << v[dq[st]] << " ";
    }

    return 0;
}

date.in:

8 3
3 1 4 1 5 9 2 6

date.out:

1 1 1 1 2 2

Pas cu pas

Pasul 4 explicat: - v[4] = 1 - Scoatem din spate: v[3]=4 >= 1 → scoatem. v[2]=1 >= 1 → scoatem. Deque gol. - Adăugăm indicele 4. - Indicele 1 a ieșit din fereastră (1 < 4-3+1 = 2), dar deja nu mai e. - Minim: v[4] = 1

Pasul 7 explicat: - v[7] = 2 - Scoatem din față: indicele 4 a ieșit (4 < 7-3+1 = 5) → scoatem. - Scoatem din spate: v[6]=9 >= 2, v[5]=5 >= 2 → scoatem tot. - Deque: [7], minim = v[7] = 2

De ce O(n)?

Fiecare indice intră în deque o singură dată (push_back) și iese cel mult o dată (pop_front sau pop_back). Total: 2n operații = O(n).

Varianta cu maxim pe fereastră

Singura diferență: schimbăm >= în <= la eliminarea din spate:

// Pentru MAXIM:
while (st <= dr && v[dq[dr]] <= v[i])
    dr--;

Deque-ul devine descrescător - cel mai mare e în față.

Problema: diferența maximă pe fereastră

Vrem max(v[i..i+K-1]) - min(v[i..i+K-1]) maximă peste toate ferestrele.

Folosim două deque-uri: unul pentru minim, altul pentru maxim.

int dqMin[100001], stMin = 1, drMin = 0;
int dqMax[100001], stMax = 1, drMax = 0;

for (int i = 1; i <= n; i++) {
    while (stMin <= drMin && dqMin[stMin] < i - k + 1) stMin++;
    while (stMin <= drMin && v[dqMin[drMin]] >= v[i]) drMin--;
    drMin++; dqMin[drMin] = i;

    while (stMax <= drMax && dqMax[stMax] < i - k + 1) stMax++;
    while (stMax <= drMax && v[dqMax[drMax]] <= v[i]) drMax--;
    drMax++; dqMax[drMax] = i;

    if (i >= k) {
        int dif = v[dqMax[stMax]] - v[dqMin[stMin]];
        if (dif > maxDif) maxDif = dif;
    }
}

Deque vs Stivă vs Coadă

Deque-ul poate simula atât stiva (push_back + pop_back) cât și coada (push_back + pop_front).

Greșeli frecvente

1. Stocarea valorilor în loc de indici

dq[dr] = v[i]; // GREȘIT - nu putem verifica dacă a ieșit din fereastră
dq[dr] = i;    // CORECT - stocăm indicele, accesăm v[dq[...]] pentru valoare

Avem nevoie de indici ca să verificăm dq[st] < i - k + 1 (ieșit din fereastră).

2. Ordinea operațiilor

Ordinea corectă la fiecare pas: 1. Scoatem din față (ieșiți din fereastră) 2. Scoatem din spate (mai mari/mici decât curentul) 3. Adăugăm curentul 4. Citim minimul/maximul

Dacă inversăm, putem avea indici invalizi.

3. Afișarea înainte de a avea K elemente

if (i >= k) // afișăm doar după ce avem prima fereastră completă

Ce să reții

• Deque permite operații O(1) la ambele capete.
• Problema clasică: min/max pe fereastră glisantă în O(n).
• Stocăm indici în deque, nu valori.
• Deque-ul este mereu monoton (crescător pentru min, descrescător pentru max).
• Fiecare element intră și iese cel mult o dată → O(n) total.
• Poate înlocui stiva (push_back + pop_back) sau coada (push_back + pop_front).

Probleme

pbinfoBest Sum2→

pbinfoMaxsecvk→

pbinfoPlanor→

pbinfoMister→