Colecciones de Java: interfaces de cola y deque

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 extienden el java.util.Collection y java.util.Map interfaces. En su mayoría, estas clases ofrecen diferentes formas de formular una colección de objetos dentro de uno solo.

Colecciones de Java 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 colecciones de Java:

• La interfaz de lista
• La interfaz de conjunto
• La interfaz del mapa
• Colas, Deques, Pilas (estás aquí)

Cola

Comencemos este artículo final de la serie con el java.util.Queue interfaz.

Principio

En primer lugar, ¿para qué sirve? los Queue Esta diseñado para retener 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.

Por tanto, la idea es introducir algunos elementos en una Queuey luego recupérelos. Generalmente, las colas devuelven elementos que respetan el patrón Primero en entrar, primero en salir (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 responder a algún tipo de sistema de prioridad (por ejemplo, usando Comparator).

Te puede interesar:Colecciones Java: la interfaz de conjuntos

Puedes pensar en LIFO como una pila de monedas. El último que se coloca en la parte superior de la pila es el primero que se retira.

Exploremos ahora las características del Queue ¡interfaz!

Agregar un elemento

Comenzaremos agregando un elemento a un Queue. Primero, creemos una instancia usando el ArrayDeque implementación, que también implementa la Deque interfaz que cubriremos más adelante:

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

Para agregar un elemento en este Queue, tenemos dos posibilidades: add() método o el offer() método.

Empecemos por el primero:

queue.add(3);

Y con este último:

queue.offer(4);

Ambos devuelven un boolean valor que indica si el elemento se agregó al Queue o no, según su capacidad (si aplica). Entonces, ¿cuál es la diferencia entre ambos métodos?

Bueno, el primero de hecho nunca regresará false, en lugar de lanzar un Exception al agregar un elemento a un Queue. Por otro lado, el segundo volverá false en esos casos.

En vez de ArrayDeque, que no tiene límites, usemos el LinkedBlockingQueue al que se le puede asignar una capacidad:

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

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

Te puede interesar:Colecciones Java: la interfaz de lista

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

Intentar agregar estos dos elementos resultará en:

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

Por otro lado, usando el offer() el método en su lugar no hará nada y regresará false como resultado.

Recuperar un elemento

Como se dijo anteriormente, un Queue generalmente respeta FIFO, lo que significa que devolverá el primer elemento ingresado primero, si estamos recuperando uno.

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

los remove() y element() Los métodos lanzarán una excepción cuando se llamen en un vacío Queue:

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(3);
queue.offer(4);

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

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

Utilizando remove() y element() en vez 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 indexado while y for bucles, el Queue implementos de interfaz Iterable y proporciona un Iterator, lo que lo hace elegible para el for-each lazo:

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 forEach() método, pasando una referencia de método:

Te puede interesar:Java: compruebe si la matriz contiene valor o elemento

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

Esto logra el mismo resultado que el ciclo anterior.

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

Implementaciones

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

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

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

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 están naturalmente ordenadas por su gravedad (como enum están ordenados naturalmente por su orden de declaración).

Entonces, si tuviéramos que agregar dos anomalías a un PriorityQueue sin un Comparator, uno LOW y uno HIGH, entonces la poll() El método devolvería la segunda anomalía primero y la primera:

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 Comparator al PriorityQueue constructor, digamos uno que invierte el orden natural:

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

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

Deque

Ahora que el Queue se ha cubierto la interfaz, saltemos a Deque.

Principio

Deque significa Cola de doble final, lo que significa que se trata de una cola a la que se puede acceder por ambos extremos y, por tanto, se puede utilizar con los estilos FIFO y LIFO. Por defecto, organiza su elemento estilo LIFO, lo que significa que obtener el primero en el Deque devolvería el último que se había agregado.

Te puede interesar:Cómo declarar e inicializar una matriz en Java

Agregar un elemento

Saltemos a Deque usos con inserción de elementos. Existen múltiples posibilidades para lograrlo:

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

Resumámoslos en una tabla:

Arriba Abajo

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

Digamos que tenemos un Deque de Integer y llamamos addFirst() con enteros 3 y 4:

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(), entonces habría contenido 3 y 4, en este orden. Lo mismo hubiera pasado con offerFirst() y offerLast(), respectivamente.

Recuperar y eliminar un elemento

Ahora, veamos cómo recuperar elementos de un Deque. Nuevamente, existen múltiples posibilidades:

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

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

Primer elemento (superior), sin eliminación Primer elemento (superior), eliminación

Sin excepción	peek(), peekFirst()	poll(), pollFirst()
Excepción	getFirst(), element()	remove(), removeFirst(), pop()

Último elemento (inferior), sin eliminación Último elemento (inferior), eliminación

Te puede interesar:Ordenar por selección en Java

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

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

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

deque.peekFirst();

Entonces, esto volvería 4, sin quitar el elemento. Si hubiéramos usado peekLast(), entonces habría vuelto 3.

Ahora, si tuviéramos que usar removeFirst() o pop(), tendríamos 4 pero el Deque solo contendría 3 en el final.

Iterando sobre elementos

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

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

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

Esto imprimiría:

4
3

También puede utilizar un Iterator:

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:

4
3

Implementaciones

• ArrayDeque: Este es el que usamos para Queue y que está respaldado por un array. Implementa ambos Queue y Deque.
• LinkedList: Implementa ambos Queue, Deque y List. También vemos este antes.
• LinkedBlockingDeque: Este funciona un poco como el LinkedList, pero puede estar acotado. Por lo tanto, las operaciones de inserción que vimos anteriormente arrojarían una excepción si esto Deque estaba lleno.

¿Apilar?

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

¿Por qué no usarlo entonces?

Porque la documentación nos aconseja utilizar el Deque interfaz que ofrece una API más consistente. Más, Stack es una subclase de Vector y por lo tanto está estrechamente ligado a él, lo que lo convierte en un List sobre todas las cosas, que es conceptualmente diferente de una pila.

Te puede interesar:Java: cómo obtener claves y valores de un mapa

Conclusión

El marco de colecciones de Java es un marco fundamental que todo desarrollador de Java debería saber utilizar.

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