Java Queue Interface y sus implementaciones

Aquí vamos a discutir la interfaz Java Queue. Descubrirá qué es la estructura de datos de la cola , cómo se representa en Java, qué métodos son los más importantes para todas las colas. Además, qué implementaciones de Queue están en lenguaje Java. Después de eso, echamos un vistazo más de cerca a las implementaciones más importantes y las aprendemos con ejemplos.

Estructura de datos de la cola

Una cola es una estructura de datos abstractos lineales con el orden particular de realizar operaciones: primero en entrar, primero en salir (FIFO). Eso significa que puede agregar un elemento (o ponerlo en la cola) solo al final de la estructura y tomar un elemento (quitarlo de la cola o eliminarlo de la cola) solo desde el principio. Puede imaginar la estructura de datos de la cola muy fácilmente. Parece una cola o una fila de clientes en la vida real. El cliente que llegó primero, también será atendido primero. Si tiene cuatro personas en fila en McDonalds o en otro lugar, el primero en hacer fila será el primero en llegar a la tienda. Si llega el nuevo cliente, será el 5º en la fila para conseguir hamburguesas. Entonces, mientras se trabaja con una cola, se agregan nuevos elementos al final, y si desea obtener un elemento, se tomará desde el principio. Este es el principio fundamental del trabajo de estructura de datos de cola clásica.

Cola en Java

Queue en Java es una interfaz. De acuerdo con la documentación de Oracle, la interfaz Queue tiene 2 superinterfaces, 4 interfaces diferentes que heredan de la cola y una lista de clases extremadamente impresionante. ¿Qué significa? En primer lugar, Java Queue es parte de Collection Framework e implementa la interfaz Collection. Por lo tanto, es compatible con todos los métodos de la interfaz de colección, como la inserción, la eliminación, etc. Queue implementa una interfaz Iterable, que permite que un objeto sea el objetivo de la instrucción "for-each loop".

Métodos de cola Java

La cola declara una serie de métodos. Como métodos de interfaz, deben estar representados en todas las clases que implementan Queue. Los métodos de cola más importantes, Java:

• Oferta booleana() : inserta un nuevo elemento en la cola si es posible
• Boolean add(E e) – inserta un nuevo elemento en la cola si es posible. Devuelve verdadero en caso de éxito y lanza una IllegalStateException si no hay espacio.
• Object poll() : recupera y elimina un elemento del encabezado del. Devuelve nulo si la cola está vacía.
• Object remove() : recupera y elimina un elemento de la cabeza de la cola.
• Object peek() : recupera, pero no elimina, un elemento del principio de la cola. Devuelve nulo si la cola está vacía.
• Object element() : recupera, pero no elimina, un elemento del principio de la cola.

Subinterfaces de Java Queue

La interfaz de cola es heredada por 4 subinterfaces: BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Las puedes dividir en 3 grupos: Deques, Blocking Queues y Transfer Queues with BlockingDeque pertenecientes a las dos primeras. Echemos un vistazo a estos grupos.

Deques

Deque significa cola de dos extremos y admite la adición o eliminación de cualquiera de los extremos de los datos como una cola (primero en entrar, primero en salir/FIFO) o desde la cabeza como otra estructura de datos popular llamada pila (último en entrar ) . primero en salir/LIFO). Clases que implementan la interfaz Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Colas de bloqueo

Una cola de bloqueo es una cola que bloquea un subproceso en dos casos:

• hilo está tratando de obtener elementos de una cola vacía
• hilo está tratando de poner elementos en la cola completa

Cuando un subproceso intenta obtener elementos de una cola vacía, espera hasta que otro subproceso coloca los elementos en la cola. De manera similar, cuando un subproceso intenta poner elementos en una cola completa, espera hasta que otro subproceso saca los elementos de la cola para obtener espacio libre para los elementos. Claro, el concepto de "cola llena" implica que la cola tiene un tamaño limitado, que generalmente se especifica en el constructor. Las colas de bloqueo estándar incluyen LinkedBlockingQueue, SynchronousQueue y ArrayBlockingQueue. Implementación de clases de interfaz BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BloqueoDequees una subinterfaz para BlockingQueue. BlockingDeque como BlockingQueue es una cola de bloqueo, pero bidireccional. Así que hereda las propiedades de la interfaz Deque. Está orientado a la ejecución multihilo, no permite cero elementos y la capacidad puede ser limitada. Las implementaciones de la interfaz BlockingDeque bloquean la operación de obtener elementos si la cola está vacía y agregar un elemento a la cola si está llena.

Colas de transferencia

La interfaz TransferQueue amplía la interfaz BlockingQueue. Sin embargo, a diferencia de la implementación de las colas de la interfaz BlockingQueue, donde los subprocesos se pueden bloquear si la cola está vacía (lectura) o si la cola está llena (escritura), las colas de la interfaz TransferQueue bloquean el flujo de escritura hasta que otro flujo recupera el elemento. Use un método de transferencia para esto. En otras palabras, la implementación de BlockingQueue garantiza que el elemento creado por el Productor debe estar en la cola, mientras que la implementación de TransferQueue garantiza que el elemento Productor sea "recibido" por el Consumidor. Solo hay una implementación oficial de Java de la interfaz TransferQueue: LinkedTransferQueue.

Implementaciones de colas de Java

Hay muchas clases que implementan la interfaz Queue:

• AbstractQueue según los documentos de Queue Java 8, esta clase abstracta proporciona implementaciones básicas de algunas operaciones de Queue. No permite elementos nulos. Hay 3 métodos más para agregar, eliminar y elementos basados ​​en la oferta clásica de la cola , la encuesta y el vistazo , respectivamente. Sin embargo, lanzan excepciones en lugar de indicar fallas a través de retornos falsos o nulos.
• ArrayBlockingQueue : una cola de bloqueo FIFO de tamaño fijo respaldada por una matriz
• ArrayDeque : implementación de matriz redimensionable de la interfaz Deque
• ConcurrentLinkedDeque : un deque concurrente ilimitado basado en nodos vinculados.
• ConcurrentLinkedQueue : una cola ilimitada segura para subprocesos basada en nodos vinculados.
• DelayQueue : una cola de programación basada en el tiempo respaldada por un montón
• LinkedBlockingDeque : la implementación simultánea de la interfaz Deque.
• LinkedBlockingQueue : una cola de bloqueo FIFO limitada opcionalmente respaldada por nodos vinculados
• LinkedList : implementación de lista doblemente enlazada de las interfaces List y Deque. Implementa todas las operaciones de lista opcionales y permite todos los elementos (incluido nulo)
• LinkedTransferQueue : una TransferQueue ilimitada basada en nodos vinculados
• PriorityBlockingQueue : una cola de prioridad de bloqueo ilimitada respaldada por un montón
• PriorityQueue : una cola de prioridad basada en la estructura de datos del montón
• SynchronousQueue : una cola de bloqueo en la que cada operación de inserción debe esperar una operación de eliminación correspondiente por parte de otro subproceso, y viceversa.

Las implementaciones más populares son LinkedList, ArrayBlockingQueue y PriorityQueue. Veámoslos y hagamos algunos ejemplos para una mejor comprensión.

Lista enlazada

La clase LinkedList en Java implementa las interfaces List y Deque. Por lo tanto, es una combinación de List y Deque, una cola bidireccional que admite agregar y eliminar elementos de ambos lados. En Java, LinkedList es una lista doblemente enlazada: cada elemento de List llama a Node y contiene un objeto y referencias a dos objetos vecinos: el anterior y el siguiente. Puede decir que LinkedList no es muy efectivo en términos de uso de memoria. Eso es cierto, pero esta estructura de datos puede ser útil en el caso del rendimiento de las operaciones de inserción y eliminación. Sin embargo, sucede solo si usa iteradores para ellos (en este caso ocurre en tiempo constante). Las operaciones de acceso por índice se realizan buscando desde el principio hasta el final (el que esté más cerca) del elemento deseado. Sin embargo, no olvide los costos adicionales por almacenar referencias entre elementos. Entonces, LinkedList es la implementación de cola más popular en Java. También es una implementación de List y Deque y nos permite crear una cola bidireccional que consta de cualquier objeto, incluido nulo. LinkedList es una colección de elementos.

Constructores de listas enlazadas

LinkedList() sin parámetros se usa para construir una lista vacía. LinkedList(Collection<? extends E> c) es para crear una lista que contiene los elementos de la colección especificada, en orden, son devueltos por el iterador de la colección.

Principales métodos de lista enlazada:

• add(E elemento) Agrega el elemento especificado al final de esta lista;
• add(int index, elemento E) Inserta el elemento en la posición especificada index;
• get(int index) Devuelve el elemento en la posición especificada en esta lista;
• remove(int index) Elimina el elemento que está en la posición index;
• remove(Object o) Elimina la primera ocurrencia del elemento ?o de esta lista si está ahí.
• remove() Recupera y elimina el primer elemento de la lista.
• addFirst(), addLast() agrega un elemento al principio/final de una lista
• clear() elimina todos los elementos de la lista
• contiene (Objeto o) devuelve verdadero si la lista contiene el elemento o.
• indexOf(Object o) devuelve el índice de la primera aparición del elemento o, o -1 si no está en la lista.
• set (índice int, elemento E) reemplaza el elemento en la posición de índice con el elemento
• size() Devuelve la cantidad de elementos de la lista.
• toArray() devuelve una matriz que contiene todos los elementos de la lista desde el primero hasta el último elemento.
• pop() que extrae un elemento de la pila (representado por la lista)
• push(E e) que empuja un elemento a la pila (representado por esta lista)

Ejemplo de Java Queue: LinkedList (poner y quitar elementos de diferentes maneras)

import java.util.*;

public class LinkedListTest {

       public static void main(String args[]){

           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

PriorityQueue

PriorityQueue no es exactamente la cola en el sentido general FIFO. Los elementos de la cola de prioridad se ordenan según su ordenación natural o mediante un Comparador proporcionado en el momento de la construcción de la cola, según el constructor que se utilice. Sin embargo, no es un orden como podría ser una estructura lineal como una lista (de mayor a menor o viceversa). Una cola de prioridad basada en un montón mínimo de prioridad. Heap es una estructura de datos basada en un árbol binario. La prioridad de cada padre es mayor que las prioridades de sus hijos. Un árbol se llama binario completo si cada padre no tiene más de dos hijos y el llenado de los niveles va de arriba a abajo (desde el mismo nivel, de izquierda a derecha). El montón binario se reorganiza cada vez que se agrega o elimina un nuevo elemento. En el caso de min-heap, el elemento más pequeño va a la raíz sin importar el orden de su inserción. Cola de prioridad basada en este montón mínimo, por lo que si tenemos un PriorityQueue de enteros, su primer elemento será el más pequeño de estos números. Si elimina la raíz, la siguiente más pequeña se convierte en una raíz.

Métodos principales de PriorityQueue:

• boolean add(objeto) inserta el elemento especificado en la cola de prioridad. Devuelve verdadero en caso de éxito. Si la cola está llena, el método lanza una excepción.
• oferta booleana (objeto) inserta el elemento especificado en esta cola de prioridad. Si la cola está llena, el método devuelve falso.
• boolean remove(object) elimina una sola instancia del elemento especificado de esta cola, si está presente.
• Object poll() recupera y elimina el encabezado de esta cola. Devuelve nulo si la cola está vacía.
• void clear() elimina todos los elementos de la cola de prioridad.
• Object element() recupera el encabezado de esta cola sin eliminarlo. Lanza NoSuchElementException si la cola está vacía.
• Object peek() recupera el encabezado de la cola sin eliminarlo. Devuelve nulo si la cola está vacía.
• boolean contains(Object o) devuelve verdadero si la cola contiene el elemento o.
• int size() devuelve el número de elementos en esta cola.

Ejemplo de PriorityQueue

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
   public static void main(String[] args) {

       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();

       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }

       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval):
1
2
3
4
5

Es importante comprender que las colas de prioridad se basan en montones binarios, por lo que no mantienen los elementos en un orden ordenado lineal. Todos los caminos desde la raíz hasta la hoja están ordenados, pero los diferentes caminos desde la raíz no lo están. Eso significa que puede obtener el elemento mínimo de la cola muy rápidamente. Si elimina la cabeza cada vez, imprimirá una estructura ordenada.

ArrayBlockingQueue

Estructura de datos internos de ArrayBlockingQueuese basa en una matriz circular para almacenar elementos. Es una cola típica (FIFO) en caso de que se inserten nuevos elementos al final de la cola y las operaciones de extracción devuelvan un elemento del principio de la cola. Una vez creada, la capacidad de la cola no se puede cambiar. Los intentos de insertar (poner) un elemento en una cola completa conducen a bloquear el flujo; intentar tomar un elemento de una cola vacía también bloquea el hilo. Como dijimos antes, esta matriz es circular. Eso significa que el primer y el último elemento de la matriz se tratan como lógicamente adyacentes. La cola avanza los índices de los elementos de cabeza y cola cada vez que coloca el elemento en la cola o lo elimina de la cola. Si algún índice avanza el último elemento de la matriz, se reinicia desde 0. Por lo tanto, la cola no tiene que cambiar todos los elementos en caso de que se elimine la cabeza (como en la matriz habitual). Sin embargo, en caso de eliminar un elemento del medio (usando Iterator.remove), los elementos se desplazan. ArrayBlockingQueue admite una política de equidad adicional con un parámetro justo en el constructor para ordenar el trabajo de los flujos de espera de productores (inserción de elementos) y consumidores (extracción de elementos). Por defecto, el pedido no está garantizado. Sin embargo, si la cola se crea con "fair == true", la implementación de la clase ArrayBlockingQueue proporciona acceso a subprocesos en orden FIFO. La equidad generalmente reduce el ancho de banda, pero también reduce la volatilidad y evita quedarse sin recursos.

Constructores de clase ArrayBlockingQueue

• ArrayBlockingQueue (capacidad int) crea una cola de capacidad fija y con una política de acceso por defecto.
• ArrayBlockingQueue (int capacity, boolean fair) crea una cola con una capacidad fija y una política de acceso especificada.
• ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) crea una cola con una capacidad fija especificada por la política de acceso e incluye elementos en la cola.

Aquí tenemos el ejemplo de BlockingQueueExample. Creamos una cola de ArrayBlockingQueue con una capacidad de un elemento y una bandera justa. Se inician dos hilos. El primero de ellos, el subproceso Producer, pone en cola los mensajes de la matriz de mensajes mediante el método put. El segundo subproceso, Consumer, lee elementos de la cola utilizando el método de toma y los muestra en la consola. El orden de los elementos es el natural para la cola.

import java.util.concurrent.*;

public class ArrayBlockingQueueExample {

   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};

       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }

       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

La salida es la cola en orden natural; los dos primeros elementos aparecen con un retraso. Para reforzar lo que aprendió, le sugerimos que vea una lección en video de nuestro Curso de Java

Conclusiones

• La Cola se usa para insertar elementos al final de la cola y los elimina del principio de la cola. Sigue el concepto FIFO.
• Java Queue es parte de Collection Framework e implementa la interfaz de colección. Por lo tanto, es compatible con todos los métodos de la interfaz de colección, como la inserción, la eliminación, etc.
• Las implementaciones de Queue más utilizadas son LinkedList, ArrayBlockingQueue y PriorityQueue.
• Los elementos de la cola de prioridad se ordenan según su ordenación natural o mediante un Comparador proporcionado en el momento de la construcción de la cola, según el constructor que se utilice.
• Si se realiza alguna operación nula en BlockingQueues, se lanza NullPointerException.