Queue, Deque, ArrayDeque y PriorityQueue

Queue: la abstracción FIFO

La interfaz Queue<E> representa una cola con política First-In-First-Out (FIFO): los elementos salen en el orden en que entraron.

Métodos principales, dos variantes:

| Operación | Lanza excepción | Devuelve especial | |-----------|-----------------|-------------------| | Insertar al final | add(e) | offer(e) a boolean | | Extraer del frente | remove() | poll() a null si vacía | | Consultar frente sin extraer | element() | peek() a null si vacía |

Usa las variantes sin excepción (offer/poll/peek) cuando la cola puede estar vacía; las otras (add/remove/element) cuando un fallo debe ser un error.

Queue<String> cola = new LinkedList<>();
cola.offer("primero");
cola.offer("segundo");
cola.offer("tercero");

String frente = cola.peek(); // "primero" (sin extraer)
String saliendo = cola.poll(); // "primero" (extrae)
System.out.println(cola); // [segundo, tercero]

Deque: doble extremo

Deque<E> (Double-Ended Queue) extiende Queue permitiendo operaciones tanto en el frente como en el final. Es la interfaz más versátil: puede usarse como cola FIFO y como pila LIFO.

Métodos clave (con ambas variantes, exception y special):

| Operación | Exception | Special | |-----------|-----------|---------| | Insertar frente | addFirst | offerFirst | | Insertar final | addLast | offerLast | | Extraer frente | removeFirst | pollFirst | | Extraer final | removeLast | pollLast | | Consultar frente | getFirst | peekFirst | | Consultar final | getLast | peekLast |

Y operaciones tipo stack:

| Operación | Método | |-----------|--------| | Push | push(e) (equivalente a addFirst) | | Pop | pop() (equivalente a removeFirst) | | Peek | peek() |

ArrayDeque: la implementación por defecto

ArrayDeque<E> es la implementación recomendada de Deque. Usa un array circular interno, no tiene capacidad máxima (crece) y es muy rápida:

Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(1);
deque.offerLast(2);
deque.offerFirst(0);
// Estado: [0, 1, 2]

deque.pollFirst(); // 0
deque.pollLast(); // 2
// Estado: [1]

Ventajas sobre alternativas:

• Más rápida que LinkedList para operaciones de cola/deque (menos GC, caché-friendly).
• Thread-safe: no, usa ConcurrentLinkedDeque o similar.
• No permite null: lanza NullPointerException.

ArrayDeque como pila (sustituto de Stack)

Deque<String> pila = new ArrayDeque<>();
pila.push("a");
pila.push("b");
pila.push("c");
System.out.println(pila.peek()); // "c"
System.out.println(pila.pop()); // "c"
System.out.println(pila); // [b, a]

La clase java.util.Stack es legacy (hereda de Vector, sincronizada, lenta). Nunca la uses en código nuevo; usa ArrayDeque como pila.

LinkedList como Queue/Deque

LinkedList implementa Deque también, pero su rendimiento suele ser peor que ArrayDeque:

• Cada nodo consume más memoria (punteros siguiente/anterior).
• Peor localidad de caché.
• Más rotación de GC.

Úsala como deque solo si ya necesitas LinkedList por otros motivos (inserción/eliminación frecuente en posiciones arbitrarias, que es su único punto fuerte).

PriorityQueue: cola de prioridad

PriorityQueue<E> es una cola donde los elementos se extraen según un criterio de prioridad, no por orden de inserción. Internamente usa un heap binario.

PriorityQueue<Integer> cola = new PriorityQueue<>(); // orden natural: menor primero
cola.offer(5);
cola.offer(1);
cola.offer(3);
cola.offer(2);
cola.offer(4);

while (!cola.isEmpty()) {
    System.out.println(cola.poll()); // 1, 2, 3, 4, 5 (ordenados)
}

Con Comparator

Para ordenar por otro criterio o en orden descendente, pasa un Comparator:

// Cola que extrae MAYOR primero
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Prioridad personalizada por campo
record Tarea(String nombre, int prioridad) {}
PriorityQueue<Tarea> cola = new PriorityQueue<>(
    Comparator.comparingInt(Tarea::prioridad).reversed()
);
cola.offer(new Tarea("limpiar", 2));
cola.offer(new Tarea("urgente", 10));
cola.offer(new Tarea("normal", 5));

cola.poll(); // Tarea[nombre=urgente, prioridad=10]

Características importantes

• No es ordenada globalmente: iterar PriorityQueue NO da el orden de prioridad. Solo poll extrae en orden.
• No es Sequenced: no implementa SequencedCollection.
• Rendimiento: offer y poll son O(log n), peek es O(1).

Casos de uso típicos

• Planificadores / schedulers: tareas con deadline, prioridad.
• Algoritmos de grafos: Dijkstra, A*.
• Merge de streams ordenados: merge-k-sorted.
• Top-K problems: conservar los N elementos más grandes/pequeños.

// Top-3 salarios más altos
PriorityQueue<Double> top3 = new PriorityQueue<>(); // min-heap
for (Empleado e : empleados) {
    top3.offer(e.salario());
    if (top3.size() > 3) top3.poll();
}
// top3 contiene los 3 salarios más altos (en orden min-heap)

Métodos uniformes con SequencedCollection (Java 21+)

Desde Java 21, Deque implementa SequencedCollection, unificando API:

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("a");
deque.addLast("z");
String primero = deque.getFirst();
String ultimo = deque.getLast();
deque.reversed().forEach(System.out::println);

Resumen comparativo

| Clase | Interfaces | FIFO | LIFO | Prioridad | Thread-safe | |-------|-----------|:----:|:----:|:---------:|:-----------:| | ArrayDeque | Deque | ✅ | ✅ | | ❌ | | LinkedList | Deque, List | ✅ | ✅ | | ❌ | | PriorityQueue | Queue | ❌ | | ✅ | ❌ | | ConcurrentLinkedDeque | Deque | ✅ | ✅ | | ✅ | | ArrayBlockingQueue | BlockingQueue | ✅ | | | ✅ | | LinkedBlockingDeque | BlockingDeque | ✅ | ✅ | | ✅ | | PriorityBlockingQueue | BlockingQueue | | | ✅ | ✅ |

Las variantes "Blocking" del paquete java.util.concurrent añaden bloqueo en operaciones cuando la cola está llena o vacía, para uso en productor-consumidor concurrente.

Elección rápida

• Cola FIFO normal a ArrayDeque (más rápida) o LinkedList (si necesitas List).
• Pila LIFO a ArrayDeque (push/pop/peek).
• Por prioridad a PriorityQueue con Comparator.
• Cola concurrente a ConcurrentLinkedDeque o ArrayBlockingQueue.
• Cola con tamaño máximo a ArrayBlockingQueue.

ArrayDeque cubre el 90% de los casos prácticos. Úsala como deque, pila, cola FIFO y olvida Stack, Vector y LinkedList para esos usos.