Sebastian Gomez

Apr 06, 2023

Updated: Jun 24, 2026

Estructuras de datos en Go: Deque

Las deques, o colas de doble extremo, son estructuras de datos versátiles que nos permiten insertar y eliminar elementos tanto por el frente como por la parte trasera. En este post exploraremos las principales características de esta estructura, su historia y algunos ejemplos de su uso en problemas de computación.

Nota sobre el nombre. A lo largo del post usamos deque (de "double ended queue", cola de doble extremo). Ojo con un error muy común, "dequeue" no es la estructura sino la operación de sacar un elemento de una cola. La estructura se llama deque y el tipo que implementamos se llama Deque.

Que es una deque

Una deque es un tipo de estructura de datos que permite insertar y eliminar elementos tanto por el frente como por la parte trasera. Esto la hace similar a una cola o a una pila, pero con la flexibilidad adicional de poder agregar o quitar elementos en ambos extremos. Por eso resulta tan útil en muchos algoritmos y situaciones donde necesitamos operaciones de inserción y eliminación eficientes en los dos extremos.

Un poco de historia

El concepto de deque se popularizó en la literatura de algoritmos a mediados del siglo XX, cuando las primeras estructuras de datos lineales empezaron a formalizarse. Donald Knuth la describe y analiza en The Art of Computer Programming, donde aparece como una generalización natural de la cola y la pila.

Desde entonces, la deque se ha usado ampliamente en distintos ámbitos de la informatica, desde la programación de sistemas hasta los algoritmos de grafos y el procesamiento de datos en tiempo real.

Ejemplo de código en Go

Veamos una implementación de una deque en Go. Para mantenerla clara y correcta, vamos a respaldarla con un slice. Cada operación se apoya en las funciones nativas de slices de Go, así que es fácil de leer y, sobre todo, corre sin sorpresas.

Nota. El código original de este post intentaba mezclar un buffer circular de tamaño fijo con un slice que crecía con append. Esos dos modelos no encajan y el programa terminaba con un panic de tipo index out of range. Aquí elegimos un único modelo, respaldar la deque con un slice, que es más simple y siempre consistente.

package main

import (
	"errors"
	"fmt"
)

// Deque es una cola de doble extremo respaldada por un slice.
type Deque struct {
	items []int
}

// NewDeque crea una nueva deque vacia y devuelve un puntero a ella.
func NewDeque() *Deque {
	return &Deque{items: make([]int, 0)}
}

// Size devuelve el numero de elementos en la deque.
func (d *Deque) Size() int {
	return len(d.items)
}

// IsEmpty indica si la deque no tiene elementos.
func (d *Deque) IsEmpty() bool {
	return len(d.items) == 0
}

// PushFront inserta un elemento en el frente de la deque.
func (d *Deque) PushFront(item int) {
	d.items = append([]int{item}, d.items...)
}

// PushBack inserta un elemento en la parte trasera de la deque.
func (d *Deque) PushBack(item int) {
	d.items = append(d.items, item)
}

// PopFront elimina y devuelve el elemento del frente.
func (d *Deque) PopFront() (int, error) {
	if d.IsEmpty() {
		return 0, errors.New("la deque esta vacia")
	}
	item := d.items[0]
	d.items = d.items[1:]
	return item, nil
}

// PopBack elimina y devuelve el elemento de la parte trasera.
func (d *Deque) PopBack() (int, error) {
	if d.IsEmpty() {
		return 0, errors.New("la deque esta vacia")
	}
	last := len(d.items) - 1
	item := d.items[last]
	d.items = d.items[:last]
	return item, nil
}

func main() {
	deque := NewDeque()

	// Insertar elementos en el frente y en la parte trasera de la deque.
	deque.PushFront(1)
	deque.PushBack(2)
	deque.PushBack(3)
	deque.PushFront(0)

	// Imprimir los elementos de la deque.
	fmt.Println("Elementos en la deque:")
	n := deque.Size()
	for i := 0; i < n; i++ {
		item, err := deque.PopFront()
		if err != nil {
			break
		}
		fmt.Println(item)
	}
}

Fíjate en un detalle importante del main. Antes de iterar tomamos una instantánea del tamaño con n:= deque.Size(). Si usáramos directamente deque.Size() en la condición del for, cada PopFront reduciría el tamaño dentro del bucle y solo recorreríamos la mitad de los elementos. Tomar n una sola vez nos evita ese clásico error.

Si ejecutas el programa, la salida será:

Elementos en la deque:
0
1
2
3

Nota sobre rendimiento. PushFront y PopFront con esta implementación basada en slices desplazan elementos, así que son O(n). Es perfecto para aprender y para volúmenes pequeños. Si necesitas las cuatro operaciones en O(1) amortizado, lo habitual es usar un buffer circular con índices head y tail y redimensionado por duplicación, o una lista doblemente enlazada con container/list de la librería estándar.

Ejemplos de uso de deques

Las deques son útiles en una gran variedad de problemas de computación. Estos son algunos de los usos más comunes:

• Cache LRU: podemos implementar una cache de tamaño limitado donde, al alcanzar el límite, se eliminan los elementos usados menos recientemente por un extremo mientras se agregan los nuevos por el otro.
• Procesamiento de ventanas deslizantes: en problemas como el máximo de una ventana deslizante, una deque monótona nos permite mantener candidatos y descartar los que ya no sirven en tiempo constante amortizado.
• Recorridos de grafos y árboles: una deque puede servir como cola en una búsqueda en anchura (BFS) o como pila en una búsqueda en profundidad (DFS), usando un extremo u otro según convenga.
• Edición de texto y deshacer o rehacer: podemos modelar un historial de operaciones donde se insertan y eliminan elementos por ambos extremos.

Estos son solo algunos ejemplos; la versatilidad de las deques las hace aplicables a muchos otros problemas de computación.

Conclusión

En resumen, una deque es una estructura de datos útil y versátil que podemos usar en muchos problemas de computación. Esperamos que esta introducción te haya dado una buena idea de qué son las deques y cómo implementarlas en Go. Si tienes preguntas o comentarios, no dudes en dejarlos a continuación.

Ejercicios para practicar

A continuación te dejo unos ejercicios para que practiques la estructura Deque en Go. Para que sea un buen reto de Go moderno, te propongo implementarlos con genericos, de modo que tu deque funcione con cualquier tipo (Deque[T any]) en lugar de quedar atada a int. Cuando termines, envía tu solución como un Pull request a este repositorio: Go Para Principiantes.

1. Implementa una función NewDeque[T any]() que cree una nueva deque vacía y devuelva un puntero a ella.
2. Implementa un método Size() int que devuelva el número de elementos en la deque.
3. Implementa un método IsEmpty() bool que devuelva verdadero si la deque está vacía y falso en caso contrario.
4. Implementa un método PushFront(value T) que añada un elemento al frente de la deque.
5. Implementa un método PushBack(value T) que añada un elemento al final de la deque.
6. Implementa un método PopFront() (T, error) que elimine y devuelva el elemento del frente. Si la deque está vacía, devuelve un error.
7. Implementa un método PopBack() (T, error) que elimine y devuelva el elemento del final. Si la deque está vacía, devuelve un error.
8. Implementa un método Front() (T, error) que devuelva el elemento del frente sin eliminarlo. Si la deque está vacía, devuelve un error.
9. Implementa un método Back() (T, error) que devuelva el elemento del final sin eliminarlo. Si la deque está vacía, devuelve un error.
10. Escribe un programa que use todas las funciones anteriores para realizar diversas operaciones con deques, como añadir y eliminar elementos, comprobar si está vacía y obtener el tamaño.

Pista. Los genericos en Go llegaron en la versión 1.18. Si declaras type Deque[T any] struct { items []T }, todos los métodos del ejemplo anterior se adaptan casi sin cambios, solo reemplaza int por el parámetro de tipo T.

Resumen en 3 puntos

1. Una deque es una cola de doble extremo que permite insertar y eliminar elementos por ambos extremos; no la confundas con "dequeue", que es la operación de extraer de una cola.
2. La implementación más sencilla y siempre correcta en Go es respaldarla con un slice; para O(1) amortizado en ambos extremos conviene un buffer circular o container/list.
3. Las deques brillan en cache LRU, ventanas deslizantes, recorridos de grafos (BFS y DFS) e historiales de edición.

Eso es todo, espero que este post te sea de utilidad y lo puedas aplicar a algún proyecto que tengas en mente. Déjame un comentario si te sirvió, si quieres añadir alguna opinión o si tienes alguna duda. Y recuerda que, si te gustó, también puedes compartirlo usando los links a las redes sociales aquí abajo. Buena suerte y a seguir programando.