🧱 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ón | Costo | Notas |
|---|---|---|
| push_back / push_front | O(1) | su gracia frente a vector |
| pop_back / pop_front | O(1) | |
| d[i] | O(1) | un poco más lento que en vector |
| insert / erase en el medio | O(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.