Java ArrayDeque

ArrayDeque<E> es un array circular que crece bajo demanda. Implementa tanto Queue<E> como Deque<E>, por lo que puede desempeñar el papel de cola FIFO, pila LIFO o cola de doble extremo sin cambios de código. El Javadoc de Stack recomienda usar Deque en lugar de la clase heredada; el Javadoc de Deque añade la recomendación práctica de que ArrayDeque debería ser tu implementación predeterminada. Casi siempre es más rápido que LinkedList, más compacto en memoria, y la opción preferida de la biblioteca estándar una vez que dejas de necesitar la interfaz List.

Por qué un array circular

Una "cola basada en array" clásica presenta un problema: tras algunos ciclos de agregar al final y eliminar del principio, el array se llena por el extremo final mientras se acumulan posiciones vacías por el extremo inicial. Una solución ingenua sería desplazar todo hacia la izquierda en cada eliminación — O(n) por operación, arruinando el rendimiento.

El truco del array circular lo resuelve. La clase mantiene dos índices, head y tail, y los deja dar la vuelta:

slots:   [ . . . D E F G H A B C ]
                         ^head     ^... wraps to slot 0 ... ^tail

addFirst decrementa head, addLast incrementa tail, ambos módulo la longitud del array. removeFirst y removeLast hacen lo contrario. Cada operación es O(1); el único coste es duplicar el array de respaldo cuando head colisionaría con tail, lo cual se amortiza.

El resultado: sin asignación de nodos por elemento, sin seguimiento de punteros, acceso eficiente para la caché. Esa es la razón técnica por la que ArrayDeque suele ser la opción más rápida para cargas de trabajo de cola y pila.

Repaso de la interfaz Deque

Un Deque tiene dos extremos. Cada operación viene en tres variantes:

Además de eso, los sinónimos de Queue y pila se mapean al extremo de la cabeza:

Así que Deque es una sola interfaz que expone una cola y una pila al mismo tiempo, dependiendo de cómo se llame al extremo de la cabeza. Cubrimos estos mapeos en los capítulos de Queue y Stack; Deque es donde se unen.

Qué añade ArrayDeque por encima

En la práctica, muy poco en términos de API — ese es el punto. La clase expone el contrato Deque fielmente: los dos extremos, los tres estilos de error por operación, y un clear(), iterator(), descendingIterator(), contains, size, isEmpty. La iteración con el iterador estándar va de cabeza a cola; descendingIterator es la forma económica de recorrer de cola a cabeza sin invertir.

Los constructores reflejan a ArrayList:

Deque<String> a = new ArrayDeque<>();          // initial capacity 16
Deque<String> b = new ArrayDeque<>(1_000);     // pre-sized
Deque<String> c = new ArrayDeque<>(other);     // from any Collection (head = first iter element)

Pre-dimensiona cuando conoces la carga de trabajo. El valor predeterminado de 16 se redondea al siguiente potencia de dos, y el crecimiento duplica el array — por lo que un millón de llamadas offerLast desde una deque de tamaño predeterminado desencadena unas 16 operaciones de crecimiento y copia.

Las reglas: sin nulos, no hilo-seguro, fail-fast

Tres reglas que debes interiorizar:

1. ArrayDeque no permite elementos null. Cada inserción lanza NullPointerException. Así, que pollFirst() devuelva null para una deque vacía sigue siendo inequívoco.
2. No es hilo-seguro. Dos hilos que muten el mismo ArrayDeque lo corromperán. Para uso concurrente, mira ConcurrentLinkedDeque (sin bloqueos, sin límite) o LinkedBlockingDeque (acotado, con bloqueo).
3. Iteración fail-fast. Modificar la deque fuera del iterador mientras se itera lanza ConcurrentModificationException. Usa Iterator.remove() o removeIf para mutación segura.

Cuándo elegir ArrayDeque sobre alternativas

El flujo de decisión:

• ¿Necesitas una Queue? → ArrayDeque. Predeterminado.
• ¿Necesitas una pila? → ArrayDeque. Predeterminado. Usa push / pop / peek.
• ¿Necesitas un Deque? → ArrayDeque. Predeterminado.
• ¿Necesitas semántica tanto de Deque como de List en el mismo objeto? → LinkedList. Poco frecuente.
• ¿Necesitas un orden de prioridad? → PriorityQueue. Abstracción diferente.
• ¿Necesitas acceso concurrente? → ConcurrentLinkedDeque (sin límite) o LinkedBlockingDeque (acotado). La elección correcta depende de si necesitas contrapresión.

El Javadoc expresa la recomendación en texto claro: "Esta clase probablemente sea más rápida que Stack cuando se usa como pila, y más rápida que LinkedList cuando se usa como cola." Eso viene directamente de los autores del JDK; merece tomarse al pie de la letra.

Un ejemplo práctico: cola, pila, deque, ventana deslizante

El programa a continuación usa una instancia de ArrayDeque como cola FIFO, otra como pila LIFO, y una tercera como almacenamiento detrás de un máximo de ventana deslizante — un problema clásico donde ArrayDeque es la respuesta del libro de texto porque se necesita mutación barata en ambos extremos.

Lo que puedes extraer de esta ejecución:

• Las secciones 1 y 2 son la misma clase haciendo dos trabajos llamando a métodos diferentes. Cola FIFO: offerLast / pollFirst. Pila LIFO: push / pop. No hay una clase separada que aprender.
• descendingIterator() es el recorrido inverso económico — útil cuando has construido una deque como pila y quieres imprimirla de abajo hacia arriba.
• La función de ventana deslizante usa ambos extremos en el mismo bucle — pollFirst para descartar los índices que quedaron fuera de la ventana, pollLast para mantener una pila monotónica decreciente, peekFirst para leer el máximo actual. Ese acceso de doble extremo es la razón de existir de ArrayDeque; intentar hacer esto con un ArrayList sería cuadrático.

Qué sigue

Has visto cómo ArrayDeque implementa ambos extremos de la historia cola/pila. La interfaz que ha estado implementando todo este tiempo merece su propio capítulo — Deque es el contrato que une todo lo que hemos cubierto sobre las colecciones tipo cola. Lo retomamos en la próxima sesión.

Práctica