Interfaccia Java Deque

Java Deque è una struttura dati che combina una coda e uno stack ordinari. Puoi aggiungere e togliere elementi sia alla testa che alla coda della Deque. Nella coda "tradizionale" aggiungi elementi alla coda della riga (dopo l'ultimo elemento) e rimuovi elementi dalla testa della coda. Questo principio si chiama First In First Out (FIFO) e funziona come qualsiasi normale linea di clienti nella vita reale. In Java Queue è un'interfaccia, una parte del Collections Framework. Esiste anche un'importante struttura di dati chiamata Stack, un elenco che funziona con elementi in un principio totalmente inverso, LIFO: ultimo a entrare, primo a uscire. È simile a una pila di lastre, l'aggiunta o la rimozione è possibile solo in alto.

Coda vs Deque

Deque è un tipo strano di coda: puoi aggiungere nuovi elementi sia alla coda che alla testa della lenza. La stessa storia con la rimozione: puoi rimuovere l'ultimo o il primo elemento da questa struttura. Quindi, sembra essere una miscela di Stack e Queue. Il nome "Deque" significa "Coda a doppia estremità". "Deque" si pronuncia come un "mazzo" di carte e sai una cosa? È in qualche modo simile a un vero mazzo di carte: puoi prendere una carta dal fondo o dall'alto di tale mazzo. Vuoi aggiungere o rimuovere elementi da entrambi i lati di una struttura lineare? Usa Deque. Java 8 o quasi tutte le altre versioni lo supportano. Immagina un tipico mattoncino lego e "torri" a una colonna fatte di mattoncini. Puoi aggiungere un nuovo mattone in cima o in fondo alla torre. Puoi anche rimuovere un mattone da entrambi i lati. Ecco un esempio: aggiungiamo tutti i mattoni gialli in alto e tutti i rossi in basso. Dimostreremo presto questo esempio con il codice Java. Quindi puoi accodare e rimuovere dalla coda da entrambe le estremità di una Deque Java, il che significa che puoi usare una Deque sia come coda che come stack. Leggi Stack in Java: Java Stack 101: Approfondire la classe Stack Leggi Queue in Java: Java Queue Interface e le sue implementazioni

Le caratteristiche di Deque

• Deque in Java è un'interfaccia, le cui implementazioni forniscono il supporto di un array ridimensionabile. Quindi hai una serie di capacità senza restrizioni e puoi aggiungere nuovi elementi in base alle tue esigenze.
• L'accesso simultaneo da parte di più thread non è supportato da Deque
• Deque non è thread-safe in caso di assenza di sincronizzazione esterna.
• Nessun elemento Null consentito nella deque dell'array.

Deque Dichiarazione dell'interfaccia Java

public interface Deque<E> extends Queue<E>

Metodi Java Deque

java.util.Deque è un'interfaccia che estende Java Queue Interface e rappresenta una coda a doppia estremità. Quindi puoi utilizzare tutti i metodi Java Queue mentre lavori con un Deque. Nonostante Deque non estenda l'interfaccia Stack, l'interfaccia Deque definisce metodi che consentono di eseguire operazioni tipiche dello stack come push , peek e pop .

• boolean add(element) aggiunge un elemento alla coda della Deque. Restituisce true in caso di successo, genera un'eccezione IllegalStateException se non è attualmente disponibile spazio.
• addFirst(element) aggiunge un elemento alla testa della Deque.
• addLast(element) aggiunge un elemento alla coda della Deque.
• offer(element) aggiunge un elemento alla coda e restituisce un valore booleano per spiegare se l'inserimento ha avuto successo.
• offerFirst(element) aggiunge un elemento alla testa e restituisce un valore booleano per spiegare se l'inserimento ha avuto successo.
• offerLast(element) aggiunge un elemento alla coda e restituisce un valore booleano per spiegare se l'inserimento ha avuto successo.
• iterator() restituisce un iteratore per la deque.
• discendenteIterator() restituisce un iteratore che ha l'ordine inverso per questa deque.
• push(element) aggiunge un elemento alla testa.
• pop(element) rimuove un elemento dalla testa e lo restituisce.
• removeFirst() rimuove l'elemento in testa.
• removeLast() rimuove l'elemento alla coda.
• poll() recupera e rimuove l'inizio della coda rappresentata da questa deque (in altre parole, il primo elemento di questa deque), o restituisce null se questa deque è vuota.
• pollFirst() recupera e rimuove il primo elemento di questa deque o restituisce null se questa deque è vuota.
• pollLast() recupera e rimuove l'ultimo elemento di questa deque o restituisce null se questa deque è vuota.
• peek() recupera, ma non rimuove, l'inizio della coda rappresentata da questa deque (in altre parole, il primo elemento di questa deque), oppure restituisce null se questa deque è vuota.
• peekFirst() recupera, ma non rimuove, il primo elemento di questa deque, oppure restituisce null se questa deque è vuota.
• peekLast() recupera, ma non rimuove, l'ultimo elemento di questa deque, oppure restituisce null se questa deque è vuota.

Qui nella tabella sottostante tutti i metodi sono divisi per gruppi. Come puoi vedere ci sono molti metodi diversi per aggiungere e rimuovere un elemento. Ad esempio, sia removeFirst() che pop() rimuovono il primo elemento da deque. Il secondo "è venuto" dalla pila. Ciò significa che se usi il tuo ArrayDeque solo come stack, usa pop() per rimuovere, push() per aggiungere e peek() per esaminare. Questo rende il tuo codice più sensato per altri sviluppatori.

Implementazioni Deque

Java Deque è un'interfaccia e ha implementazioni nell'API Java Collections:

• java.util.LinkedList //Implementazione elenco e deque
• java.util.ArrayDeque //Implementazione Deque, libreria Java

La classe LinkedList utilizza internamente un elenco a doppio collegamento per modellare una coda o una deque. La classe ArrayDeque memorizza gli elementi internamente in un array. Se il numero di elementi supera il volume dell'array, viene allocato un nuovo array e tutti gli elementi vengono spostati. Ciò significa che ArrayDeque cresce in base alle esigenze.

Classe ArrayDeque

La classe ArrayDeque <E> è una coda bidirezionale generale, che eredita funzionalità dalla classe AbstractCollection e utilizza l'interfaccia Deque. ArrayDeque fornisce la possibilità di utilizzare deque e ridimensionabile-array. Inizialmente, l'array è inizializzato con la dimensione 16. È implementato come una coda a due vie, dove supporta due puntatori, cioè la testa e la coda. Eredita la classe AbstractCollection e implementa l' interfaccia Deque . I punti importanti sulla classe ArrayDeque sono:

• Puoi aggiungere o rimuovere elementi dalla coda e dalla testa dell'ArrayDeque
• Gli elementi nulli non sono consentiti
• ArrayDeque non è thread-safe, in assenza di sincronizzazione esterna.
• ArrayDeque non ha limiti di capacità.

Costruttori della classe ArrayDeque

• ArrayDeque() crea una coda vuota.
• ArrayDeque (Collection <? Extends E> collection) crea una coda piena di elementi Collection Collection.
• ArrayDeque (capacità int) crea una coda con capacità di capacità iniziale . Se non si specifica la capacità iniziale, la capacità predefinita è 16.

Esempio Java Deque — ArrayDeque

Ricordi l'esempio della torre Lego dall'inizio dell'articolo? Creiamo una classe per costruire torri a una colonna fatte di mattoncini Lego. I mattoni possono essere rossi, gialli o blu. La nostra regola per la costruzione della Torre: mettiamo i mattoni rossi in basso e i mattoni gialli in cima. Esempio di Big Java Deque

//enum with colors 
public enum Color {
   RED, YELLOW, BLUE;
}

//class for the standard Lego Brick. You can connect or disconnect the Brick, it has color   
public class LegoBrick {
   Color color;
   boolean isConnected;

   public void connect() {
       System.out.println("This brick is connected");
       this.isConnected = true;
   }

   public void disconnect() {
       System.out.println("Disconnected");
       isConnected = false;
   }

   public LegoBrick(Color color, boolean isConnected) {
       this.color = color;
       this.isConnected = isConnected;
   }

   public Color getColor() {
       return color;
   }

   public boolean isConnected() {
       return isConnected;
   }

   @Override
   public String toString() {
       return "LegoBrick{" +
              "color=" + color +
              ", isConnected=" + isConnected +
              '}';
   }
}

Ecco la nostra classe Tower. Iniziamo una torre. La torre iniziata dipende dalla quantità di rossi e gialli. Possiamo aggiungere mattoni alla torre o rimuoverlo. Aggiungiamo il mattone in alto se è giallo e lo aggiungiamo in basso se è rosso.

import java.util.ArrayDeque;
public class LegoTower {
   ArrayDeque<LegoBrick> myTower;
   int quantityOfReds;
   int quantityOfYellows;

   public void addBrickToTower(LegoBrick newLegoBrick) {
       if (newLegoBrick.getColor() == Color.YELLOW) {
           this.myTower.offerLast(newLegoBrick);
           quantityOfYellows++;
       }
	//we can use addFirst(e)/push(e) instead of offerFirst here 
       if (newLegoBrick.getColor() == Color.RED) {
           myTower.offerFirst(newLegoBrick);
           quantityOfReds++;
       }
   }

   public void removeBrickFromTower (LegoBrick legoBrick) {
       if (legoBrick.getColor() == Color.YELLOW) {
           this.myTower.removeLast();
           quantityOfYellows--;
       }
       if (legoBrick.getColor() == Color.RED) {
           myTower.removeFirst();
           quantityOfReds--;
       }
       legoBrick.isConnected = false;

   }

   public LegoTower(int quantityOfReds, int quantityOfYellows) {

       myTower = new ArrayDeque<>();
       this.quantityOfReds = quantityOfReds;
       this.quantityOfYellows = quantityOfYellows;
       for (int i = 0; i < quantityOfReds; i++) {
           LegoBrick redLegoBrick = new LegoBrick(Color.RED, false);
           myTower.addFirst(redLegoBrick);
           redLegoBrick.isConnected = true;
       }
       for (int i = 0; i < quantityOfYellows; i++) {
           LegoBrick yellowLegoBrick = new LegoBrick(Color.YELLOW, false);
           myTower.addLast(yellowLegoBrick);
           yellowLegoBrick.isConnected = true;
       }
   }

   public void setMyTower(ArrayDeque<legobrick> myTower) {
       this.myTower = myTower;
   }

   public void setQuantityOfReds(int quantityOfReds) {
       this.quantityOfReds = quantityOfReds;
   }

   public void setQuantityOfYellows(int quantityOfYellows) {
       this.quantityOfYellows = quantityOfYellows;
   }

   @Override
   public String toString() {
       return "LegoTower{" +
              "myTower=" + myTower +
              ", quantityOfReds=" + quantityOfReds +
              ", quantityOfYellows=" + quantityOfYellows +
              '}';
   }

   public void drawTower() {
       for (LegoBrick i : myTower) {
           System.out.println(i.color);
       }
   }
}


public class Main {
   public static void main(String[] args) {
       LegoBrick legoBrick1 = new LegoBrick(Color.YELLOW, false);
       legoBrick1.connect();
       System.out.println(legoBrick1.toString());
       legoBrick1.disconnect();
       System.out.println(legoBrick1.toString());
       LegoBrick legoBrick2 = new LegoBrick(Color.YELLOW, false);
       LegoBrick legoBrick3 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick4 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick5 = new LegoBrick(Color.YELLOW, false);

       LegoTower legoTower = new LegoTower(2, 5);
       System.out.println("my Initiated Lego Tower: ");
       legoTower.drawTower();
       legoTower.addBrickToTower(legoBrick1);
       legoTower.addBrickToTower(legoBrick2);
       legoTower.addBrickToTower(legoBrick3);
       legoTower.addBrickToTower(legoBrick4);
       legoTower.addBrickToTower(legoBrick5);
       System.out.println("My LegoTower after adding some elements: ");
       legoTower.drawTower();
       legoTower.removeBrickFromTower(legoBrick1);
       legoTower.removeBrickFromTower(legoBrick3);
       System.out.println("We removed one red and one yellow brick:");
       legoTower.drawTower();

   }

}

Il risultato dell'esecuzione di questo programma:

my Initiated LegoTower:

RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements: 
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW

Process finished with exit code 0

Aspetta cosa?? Perché i rossi sono in alto? No, non lo fanno. Sono appena stati stampati sulla console a partire dal primo (in basso) fino all'ultimo (in alto). Quindi, se vuoi vedere qualcosa come nell'immagine con i mattoncini sopra, puoi cambiare il metodo drawTower della classe LegoTower. È un compito molto facile!

Lista collegata

L'interfaccia Elenco mantiene la sequenza di aggiunta di elementi e consente l'accesso all'elemento tramite indice. Deque è una coda bidirezionale e supporta l'aggiunta e la rimozione di elementi da entrambi i lati. LinkedList è principalmente noto come implementazione List, ma anche questa classe implementa la Deque e ci consente di creare una coda bidirezionale composta da qualsiasi oggetto incluso null. LinkedList è una raccolta di elementi. Possiamo vederlo nel codice sorgente della classe, stavolta prestando attenzione ai campi: Qui aggiungiamo un esempio, ma se vuoi saperne di più su LinkedList, benvenuto in questo articolo di CodeGym .

Implementazione di elenchi collegati in Java, aggiunta e rimozione di elementi. Esempio

Proviamo queste operazioni in pratica. Innanzitutto, implementazione Java LinkedList: creazione di una LinkedList of Strings, aggiungendo lì 3 elementi. Quindi rimuoverne uno, quindi aggiungerne uno nel mezzo.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<string> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Il risultato dell'esecuzione di questo programma:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]