Java Language
Code e Deques

L'uso di PriorityQueue

PriorityQueue è una struttura dati. Come SortedSet , PriorityQueue ordina anche i suoi elementi in base alle loro priorità. Gli elementi, che hanno una priorità più alta, vengono prima di tutto. Il tipo di PriorityQueue dovrebbe implementare un'interfaccia comparable o di comparator , i cui metodi decidono le priorità degli elementi della struttura dati.

//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 come coda FIFO

La classe java.util.LinkedList , mentre si implementa java.util.List è un'implementazione generica dell'interfaccia java.util.Queue che opera anche su un principio FIFO (First In, First Out) .

Nell'esempio seguente, con il metodo offer() , gli elementi vengono inseriti in LinkedList . Questa operazione di inserimento si chiama enqueue . Nel ciclo while seguito, gli elementi vengono rimossi dalla Queue basata su FIFO. Questa operazione si chiama 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() );
}

L'output di questo codice è

first element
second element
third element
fourth element
fifth element

Come visto nell'output, il primo elemento inserito "first element" viene rimosso per primo, "second element" viene rimosso in secondo luogo, ecc.

Stacks

Cos'è una pila?

In Java, gli stack sono una struttura di dati LIFO (Last In, First Out) per oggetti.

Stack API

Java contiene un'API dello stack con i seguenti metodi

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

Esempio

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");
      }
   }
}

Questo ritorna:

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 è un'interfaccia, che è una coda che si blocca quando si tenta di disconnettersi da esso e la coda è vuota, o se si tenta di accodare gli elementi a esso e la coda è già piena. Un thread che tenta di disconnettere da una coda vuota viene bloccato fino a quando un altro thread inserisce un elemento nella coda. Un thread che tenta di accodare un elemento in una coda completa viene bloccato fino a quando un altro thread non fa spazio nella coda, eliminando uno o più elementi o eliminando completamente la coda.

I metodi BlockingQueue sono disponibili in quattro forme, con diversi modi di gestire le operazioni che non possono essere soddisfatti immediatamente, ma potrebbero essere soddisfatti in futuro: uno lancia un'eccezione, il secondo restituisce un valore speciale (nullo o falso, a seconda della operazione), il terzo blocca il thread corrente per un tempo indefinito fino a quando l'operazione può avere successo, e il quarto blocco solo per un dato limite di tempo massimo prima di rinunciare.

Un BlockingQueue può essere limitato o illimitato . Un BlockingQueue limitato è uno che viene inizializzato con la capacità iniziale.

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

Qualsiasi chiamata a un metodo put () verrà bloccata se la dimensione della coda è uguale alla capacità iniziale definita.

Una coda illimitata è una che è inizializzata senza capacità, in realtà per impostazione predefinita è inizializzata con Integer.MAX_VALUE.

Alcune implementazioni comuni di BlockingQueue sono:

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

Ora diamo un'occhiata a un esempio di 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");

Questo stamperà:

Entry one done
Entry two done

E il thread verrà bloccato dopo la seconda uscita.

Interfaccia della coda

Nozioni di base

Una Queue è una raccolta per contenere elementi prima dell'elaborazione. Le code tipicamente, ma non necessariamente, ordinano gli elementi in un modo FIFO (first-in-first-out).

Capo della coda è l'elemento che verrebbe rimosso da una chiamata per rimuovere o eseguire il polling. In una coda FIFO, tutti i nuovi elementi sono inseriti nella coda della coda.

L'interfaccia della coda

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

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

Ogni metodo di Queue esiste in due forme:

• si genera un'eccezione se l'operazione fallisce;
• altro restituisce un valore speciale se l'operazione fallisce ( null o false seconda dell'operazione.

deque

Un Deque è una "coda doppia", il che significa che è possibile aggiungere elementi nella parte anteriore o coda della coda. Solo la coda può aggiungere elementi alla coda di una coda.

Il Deque eredita l'interfaccia Queue , il che significa che i metodi regolari rimangono, tuttavia l'interfaccia di Deque offre metodi aggiuntivi per essere più flessibili con una coda. I metodi aggiuntivi parlano davvero da soli se si sa come funziona una coda, poiché questi metodi sono pensati per aggiungere più flessibilità:

Ovviamente sono disponibili le stesse opzioni per offer , poll e peek , tuttavia non funzionano con eccezioni ma piuttosto con valori speciali. Non ha senso mostrare ciò che fanno qui.

Aggiunta e accesso agli elementi

Per aggiungere elementi alla coda di un Deque si chiama il suo metodo add() . Puoi anche usare i addFirst() e addLast() , che aggiungono elementi alla testa e alla coda 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

Puoi dare un'occhiata all'elemento in testa alla coda senza togliere l'elemento dalla coda. Questo viene fatto tramite il metodo element() . È anche possibile utilizzare i metodi getLast() getFirst() e getLast() , che restituiscono il primo e l'ultimo elemento nel Deque . Ecco come appare:

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

Rimozione di elementi

Per rimuovere elementi da un deque, si chiamano i metodi remove() , removeFirst() e removeLast() . Ecco alcuni esempi:

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