Colas en Data Structures & Algorithms — Guía

Completa en Java
Basado en Goodrich, Tamassia & Goldwasser — Data Structures & Algorithms in Java

Resumen Ejecutivo
Las colas (queues) son estructuras de datos fundamentales en el análisis de algoritmos. Definen
el orden en que los elementos se procesan y, dependiendo del tipo de cola utilizado, permiten
resolver problemas que van desde la planificación de procesos en un sistema operativo hasta la
implementación de algoritmos de búsqueda en grafos. Comprender las colas es comprender
cómo fluye la información a través de un sistema.

1. Importancia de las Colas en DSA

Una cola es una colección ordenada de elementos en la que la posición o prioridad de cada
elemento determina cuándo será procesado. No son solo un contenedor: son una política de
decisión.

¿Por qué son críticas?

Modelan el mundo real: colas de impresión, atención al cliente, solicitudes HTTP,
planificación de tareas en la CPU.
Son la base de algoritmos esenciales: BFS (Breadth-First Search) usa una cola FIFO; los
algoritmos de Dijkstra y A* usan una Priority Queue; la evaluación de expresiones usa una
pila (Stack).
Definen la complejidad temporal de los algoritmos: la elección del tipo de cola impacta
directamente en el tiempo de ejecución vs de operaciones críticas.
Son el pilar del diseño de sistemas concurrentes: los BlockingQueue de Java son
fundamentales en arquitecturas productor-consumidor.

Regla de Oro para el Análisis

Antes de elegir una cola, pregunta : ¿qué elemento debe procesarse primero y bajo qué
criterio?

Criterio de prioridad Tipo de cola recomendado

Orden de llegada Cola FIFO simple

Último en llegar Pila (Stack / LIFO)

Ambos extremos Deque (doble extremo)

 Criterio de prioridad Tipo de cola recomendado

Mayor/menor valor numérico Priority Queue (Heap)

Tiempo real de ejecución Delay Queue o TimerQueue

2. Clases de Colas — Taxonomía Completa

2.1 Cola Simple (FIFO — First In, First Out)

El primer elemento en entrar es el primero en salir. Es el modelo más intuitivo: como la fila de un
supermercado.

Operaciones fundamentales:

Operación Descripción Complejidad

enqueue(e) Agrega e al final de la cola

dequeue() Extrae y retorna el frente

first() Consulta el frente sin extraer

size() Cantidad de elementos

isEmpty() Verifica si está vacía

Qué analizar en una Cola FIFO:

¿La implementación es con array circular o con lista enlazada?

¿Existe riesgo de desbordamiento (overflow) si se usa array de tamaño fijo?
¿El orden de llegada es justo para todos los elementos (fairness)?

// Cola FIFO con ArrayDeque (implementación preferida en Java)

import [Link];
import [Link];

public class ColaFIFO {

public static void main(String[] args) {
Queue<String> cola = new ArrayDeque<>();

// Simulación de llegada de clientes

[Link]("Cliente-A"); // enqueue
[Link]("Cliente-B");
[Link]("Cliente-C");

[Link]("Atendiendo: " + [Link]()); // Cliente-A

[Link]("Siguiente: " + [Link]()); // Cliente-B (sin extraer)
[Link]("Atendiendo: " + [Link]()); // Cliente-B

// Cola: [Cliente-C]
 }
}

2.2 Pila (Stack — LIFO: Last In, First Out)

El último elemento en entrar es el primero en salir. Como una pila de platos: solo se accede al
plato del tope.

Operaciones fundamentales:

Operación Descripción Complejidad

push(e) Coloca e en el tope amortizado

pop() Extrae y retorna el tope amortizado

top() / peek() Consulta el tope sin extraer

isEmpty() Verifica si está vacía

Qué analizar en una Pila :

¿Existe riesgo de StackOverflowError en recursión profunda?

¿Se necesita simular recursión de forma iterativa con una pila explícita?
¿El comportamiento LIFO modela correctamente el problema (ej. paréntesis balanceados,
historial de navegación)?

import [Link];
import [Link];

public class ValidadorParentesis {

// EJEMPLO DE MEDIANA COMPLEJIDAD
// Verifica si una expresión tiene paréntesis, corchetes y llaves balanceados.
// Usa una pila: cada apertura se "recuerda" y cada cierre debe coincidir con el últ
public static boolean esValida(String expresion) {
Deque<Character> pila = new ArrayDeque<>();

for (char c : [Link]()) {

if (c == '(' || c == '[' || c == '{') {
[Link](c); // Apila la apertura
} else if (c == ')' || c == ']' || c == '}') {
if ([Link]()) return false; // Cierre sin apertura previa
char tope = [Link]();
// Verifica que el cierre corresponda a la última apertura
if ((c == ')' && tope != '(') ||
(c == ']' && tope != '[') ||
(c == '}' && tope != '{')) {
return false;
}
}
}
return [Link](); // Debe estar vacía si todo está balanceado
}
 public static void main(String[] args) {
[Link](esValida("{[()]}")); // true
[Link](esValida("{[(])}")); // false — cierre incorrecto
[Link](esValida("((())")); // false — falta cerrar
}
}

2.3 Deque (Double-Ended Queue — Cola de Doble Extremo)

Permite insertar y extraer por ambos extremos (frente y final). Es la más flexible de las colas
básicas.

Operaciones fundamentales:

Operación Descripción Complejidad

addFirst(e) Inserta al frente

addLast(e) Inserta al final

removeFirst() Extrae del frente

removeLast() Extrae del final

peekFirst() Consulta el frente

peekLast() Consulta el final

Qué analizar en un Deque:

¿El problema requiere acceso por ambos extremos simultáneamente?

¿Se puede usar como pila (solo addFirst/removeFirst) o cola (solo addLast/removeFirst)?
¿La implementación subyacente es con array circular o lista doblemente enlazada?

// EJEMPLO DE MEDIANA COMPLEJIDAD — Ventana deslizante con Deque

// Dado un arreglo y un tamaño k, encuentra el máximo en cada ventana de k elementos.
// Complejidad: O(n) — cada elemento se agrega y elimina del deque a lo sumo una vez.
import [Link];
import [Link];

public class MaxVentanaDeslizante {

public static int[] maxVentana(int[] nums, int k) {
int n = [Link];
int[] resultado = new int[n - k + 1];
// El deque guarda ÍNDICES, no valores.
// Invariante: los índices en el deque corresponden a elementos en orden DECRECI
Deque<Integer> deque = new ArrayDeque<>();

for (int i = 0; i < n; i++) {

// 1. Elimina índices que ya no están en la ventana actual [i-k+1, i]
while (![Link]() && [Link]() < i - k + 1) {
[Link]();
 }
// 2. Elimina índices cuyo valor es menor que el actual (ya no pueden ser máx
while (![Link]() && nums[[Link]()] < nums[i]) {
[Link]();
}
[Link](i); // Agrega el índice actual al final

// 3. El frente del deque siempre tiene el índice del máximo de la ventana

if (i >= k - 1) {
resultado[i - k + 1] = nums[[Link]()];
}
}
return resultado;
}

public static void main(String[] args) {

int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] maximos = maxVentana(nums, k);
// Ventanas: [1,3,-1]=3, [3,-1,-3]=3, [-1,-3,5]=5, [-3,5,3]=5, [5,3,6]=6, [3,6,7]=7
for (int m : maximos) [Link](m + " "); // 3 3 5 5 6 7
}
}

2.4 Priority Queue (Cola de Prioridad)

Una Priority Queue es una colección de pares (clave, valor) donde la clave representa la
prioridad. A diferencia de FIFO, el orden de salida lo determina la prioridad, no el tiempo de
llegada.

Sus dos operaciones fundamentales son:

insert(k, v) — agrega el par (clave k, valor v) a la cola.

removeMin() — extrae y retorna el par cuya clave es la menor de todas.
Complejidad según implementación:

Implementación insert removeMin min Uso ideal

Lista desordenada Pocas extracciones

Lista ordenada Pocas inserciones

Heap binario Uso general (estándar)

Heap de Fibonacci amort. Grafos con muchas decrements

Qué analizar en una Priority Queue:

¿Se necesita min-heap (mínimo primero) o max-heap (máximo primero)?

¿Las prioridades cambian durante la ejecución? (requiere decreaseKey)
¿Se procesan elementos en tiempo real o en lote?
 ¿Es segura para hilos concurrentes? (PriorityBlockingQueue)

Caso de Estudio: Traza de operaciones (Goodrich et al.)

Se ejecuta la siguiente secuencia sobre una PQ vacía:

# Operación Contenido PQ (ordenado por clave ↑) Retorna

1 insert(5, A) (5,A) —

2 insert(4, B) (4,B) (5,A) —

3 insert(7, F) (4,B) (5,A) (7,F) —

4 insert(1, D) (1,D) (4,B) (5,A) (7,F) —

5 removeMin() (4,B) (5,A) (7,F) (1, D)

6 insert(3, J) (3,J) (4,B) (5,A) (7,F) —

7 insert(6, L) (3,J) (4,B) (5,A) (6,L) (7,F) —

8 removeMin() (4,B) (5,A) (6,L) (7,F) (3, J)

12 insert(2, H) (2,H) (6,L) (7,F) (8,G) —

13 removeMin() (6,L) (7,F) (8,G) (2, H) ← ¡caso clave!

Regla clave: La PQ NO respeta el orden de inserción. El elemento (2,H) se insertó tarde

pero sale antes que (6,L), (7,F) y (8,G) porque su clave es menor.

import [Link];

public class EjemploPriorityQueue {

public static void main(String[] args) {
// Min-heap por defecto en Java (mínimo primero)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

[Link](new int[]{5, 'A'});

[Link](new int[]{4, 'B'});
[Link](new int[]{7, 'F'});
[Link](new int[]{1, 'D'});

int[] min = [Link](); // Extrae (1, D)

[Link]("removeMin → clave=%d, valor=%c%n", min[0], (char) min[1]);
}
}

3. Análisis Profundo: Priority Queue con Heap Binario

El heap binario es la implementación estándar de la Priority Queue. Es un árbol binario completo
almacenado en un array que cumple la propiedad de heap: cada nodo tiene una clave menor o
igual que la de sus hijos.
Estructura en memoria (array)
Para un nodo en la posición i (índice base 1):

Padre: posición
Hijo izquierdo: posición
Hijo derecho: posición

Operaciones clave
insert — Up-Heap Bubbling (burbuja hacia arriba):

1. Agrega el nuevo elemento al final del array (mantiene la completitud).

2. Compara con su padre: si viola la propiedad de heap, intercambia (swap).
3. Repite hasta que el elemento esté en su posición correcta.
4. En el peor caso sube hasta la raíz: comparaciones.
removeMin — Down-Heap Bubbling (burbuja hacia abajo):

1. Extrae la raíz (el mínimo).

2. Mueve el último elemento a la raíz (mantiene la completitud).
3. Compara con sus hijos: intercambia con el hijo menor si viola la propiedad.
4. Repite hasta llegar a una hoja: comparaciones.

4. Ejemplo de Alta Complejidad — Stack Implementado con Priority Queue

Este ejemplo clásico de Goodrich et al. demuestra la versatilidad de los ADTs: implementar una
pila (LIFO) usando únicamente una Priority Queue mínima.

El problema conceptual
Stack y Priority Queue tienen políticas de salida opuestas:

Aspecto Stack (pila) Priority Queue

Política de salida LIFO — sale el último en entrar Sale la menor clave

¿Qué elemento sale primero? El más reciente El de menor clave

Solución: Claves negativas decrecientes

Invariante: el elemento insertado más recientemente debe tener siempre la clave con mayor
prioridad (mínima) en la cola.

Mecanismo: se usa una variable timestamp que empieza en 0 y se decrementa con cada push. Así,
el último elemento siempre tiene la clave más negativa → siempre sale primero →
comportamiento LIFO.
Análisis comparativo de soluciones:

Aspecto Solución A (claves negativas) Solución B (claves positivas) Mejor

Variable extra int timestamp = 0 (decrementa) int count = 0 (incrementa) Igual

Clave 1° push -1 0 —

Operación removeMax() (requiere max-

removeMin() estándar Sol. A
extracción heap)

PQ requerida Min-PQ (la más común) Max-PQ (menos frecuente) Sol. A

[Link] Sol. A
Compatibilidad Java Requiere implementación propia
nativo

Complejidad push Igual

Complejidad pop Igual

Recomendación de expertos: La Solución A es preferida porque usa el Priority Queue

mínimo estándar, disponible directamente en Java, Python y C++. La Solución B requiere
un max-heap o invertir la comparación, añadiendo complejidad innecesaria.

Traza de ejecución
Operación timestamp PQ interna (clave, valor) Resultado

push("A") -1 (-1, A) A ingresa con clave -1

push("B") -2 (-2, B) (-1, A) B es nuevo tope

push("C") -3 (-3, C) (-2, B) (-1, A) C es nuevo tope

pop() — (-2, B) (-1, A) Extrae (-3, C) → "C" ✓ LIFO

pop() — (-1, A) Extrae (-2, B) → "B" ✓ LIFO

pop() — (vacía) Extrae (-1, A) → "A" ✓ LIFO

Implementación Java completa y documentada

import [Link];
import [Link];

/**
* Stack (LIFO) implementado sobre una Priority Queue mínima.
*
* Invariante: el elemento en el tope de la pila siempre tiene
* la clave más pequeña (más negativa) en la Priority Queue.
*
* Complejidad: push() y pop() en O(log n), top() en O(1).
*
* @param <V> tipo del valor almacenado
*/
public class StackUsingPQ<V> {
// Cada entrada es un par [clave, índice_del_valor] para poder guardar el valor V.
// Usamos un array de dos elementos: {timestamp, indiceValor}
private final PriorityQueue<long[]> pq;
private final [Link]<V> valores;
private long timestamp = 0; // ÚNICA variable entera adicional permitida

public StackUsingPQ() {
// El comparador ordena por clave (elemento [0]): min-heap
pq = new PriorityQueue<>((a, b) -> [Link](a[0], b[0]));
valores = new [Link]<>();
}

/**
* Apila un elemento en el tope. O(log n)
* Decrementa timestamp para que el nuevo elemento tenga la clave más pequeña.
*/
public void push(V value) {
timestamp--; // 0 → -1 → -2 → -3 ...
int idx = [Link]();
[Link](value);
[Link](new long[]{timestamp, idx});
// Invariante mantenida: timestamp es siempre la clave mínima actual.
}

/**
* Desapila y retorna el elemento del tope. O(log n)
* removeMin() extrae el par con la clave más negativa = el último insertado.
*/
public V pop() {
if (isEmpty()) throw new EmptyStackException();
long[] entrada = [Link](); // Extrae la clave mínima (más negativa)
return [Link]((int) entrada[1]);
}

/**
* Retorna (sin extraer) el elemento del tope. O(1)
*/
public V top() {
if (isEmpty()) throw new EmptyStackException();
long[] entrada = [Link](); // Consulta sin extraer
return [Link]((int) entrada[1]);
}

public boolean isEmpty() { return [Link](); }

public int size() { return [Link](); }

// ---- Demostración ----

public static void main(String[] args) {
StackUsingPQ<String> stack = new StackUsingPQ<>();

[Link]("A");
[Link]("B");
[Link]("C");

[Link]("top(): " + [Link]()); // C

 [Link]("pop(): " + [Link]()); // C ← LIFO
[Link]("pop(): " + [Link]()); // B ← LIFO
[Link]("pop(): " + [Link]()); // A ← LIFO
}
}

Análisis de complejidad
Método Tiempo Justificación

push(v) O(log n) Llama a [Link]() → heap sube el elemento: O(log n) comparaciones

pop() O(log n) Llama a [Link]() → heap reestructura bajando: O(log n)

top() O(1) Llama a [Link]() → la raíz del heap siempre es el mínimo

isEmpty() O(1) Solo verifica si el heap tiene elementos

size() O(1) El heap mantiene un contador interno

Espacio extra O(1) Solo la variable timestamp; la PQ ya era necesaria

Comparación con Stack nativo: Un Stack con array dinámico tiene push y pop en
amortizado, más rápido. Sin embargo, este ejercicio demuestra la versatilidad del ADT
Priority Queue: puede simular otras estructuras de datos cambiando cómo se asignan las
claves.

5. Ejemplo de Alta Complejidad — Algoritmo de Dijkstra con Priority Queue

El algoritmo de Dijkstra para caminos más cortos es el caso de uso más importante de las Priority
Queues en la práctica real.

Análisis del problema

Dado un grafo ponderado con vértices y aristas, encontrar el camino de menor costo desde
un nodo origen hasta todos los demás.

Complejidad con Priority Queue (min-heap):

— la inserción y extracción del heap domina.

Sin heap (con array): — aceptable solo para grafos densos.

Qué analiza el experto antes de implementar

1. Estructura del grafo: ¿lista de adyacencia o matriz? (lista para grafos dispersos).
2. Tipo de heap: min-heap por peso de arista.
3. Manejo de nodos ya visitados: lazy deletion vs. decrease-key.
4. Ciclos negativos: Dijkstra falla con pesos negativos (usar Bellman-Ford en ese caso).
import [Link].*;

public class Dijkstra {

/**
* Calcula la distancia mínima desde 'origen' a todos los nodos.
* Complejidad: O((V + E) log V)
*
* @param grafo Lista de adyacencia: [Link](u) = lista de {v, peso}
* @param origen Nodo de inicio (0-indexado)
* @param V Número de vértices
* @return array de distancias mínimas desde origen
*/
public static int[] dijkstra(List<List<int[]>> grafo, int origen, int V) {
int[] dist = new int[V];
[Link](dist, Integer.MAX_VALUE);
dist[origen] = 0;

// Min-heap: [distancia_acumulada, nodo]

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
[Link](new int[]{0, origen});

while (![Link]()) {
int[] actual = [Link]();
int distActual = actual[0];
int u = actual[1];

// Lazy deletion: si ya encontramos un camino mejor, ignoramos esta entrada

if (distActual > dist[u]) continue;

// Relajación de aristas adyacentes

for (int[] arista : [Link](u)) {
int v = arista[0];
int peso = arista[1];
int nuevaDist = dist[u] + peso;

if (nuevaDist < dist[v]) {

dist[v] = nuevaDist;
[Link](new int[]{nuevaDist, v}); // Inserción en heap: O(log V)
}
}
}
return dist;
}

public static void main(String[] args) {

int V = 5;
List<List<int[]>> grafo = new ArrayList<>();
for (int i = 0; i < V; i++) [Link](new ArrayList<>());

// Grafo de ejemplo (no dirigido):

// 0 --4-- 1 --1-- 2
// | | |
// 2 5 2
// | | |
// 3 --1-- 4 ------+
[Link](0).add(new int[]{1, 4}); [Link](1).add(new int[]{0, 4});
 [Link](0).add(new int[]{2, 2}); [Link](2).add(new int[]{0, 2});
[Link](1).add(new int[]{2, 1}); [Link](2).add(new int[]{1, 1});
[Link](1).add(new int[]{4, 5}); [Link](4).add(new int[]{1, 5});
[Link](2).add(new int[]{4, 2}); [Link](4).add(new int[]{2, 2});
[Link](3).add(new int[]{4, 1}); [Link](4).add(new int[]{3, 1});

int[] distancias = dijkstra(grafo, 0, V);

[Link]("Distancias desde nodo 0:");
for (int i = 0; i < V; i++) {
[Link](" nodo %d → %d%n", i, distancias[i]);
}
// nodo 0 → 0
// nodo 1 → 3 (0→2→1: 2+1=3, no 0→1: 4)
// nodo 2 → 2 (0→2: 2)
// nodo 3 → 5 (0→2→4→3: 2+2+1=5)
// nodo 4 → 4 (0→2→4: 2+2=4)
}
}

6. Mapa de Decisión: ¿Qué Cola Usar?

¿Qué elemento debe procesarse primero?

│
├── El que llegó primero (orden de llegada)
│ └── → Cola FIFO (Queue / ArrayDeque)
│
├── El que llegó último (más reciente)
│ └── → Pila Stack (Deque como pila)
│
├── Acceso por ambos extremos
│ └── → Deque (ArrayDeque / LinkedList)
│
├── El de mayor o menor prioridad numérica
│ ├── Pocas operaciones (< 100 elementos)
│ │ └── → Lista ordenada O(n) insert, O(1) removeMin
│ └── Muchas operaciones (n > 100)
│ └── → Heap binario: PriorityQueue de Java
│ ├── Min-heap (predeterminado)
│ └── Max-heap: PriorityQueue<>((a,b) -> b - a)
│
└── Entorno concurrente (multi-hilo)
├── Cola FIFO → LinkedBlockingQueue
└── Priority Queue → PriorityBlockingQueue

7. Tabla de Referencia Rápida

Tipo de
Clase Java Política insert remove peek Cuándo usar
Cola

BFS, buffer de
Cola FIFO ArrayDeque / LinkedList FIFO O(1) O(1) O(1)
mensajes
 Tipo de
Clase Java Política insert remove peek Cuándo usar
Cola

DFS, deshacer
Pila ArrayDeque (como stack) LIFO O(1) O(1) O(1)
acciones, parsing

Ventana
Deque ArrayDeque Ambos O(1) O(1) O(1) deslizante,
palíndromos

Dijkstra,
Priority Por O(log O(log
Queue
PriorityQueue clave n) n)
O(1) scheduling,
eventos

Productor-
Blocking
LinkedBlockingQueue FIFO O(1) O(1) O(1) consumidor multi-
Queue
hilo

Priority Por O(log O(log Scheduling

PriorityBlockingQueue O(1)
Blocking clave n) n) concurrente

8. Conclusión y Mejores Prácticas

1. Usa ArrayDeque sobre Stack y LinkedList para implementaciones de pila y cola FIFO en Java
moderno — es más eficiente en memoria y más rápida en caché.
2. Usa PriorityQueue con un comparador explícito para max-heaps o prioridades
personalizadas: new PriorityQueue<>((a, b) -> b - a).
3. La complejidad del heap es suficiente para la mayoría de los problemas prácticos
con hasta decenas de millones de elementos.
4. Antes de implementar, pregunta: ¿necesitas decreaseKey? Si sí, Java's PriorityQueue nativo
no lo soporta eficientemente — considera una implementación personalizada de heap de
Fibonacci.
5. Las colas no son solo almacenamiento — son decisiones de diseño que determinan la
corrección y eficiencia del algoritmo completo.

Documento generado el 8 de abril de 2026 · Basado en Goodrich, Tamassia & Goldwasser — Data
Structures & Algorithms in Java, 6ª edición