Deque en C: ejercicio resuelto

Si buscas deque en C ejercicio resuelto, aquí tienes la implementación con array circular que soporta inserción y extracción en ambos extremos en O(1). Un deque (double-ended queue, o cola de doble extremo) generaliza tanto la pila como la cola: se puede usar como cualquiera de los dos.

Con el array circular, los índices front y rear avanzan módulo CAPACIDAD, evitando desplazamiento de elementos.

Enunciado

Implementa un deque con capacidad fija de 8 elementos que soporte:

push_front(d, v): inserta al principio.
push_back(d, v), inserta al final.
pop_front(d): elimina y devuelve el elemento del principio.
pop_back(d): elimina y devuelve el elemento del final.
imprimir(d): muestra el contenido de frente a fondo.

Demuestra las cuatro operaciones con una secuencia de inserciones y extracciones.

Solución en C

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>

#define CAP 8

typedef struct {
    int datos[CAP];
    int frente;   /* índice del primer elemento */
    int tamaño;
} Deque;

static int lleno(const Deque *d)  { return d->tamaño == CAP; }
static int vacio(const Deque *d)  { return d->tamaño == 0; }

void push_back(Deque *d, int val) {
    if (lleno(d)) { fprintf(stderr, "Deque lleno\n"); return; }
    int pos = (d->frente + d->tamaño) % CAP;
    d->datos[pos] = val;
    d->tamaño++;
}

void push_front(Deque *d, int val) {
    if (lleno(d)) { fprintf(stderr, "Deque lleno\n"); return; }
    d->frente = (d->frente - 1 + CAP) % CAP;
    d->datos[d->frente] = val;
    d->tamaño++;
}

int pop_front(Deque *d) {
    if (vacio(d)) { fprintf(stderr, "Deque vacío\n"); return -1; }
    int val = d->datos[d->frente];
    d->frente = (d->frente + 1) % CAP;
    d->tamaño--;
    return val;
}

int pop_back(Deque *d) {
    if (vacio(d)) { fprintf(stderr, "Deque vacío\n"); return -1; }
    int pos = (d->frente + d->tamaño - 1) % CAP;
    d->tamaño--;
    return d->datos[pos];
}

void imprimir(const Deque *d) {
    printf("Deque [%d]: ", d->tamaño);
    for (int i = 0; i < d->tamaño; i++)
        printf("%d ", d->datos[(d->frente + i) % CAP]);
    printf("\n");
}

int main(void) {
    Deque d = {.frente = 0, .tamaño = 0};

    push_back(&d,  10); imprimir(&d);
    push_back(&d,  20); imprimir(&d);
    push_front(&d,  5); imprimir(&d);
    push_back(&d,  30); imprimir(&d);
    push_front(&d,  1); imprimir(&d);

    printf("\npop_front() = %d\n", pop_front(&d)); imprimir(&d);
    printf("pop_back()  = %d\n", pop_back(&d));  imprimir(&d);
    printf("pop_front() = %d\n", pop_front(&d)); imprimir(&d);

    return 0;
}

Resultado esperado

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Deque [1]: 10 
Deque [2]: 10 20 
Deque [3]: 5 10 20 
Deque [4]: 5 10 20 30 
Deque [5]: 1 5 10 20 30 

pop_front() = 1
Deque [4]: 5 10 20 30 
pop_back()  = 30
Deque [3]: 5 10 20 
pop_front() = 5
Deque [2]: 10 20 

Errores frecuentes

No aplicar el módulo CAP al calcular frente - 1: en C, el operador % con números negativos puede dar resultado negativo; hay que usar (frente - 1 + CAP) % CAP.
Confundir el índice del fondo con frente + tamaño: el fondo está en (frente + tamaño - 1) % CAP, ya que frente + tamaño apunta a la primera posición libre.
No verificar si el deque está lleno antes de push_front o push_back: insertar cuando tamaño == CAP sobrescribe elementos existentes.
Inicializar frente a un valor distinto de 0: para simplificar, frente = 0 y tamaño = 0 es la inicialización estándar.

Aplicación práctica

El deque se usa en la implementación de algoritmos de ventana deslizante (máximo/mínimo en ventana de tamaño k), en la planificación de tareas (inserción y extracción en ambos extremos), como estructura base de la búsqueda en anchura (BFS) bidireccional y en simuladores de colas con prioridad en los extremos.

Siguiente ejercicio recomendado

Práctica guiada y libro completo

Si quieres una ruta completa con progresión real de dificultad:

FAQ

¿Cuál es la diferencia entre un deque y una cola normal?

Una cola (FIFO) solo permite insertar por el fondo y extraer por el frente. Un deque permite insertar y extraer por ambos extremos. El deque es un superconjunto: puede simular tanto una cola (usando solo push_back y pop_front) como una pila (usando solo push_back y pop_back).

¿Por qué usar un array circular en lugar de una lista enlazada?

El array circular garantiza O(1) para todas las operaciones sin asignación dinámica de memoria, lo que lo hace más rápido y con mejor localidad de caché que una lista enlazada. La lista enlazada es preferible si la capacidad es desconocida o ilimitada.

¿Qué complejidad temporal tienen las cuatro operaciones del deque?

Las cuatro operaciones (push_front, push_back, pop_front, pop_back) son O(1) con el array circular. La operación imprimir es O(n) porque recorre todos los elementos.