7 - Deque (Double-Ended Queue)
7.1 Concepto y ventajas
Un deque es una cola doblemente terminada que permite insertar y extraer elementos tanto por el frente como por el final. Mantiene el orden de llegada, pero admite patrones de acceso más flexibles que una cola FIFO estricta.
- Simetría: las operaciones son equivalentes en ambos extremos, lo que simplifica algoritmos que alternan productores y consumidores.
- Compatibilidad con stacks: puede comportarse como pila o como cola dependiendo del extremo utilizado.
- Reducción de copias: evita desplazar elementos internos, incluso cuando se convierte en una estructura circular.
Es la base de planificadores, caches LRU y estructuras de datos avanzadas como los algoritmos de ventana deslizante.
7.2 Operaciones básicas
La interfaz mínima se compone de cuatro operaciones de modificación y dos accesos de solo lectura:
push_front/push_back: insertan un nuevo nodo en cada extremo.pop_front/pop_back: retiran nodos y retornan el valor asociado.front/back: leen sin extraer, devolviendo -1 o un código de error si la estructura está vacía.
Para evitar condiciones de carrera se recomienda empaquetar cada operación en funciones autónomas y documentar si son atómicas.
7.3 Representación interna
Hay dos enfoques predominantes:
- Array circular: requiere controlar dos punteros y asegurar que exista espacio libre. Ofrece cache locality y es apropiado para tamaños acotados.
- Lista doblemente enlazada: cada nodo contiene punteros a su anterior y siguiente, facilitando inserciones constantes sin dimensiones prefijadas.
Elegir uno u otro depende de si prima la velocidad o la elasticidad. En sistemas embebidos se prefiere el array, mientras que en servidores con cargas variables manda la lista.
7.4 Enfoque con array circular
En un deque circular, los índices frente y final se desplazan en sentidos opuestos y aprovechan el operador módulo para reutilizar el buffer.
#define CAP_DEQUE 64
typedef struct {
int datos[CAP_DEQUE];
int frente;
int final;
int cantidad;
} DequeArray;
void inicializarDeque(DequeArray *d) {
d->frente = 0;
d->final = 0;
d->cantidad = 0;
}
static int anteriorIndice(int idx) {
return (idx - 1 + CAP_DEQUE) % CAP_DEQUE;
}
static int siguienteIndice(int idx) {
return (idx + 1) % CAP_DEQUE;
}
int pushFront(DequeArray *d, int valor) {
if (d->cantidad == CAP_DEQUE) {
return 0;
}
d->frente = anteriorIndice(d->frente);
d->datos[d->frente] = valor;
d->cantidad++;
return 1;
}
int pushBack(DequeArray *d, int valor) {
if (d->cantidad == CAP_DEQUE) {
return 0;
}
d->datos[d->final] = valor;
d->final = siguienteIndice(d->final);
d->cantidad++;
return 1;
}Los pop simétricos aplican el mismo principio. Registrar cantidad permite distinguir entre lleno y vacío aun cuando los índices coincidan.
7.5 Implementación con lista doble
Una lista doblemente enlazada simplifica las operaciones de extremos, ya que cada nodo conoce a sus vecinos. Se recomienda mantener punteros a ambos extremos y un contador de nodos.
typedef struct Nodo {
int dato;
struct Nodo *anterior;
struct Nodo *siguiente;
} Nodo;
typedef struct {
Nodo *frente;
Nodo *final;
int cantidad;
} DequeLista;
void inicializarLista(DequeLista *d) {
d->frente = NULL;
d->final = NULL;
d->cantidad = 0;
}
int push_front_lista(DequeLista *d, int valor) {
Nodo *nuevo = malloc(sizeof(Nodo));
if (!nuevo) {
return 0;
}
nuevo->dato = valor;
nuevo->anterior = NULL;
nuevo->siguiente = d->frente;
if (d->frente) {
d->frente->anterior = nuevo;
} else {
d->final = nuevo;
}
d->frente = nuevo;
d->cantidad++;
return 1;
}
int pop_back_lista(DequeLista *d, int *valor) {
if (!d->final) {
return 0;
}
Nodo *nodo = d->final;
*valor = nodo->dato;
d->final = nodo->anterior;
if (d->final) {
d->final->siguiente = NULL;
} else {
d->frente = NULL;
}
free(nodo);
d->cantidad--;
return 1;
}Este estilo evita reasignar arrays y mantiene la complejidad constante aun cuando el deque crece o se vacía repetidamente.
7.6 Casos de uso prácticos
- Ventana deslizante: los algoritmos de máximo en ventanas utilizan un deque para expulsar elementos fuera de rango por el frente y agregar nuevos por el final.
- Planificadores de tareas: sistemas operativos como FreeBSD emplean deques para alternar tareas interactivas y de fondo.
- Backtracking: combinar pops en ambos extremos facilita explorar grafos en ordenes personalizados.
Siempre documenta si el deque es seguro para hilos o si requiere protección externa (mutex, spinlocks) antes de exponerlo a un scheduler.
7.7 Ejemplo completo en C
El siguiente programa implementa un deque mediante lista doble y expone todas las operaciones, además de una función imprimir para depurar el estado.
#include <stdio.h>
#include <stdlib.h>
typedef struct Nodo {
int dato;
struct Nodo *anterior;
struct Nodo *siguiente;
} Nodo;
typedef struct {
Nodo *frente;
Nodo *final;
int cantidad;
} Deque;
void inicializar(Deque *d) {
d->frente = NULL;
d->final = NULL;
d->cantidad = 0;
}
int push_front(Deque *d, int valor) {
Nodo *nuevo = malloc(sizeof(Nodo));
if (!nuevo) {
return 0;
}
nuevo->dato = valor;
nuevo->anterior = NULL;
nuevo->siguiente = d->frente;
if (d->frente) {
d->frente->anterior = nuevo;
} else {
d->final = nuevo;
}
d->frente = nuevo;
d->cantidad++;
return 1;
}
int push_back(Deque *d, int valor) {
Nodo *nuevo = malloc(sizeof(Nodo));
if (!nuevo) {
return 0;
}
nuevo->dato = valor;
nuevo->siguiente = NULL;
nuevo->anterior = d->final;
if (d->final) {
d->final->siguiente = nuevo;
} else {
d->frente = nuevo;
}
d->final = nuevo;
d->cantidad++;
return 1;
}
int pop_front(Deque *d, int *valor) {
if (!d->frente) {
return 0;
}
Nodo *nodo = d->frente;
*valor = nodo->dato;
d->frente = nodo->siguiente;
if (d->frente) {
d->frente->anterior = NULL;
} else {
d->final = NULL;
}
free(nodo);
d->cantidad--;
return 1;
}
int pop_back(Deque *d, int *valor) {
if (!d->final) {
return 0;
}
Nodo *nodo = d->final;
*valor = nodo->dato;
d->final = nodo->anterior;
if (d->final) {
d->final->siguiente = NULL;
} else {
d->frente = NULL;
}
free(nodo);
d->cantidad--;
return 1;
}
void imprimir(const Deque *d) {
printf("[deque] cantidad=%d -> ", d->cantidad);
for (Nodo *n = d->frente; n; n = n->siguiente) {
printf("%d ", n->dato);
}
puts("");
}
void vaciar(Deque *d) {
int descartado;
while (pop_front(d, &descartado)) {
}
}
int main(void) {
Deque deque;
inicializar(&deque);
push_back(&deque, 10);
push_back(&deque, 20);
push_front(&deque, 5);
imprimir(&deque);
int valor;
pop_front(&deque, &valor);
printf("pop_front = %d\n", valor);
imprimir(&deque);
push_front(&deque, 1);
push_back(&deque, 99);
imprimir(&deque);
pop_back(&deque, &valor);
printf("pop_back = %d\n", valor);
imprimir(&deque);
vaciar(&deque);
imprimir(&deque);
return 0;
}Ejecuta el programa y observa cómo las operaciones afectan al contador y a los nodos interiores para validar que no quedan referencias colgantes.
