Java Language
Colas y deques

El uso de la PriorityQueue

PriorityQueue es una estructura de datos. Al igual que SortedSet , PriorityQueue también clasifica sus elementos según sus prioridades. Los elementos, que tienen una prioridad más alta, vienen primero. El tipo de PriorityQueue debe implementar comparable interfaz comparable o de comparator , cuyos métodos deciden las prioridades de los elementos de la estructura de datos.

//The type of the PriorityQueue is Integer.
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();

//The elements are added to the PriorityQueue
queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );

//The PriorityQueue sorts the elements by using compareTo method of the Integer Class
//The head of this queue is the least element with respect to the specified ordering
System.out.println( queue );  //The Output: [1, 2, 3, 9, 3, 8]
queue.remove();
System.out.println( queue );  //The Output: [2, 3, 3, 9, 8]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 3, 9]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 9]
queue.remove();
System.out.println( queue );  //The Output: [8, 9]
queue.remove();
System.out.println( queue );  //The Output: [9]
queue.remove();
System.out.println( queue );  //The Output: []

LinkedList como una cola FIFO

La clase java.util.LinkedList , mientras implementa java.util.List es una implementación de propósito general de la interfaz java.util.Queue que también funciona con un principio FIFO (First In, First Out) .

En el siguiente ejemplo, con el método offer() , los elementos se insertan en LinkedList . Esta operación de inserción se llama enqueue . En el while bucle a continuación, los elementos se eliminan de la Queue sobre la base de FIFO. Esta operación se llama dequeue .

Queue<String> queue = new LinkedList<String>();

queue.offer( "first element" );
queue.offer( "second element" );
queue.offer( "third element" );
queue.offer( "fourth. element" );
queue.offer( "fifth. element" );

while ( !queue.isEmpty() ) {
  System.out.println( queue.poll() );
}

La salida de este código es

first element
second element
third element
fourth element
fifth element

Como se ve en la salida, el primer elemento insertado "primer elemento" se elimina en primer lugar, el "segundo elemento" se elimina en el segundo lugar, etc.

Pilas

¿Qué es una pila?

En Java, las pilas son una estructura de datos LIFO (Last In, First Out) para objetos.

API de pila

Java contiene una API de pila con los siguientes métodos

Stack()            //Creates an empty Stack
isEmpty()          //Is the Stack Empty?             Return Type: Boolean
push(Item item)    //push an item onto the stack
pop()              //removes item from top of stack  Return Type: Item
size()             //returns # of items in stack     Return Type: Int

Ejemplo

import java.util.*;

public class StackExample {

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      
      st.push(10);
      System.out.println("10 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(15);
      System.out.println("15 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(80);
      System.out.println("80 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("80 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("15 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("10 was popped from the stack");
      System.out.println("stack: " + st);
      
     if(st.isEmpty())
      {
         System.out.println("empty stack");
      }
   }
}

Esto devuelve:

stack: []
10 was pushed to the stack
stack: [10]
15 was pushed to the stack
stack: [10, 15]
80 was pushed to the stack
stack: [10, 15, 80]
80 was popped from the stack
stack: [10, 15]
15 was popped from the stack
stack: [10]
10 was popped from the stack
stack: []
empty stack

BlockingQueue

Un BlockingQueue es una interfaz, que es una cola que se bloquea cuando intenta salir de la cola y la cola está vacía, o si intenta poner en cola elementos en ella y la cola ya está llena. Se bloquea un subproceso que intenta salir de una cola vacía hasta que otro subproceso inserta un elemento en la cola. Un subproceso que intenta poner en cola un elemento en una cola completa se bloquea hasta que algún otro subproceso haga espacio en la cola, ya sea retirando uno o más elementos o eliminando la cola por completo.

Los métodos de BlockingQueue vienen en cuatro formas, con diferentes formas de manejar las operaciones que no pueden satisfacerse inmediatamente, pero que pueden satisfacerse en algún momento en el futuro: uno lanza una excepción, el segundo devuelve un valor especial (ya sea nulo o falso, dependiendo de la operación), el tercero bloquea el subproceso actual indefinidamente hasta que la operación pueda tener éxito, y el cuarto bloquea solo un límite de tiempo máximo dado antes de rendirse.

Un BlockingQueue puede ser limitado o ilimitado . Un BlockingQueue limitado es aquel que se inicializa con la capacidad inicial.

BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(2);

Cualquier llamada a un método put () se bloqueará si el tamaño de la cola es igual a la capacidad inicial definida.

Una cola ilimitada es aquella que se inicializa sin capacidad, de hecho, de forma predeterminada, se inicializa con Integer.MAX_VALUE.

Algunas implementaciones comunes de BlockingQueue son:

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

Ahora veamos un ejemplo de ArrayBlockingQueue :

BlockingQueue<String> bQueue = new ArrayBlockingQueue<>(2);
bQueue.put("This is entry 1");
System.out.println("Entry one done");
bQueue.put("This is entry 2");
System.out.println("Entry two done");
bQueue.put("This is entry 3");
System.out.println("Entry three done");

Esto imprimirá:

Entry one done
Entry two done

Y el hilo será bloqueado después de la segunda salida.

Interfaz de cola

Lo esencial

Una Queue es una colección para contener elementos antes del procesamiento. Las colas normalmente, pero no necesariamente, ordenan los elementos de una manera FIFO (primero en entrar, primero en salir).

El encabezado de la cola es el elemento que se eliminaría con una llamada para eliminar o sondear. En una cola FIFO, todos los elementos nuevos se insertan en la cola de la cola.

La interfaz de cola

public interface Queue<E> extends Collection<E> {
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

Cada método de Queue existe en dos formas:

• uno lanza una excepción si la operación falla;
• otro devuelve un valor especial si la operación falla (ya sea null o false según la operación).

Deque

Un Deque es una "cola de doble finalización", lo que significa que se pueden agregar elementos en la parte delantera o en la cola de la cola. La cola solo puede agregar elementos a la cola de una cola.

Deque hereda la interfaz de la Queue , lo que significa que los métodos regulares permanecen, sin embargo, la interfaz de Deque ofrece métodos adicionales para ser más flexible con una cola. Los métodos adicionales realmente hablan por sí mismos si sabes cómo funciona una cola, ya que esos métodos están destinados a agregar más flexibilidad:

Por supuesto las mismas opciones para offer , poll y peek están disponibles, sin embargo, no funcionan con excepciones, sino más bien con los valores especiales. No tiene sentido mostrar lo que hacen aquí.

Agregar y acceder a los elementos

Para agregar elementos a la cola de un Deque, se llama a su método add() . También puede usar los addFirst() y addLast() , que agregan elementos a la cabeza y la cola del deque.

Deque<String> dequeA = new LinkedList<>();

dequeA.add("element 1");      //add element at tail
dequeA.addFirst("element 2"); //add element at head
dequeA.addLast("element 3");  //add element at tail

Puede echar un vistazo al elemento que se encuentra al principio de la cola sin sacar el elemento de la cola. Esto se hace a través del método element() . También puede usar los getFirst() y getLast() , que devuelven el primer y último elemento en el Deque . Aquí es cómo se ve:

String firstElement0 = dequeA.element();
String firstElement1 = dequeA.getFirst();
String lastElement = dequeA.getLast();

Removiendo elementos

Para eliminar elementos de un deque, debe llamar a los métodos remove() , removeFirst() y removeLast() . Aquí están algunos ejemplos:

String firstElement = dequeA.remove();
String firstElement = dequeA.removeFirst();
String lastElement  = dequeA.removeLast();