Colecciones Java: interfaces Queue y Deque

Java Collections Framework es un marco fundamental y esencial. Las Colas y Deques están diseñadas para contener elementos antes del procesamiento en estilos FIFO o LIFO.

Introducción

El Java Collections Framework es un marco fundamental y esencial que cualquier desarrollador de Java fuerte debe conocer como la palma de su mano.

Una Colección en Java se define como un grupo o colección de objetos individuales que actúan como un solo objeto.

Hay muchas clases de colección en Java y todas ellas amplían las interfaces java.util.Collection y java.util.Map. Estas clases en su mayoría ofrecen diferentes formas de formular una colección de objetos dentro de uno solo.

Java Collections es un marco que proporciona numerosas operaciones sobre una colección: búsqueda, clasificación, inserción, manipulación, eliminación, etc.

Esta es la cuarta y última parte de una serie de artículos sobre Java Collections:

Cola

Comencemos este último artículo de la serie con la interfaz java.util.Queue.

Principio

En primer lugar, ¿para qué sirve? La Cola está diseñada para mantener elementos antes de su procesamiento . Algunos pueden tener una capacidad fija, lo que significa que solo pueden contener hasta un cierto número de elementos.

Entonces, la idea es empujar algunos elementos a una ‘Cola’ y luego recuperarlos. En general, las colas devuelven elementos que respetan el patrón First-In First-Out (FIFO), lo que significa que el elemento más antiguo de la cola se devuelve primero, luego el más antiguo después de eso, etc.

Puedes pensar en FIFO como una fila frente a una tienda. El primero en pararse en la fila es el primero en entrar.

Pero puede haber otras implementaciones que respeten el patrón Last-In First-Out (LIFO), o incluso respondan a algún tipo de sistema de prioridad (por ejemplo, usando Comparator).

Puedes pensar en LIFO como una pila de monedas. El último en colocarse en la parte superior de la pila es el primero en retirarse.

¡Exploremos ahora las funciones de la interfaz Queue!

Adición de un elemento

Comenzaremos agregando un elemento a una Cola. Primero, vamos a crear una instancia usando la implementación ArrayDeque, que también implementa la interfaz Deque que veremos más adelante:

1
Queue<Integer> queue = new ArrayDeque<>();

Para añadir un elemento en esta Cola, tenemos dos posibilidades: el método add() o el método offer().

Comencemos con el primero:

1
queue.add(3);

Y con este último:

1
queue.offer(4);

Ambos devuelven un valor booleano que indica si el elemento fue añadido a la Cola o no, según su capacidad (si aplica). ¿Cuál es la diferencia entre ambos métodos entonces?

Bueno, el primero de hecho nunca devolverá falso, sino que arrojará una Excepción al agregar un elemento a una Cola completa. Por otro lado, el segundo devolverá falso en tales casos.

En lugar de ArrayDeque, que no tiene límites, usemos LinkedBlockingQueue, a la que se le puede asignar una capacidad:

1
Queue<Integer> queue = new LinkedBlockingQueue<>(1);

Aquí, hemos instanciado una cola que puede contener un máximo de un elemento a la vez. Por lo tanto, no podemos usar el método add() dos veces consecutivas sin tener una excepción:

1
2
queue.add(3);
queue.add(4);

Intentar agregar estos dos elementos dará como resultado:

1
2
java.lang.IllegalStateException: Queue full
    at java.base/java.util.AbstractQueue.add(AbstractQueue.java:98)

Por otro lado, usar el método oferta() en su lugar no hará nada y devolverá falso como resultado.

Recuperación de un elemento

Como se indicó anteriormente, una Cola generalmente respeta FIFO, lo que significa que devolverá primero el primer elemento ingresado, si estamos recuperando uno.

La interfaz ofrece algunos métodos para recuperar elementos. Dos de ellos, remove() y poll(), eliminan el elemento antes de devolverlo. Los otros dos, element() y peek() solo lo devuelven pero no lo eliminan.

Los métodos remove() y element() generarán una excepción cuando se les llame en una Cola vacía:

1
2
3
4
5
6
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(3);
queue.offer(4);

queue.poll();
queue.peek();

Aquí, reuniremos los elementos 3 y 4, pero la primera vez se eliminará el elemento (a través de poll()), y la segunda vez no (a través de peek()), dejando nuestra cola con el elemento 4 en ella.

Usar remove() y element() en lugar de poll() y peek(), respectivamente, habría tenido los mismos resultados, ya que la cola nunca está vacía en nuestro caso.

Iterando sobre Elementos

Además de los bucles while y for indexados, la interfaz Queue implementa Iterable y proporciona un Iterator, por lo que es elegible para el bucle for-each:

1
2
3
for (Integer element: queue) {
    System.out.println(element);
}

Ese bucle imprimiría cada elemento de la cola en la consola.

Desde Java 8, por supuesto, existe la posibilidad de llamar al método forEach(), pasando una Referencia del método:

1
queue.forEach(System.out::println);

Esto logra el mismo resultado que el bucle anterior.

Si desea leer más sobre Interfaz iterable en Java, ¡lo tenemos cubierto!

Implementaciones

Ahora bien, ¿cuáles son las clases que implementan la interfaz Queue? Hay varias implementaciones de la interfaz, aunque estas son realmente las más relevantes:

  • LinkedList: Aunque se sabe principalmente que es una implementación de Lista, esta clase también implementa la interfaz Queue. Esta implementación funciona vinculando sus elementos y recorriendo esa cadena al iterar o buscar elementos.
  • ArrayDeque: una implementación de Queue y Deque. Está respaldado por una matriz, que se puede aumentar cuando la cantidad de elementos aumenta por encima de su capacidad actual.
  • DelayQueue: solo puede contener elementos que implementen la interfaz Delayed, elementos que se activan después de cierto tiempo. DelayQueue solo entregará elementos cuyos retrasos hayan expirado.
  • PriorityQueue: Ordena sus elementos según su orden natural o un Comparador (si se proporciona). Esto significa que no funciona con el principio FIFO, sino que devuelve el elemento con la prioridad más alta (definido por cómo se comparan entre sí).

Imaginemos un sistema de anomalías, con un enum que defina su gravedad:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class Anomaly implements Comparable<Anomaly> {
    private String log;
    private Severity severity;

    public Anomaly(String log, Severity severity) {
        this.log = log;
        this.severity = severity;
    }

    @Override
    public int compareTo(Anomaly o) {
        return severity.compareTo(o.severity);
    }

    private enum Severity {
        HIGH,
        MEDIUM,
        LOW
    }
}

Aquí, las anomalías se ordenan naturalmente por su gravedad (como enum se ordenan naturalmente por su orden de declaración).

Entonces, si tuviéramos que agregar dos anomalías a una ‘PriorityQueue’ sin un ‘Comparador’, una ‘BAJA’ y una ‘ALTA’, entonces el método ’encuesta()’ devolvería la segunda anomalía primero en lugar de la primera:

1
2
3
4
5
6
7
8
9
Queue<Anomaly> anomalies = new PriorityQueue<>();

Anomaly optionalInformationNotRetrievedAnomaly = new Anomaly("Couldn't retrieve optional information", Anomaly.Severity.LOW);
anomalies.offer(optionalInformationNotRetrievedAnomaly);

Anomaly databaseNotReachableAnomaly = new Anomaly("Couldn't contact database", Anomaly.Severity.HIGH);
anomalies.offer(databaseNotReachableAnomaly);

anomalies.poll(); // This would return 'databaseNotReachableAnomaly'

Ahora, si pasamos un Comparador al constructor PriorityQueue, digamos uno que invierta el orden natural:

1
Queue<Anomaly> anomalies = new PriorityQueue<>(Comparator.reverseOrder());

Luego, en el mismo escenario que antes, el método poll() devolvería la primera anomalía, es decir, opcionalInformaciónNoRecuperadaAnomalia.

Por lo tanto

Ahora que la interfaz Queue ha sido cubierta, saltemos a Deque.

Principio

Deque significa Cola de doble terminación, lo que significa que esta es una cola a la que se puede acceder por ambos extremos y, por lo tanto, se puede usar con ambos Estilos FIFO y LIFO. Por defecto, organiza el estilo LIFO de su elemento, lo que significa que obtener el primero en Deque devolvería el último que se había agregado.

Adición de un elemento

Pasemos a los usos de Deque con la inserción de elementos. Hay múltiples posibilidades para conseguirlo:

  • Algunos métodos agregan el elemento en la parte superior, otros en la parte inferior
  • Algunos métodos arrojan una excepción si Deque está lleno, otros no.

Vamos a resumirlos en una tabla:


             Top                      Bottom

Sin excepción offerFirst() offer(), offerLast() Excepción addFirst(), push() add(), addLast()


Digamos que tenemos un Deque de Integer y llamamos a addFirst() con los números enteros 3 y 4:

1
2
3
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(3);
deque.addFirst(4);

Entonces, el deque contendrá 4 y 3, en este orden.

Si hubiéramos usado addLast(), habría contenido 3 y 4, en este orden. Lo mismo habría sucedido con offerFirst() y offerLast(), respectivamente.

Recuperación y eliminación de un elemento {#recuperación y eliminación de un elemento}

Ahora, veamos cómo recuperar elementos de un Deque. De nuevo, hay múltiples posibilidades:

  • Algunos métodos devuelven el primer elemento, otros devuelven el último
  • Algunos métodos eliminan el elemento cuando se devuelve, otros no
  • Algunos métodos arrojan una excepción si Deque está vacío, otros no.

Para hacerlo un poco más fácil, también lo resumiremos en una tabla:


             First (top) element, no removal   First (top) element, removal

Sin excepción peek(), peekFirst() encuesta(), encuestaPrimero() Excepción getFirst(), element() remove(), removeFirst(), pop()



             Last (bottom) element, no removal   Last (bottom) element, removal

Sin excepción peekLast() pollLast() Excepción getLast() removeLast()


Digamos que tenemos un Deque de Integer con los elementos 4 y 3, de arriba a abajo. Y llamamos peekFirst():

1
2
3
4
5
Deque<Integer> deque = new ArrayDeque<>();
deque.push(3);
deque.push(4);

deque.peekFirst();

Entonces, esto devolvería 4, sin eliminar el elemento. Si hubiéramos usado peekLast(), habría devuelto 3.

Ahora, si usáramos removeFirst() o pop(), obtendríamos 4 pero Deque solo contendría 3 al final.

Iterando sobre Elementos

En cuanto a la Cola, podemos iterar usando los mecanismos estándar y el método forEach(). Solo tenemos que recordar que, por defecto, el Deque organiza sus elementos al estilo LIFO y por lo tanto iterará sobre ellos, de arriba a abajo:

1
2
3
4
5
Deque<Integer> deque = new ArrayDeque<>();
deque.push(3);
deque.push(4);

deque.forEach(System.out::println);

Esto imprimiría:

1
2
4
3

También podrías usar un Iterador:

1
2
3
4
5
6
7
Deque<Integer> deque = new ArrayDeque<>();
deque.push(3);
deque.push(4);

for (Iterator<Integer> iterator = deque.iterator(); iterator.hasNext();) {
    System.out.println(iterator.next());
}

Esto también imprimiría:

1
2
4
3

Implementaciones

  • ArrayDeque: Este es el que usamos para Queue y que está respaldado por un array. Implementa Queue y Deque.
  • LinkedList: implementa Queue, Deque y List. También vemos este anterior.
  • LinkedBlockingDeque: Este funciona un poco como LinkedList, pero se puede delimitar. Por lo tanto, las operaciones de inserción que vimos anteriormente lanzarían una excepción si este Deque estuviera lleno.

¿Pila?

Vale la pena señalar que también existe una Pila. Se introdujo al comienzo de Java y se iba a utilizar como una colección LIFO, con los métodos push() y pop().

¿Por qué no usarlo entonces?

Porque la documentación nos aconseja usar la interfaz Deque que ofrece una API más consistente. Además, ‘Stack’ es una subclase de ‘Vector’ y, por lo tanto, está estrechamente vinculado a él, lo que lo convierte en una ‘Lista’ por encima de todas las cosas, lo que es conceptualmente diferente de una pila.

Conclusión

El Marco de colecciones de Java es un marco fundamental que todo desarrollador de Java debería saber cómo usar.

En este artículo, hemos hablado sobre las interfaces Queue y Deque y cubrimos sus operaciones principales. El código completo de este artículo se puede encontrar en GitHub.

Licensed under CC BY-NC-SA 4.0