🧱 deque

Estructura de datos · Viene en la librería estándar (STL) · Tema: Estructuras de Datos Catálogo completo: Catálogo de estructuras

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Una cola de doble extremo: agrega y saca por adelante y por atrás en O(1), y además permite indexar como un vector.

Operaciones y costo

OperaciónCostoNotas
push_back / push_frontO(1)su gracia frente a vector
pop_back / pop_frontO(1)
d[i]O(1)un poco más lento que en vector
insert / erase en el medioO(n)

Por dentro

Bloques de memoria enlazados en vez de un solo bloque contiguo. Por eso puede crecer por ambos lados sin copiar todo, a cambio de accesos un poco más lentos que los de vector.

Cuándo usarla

Ventanas deslizantes con máximo o mínimo (la deque monótona), BFS 0-1, y cualquier proceso que consuma por los dos extremos.

Cómo se usa (C++)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    deque<int> d;
    d.push_back(2);
    d.push_front(1);      // ¡también por adelante, en O(1)!
    cout << d[0] << " " << d.back() << "\n";   // 1 2
    d.pop_front();
 
    // el patrón estrella: máximo de cada ventana de largo k, en O(n) total
    vector<int> a = {1, 3, 2, 5, 4, 1};
    int k = 3;
    deque<int> dq;                            // guarda ÍNDICES, con valores decrecientes
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();   // salió de la ventana
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();   // ya no puede ser máximo
        dq.push_back(i);
        if (i >= k - 1) cout << a[dq.front()] << " ";                // el máximo va al frente: 3 5 5 5
    }
    cout << "\n";
}
 

⚠️ Notas

El patrón de arriba se llama deque monótona: cada índice entra y sale a lo más una vez, y por eso el total es O(n) aunque una iteración descarte muchos. Es la misma idea de amortización del Stack monótono.

🔗 Relacionados