Java Deque este o structură de date care combină o coadă obișnuită și o stivă. Puteți adăuga și elimina elemente atât pe cap, cât și pe coada Deque. În coada „tradițională” adăugați elemente la coada liniei (după ultimul element) și eliminați elemente din capul cozii. Acest principiu se numește First In First Out (FIFO) și funcționează ca orice linie obișnuită de clienți din viața reală. În Java Queue este o interfață, o parte a Cadrului de colecții. Interfață Java Deque - 1 Există, de asemenea, o structură de date importantă numită Stack, o listă care funcționează cu elemente în principiu total invers, LIFO - last in, first out. Este similar cu un teanc de farfurii, adăugarea sau îndepărtarea este posibilă doar în partea de sus. Interfață Java Deque - 2

Coadă vs Deque

Deque este un tip ciudat de coadă: puteți adăuga elemente noi atât la coadă, cât și la capul liniei. Aceeași poveste cu eliminarea: puteți elimina ultimul sau primul element din această structură. Prin urmare, pare a fi un amestec de stivă și coadă. Interfață Java Deque - 3Numele „Deque” înseamnă „Coadă de așteptare dublă”. „Deque” se pronunță ca un „pack” de cărți și știi ce? Este oarecum similar cu un pachet de cărți adevărat: puteți lua o carte din partea de jos sau de sus a unui astfel de pachet. Doriți să adăugați sau să eliminați elemente de pe ambele părți ale unei structuri liniare? Folosește Deque. Java 8 sau aproape orice altă versiune îl acceptă. Imaginați-vă o cărămidă Lego tipică și „turnuri” cu o singură coloană făcute din cărămizi. Puteți adăuga o cărămidă nouă în partea de sus a turnului sau în partea de jos. De asemenea, puteți îndepărta o cărămidă de pe ambele părți. Aici avem un exemplu: adăugăm toate cărămizile galbene în partea de sus și toate roșii în partea de jos. Vom demonstra acest exemplu cu cod Java în curând. Interfață Java Deque - 4Deci, puteți pune și scoate la coadă de la ambele capete ale unui Deque Java, ceea ce înseamnă că puteți utiliza un Deque atât ca coadă, cât și ca stivă. Citiți despre Stack in Java: Java Stack 101: Deving into Stack Class Citiți despre Queue in Java: Java Queue Interface și implementările sale

Caracteristicile lui Deque

  • Deque în Java este o interfață, a cărei implementări oferă suport pentru o matrice redimensionabilă. Astfel, aveți o gamă largă de capacități fără restricții și puteți adăuga elemente noi în funcție de nevoile dvs.
  • Accesul concurent de către mai multe fire de execuție nu este acceptat de Deque
  • Deque nu este thread-safe în cazul absenței sincronizării externe.
  • Nu sunt permise elemente Null în deque matrice.

Declarație Deque Java Interface


public interface Deque<E> extends Queue<E>

Metode Java Deque

java.util.Deque este o interfață care extinde Java Queue Interface și reprezintă o coadă dublă. Deci, puteți utiliza toate metodele Java Queue în timp ce lucrați cu un Deque. În ciuda faptului că Deque nu extinde interfața Stack, interfața Deque definește metode care vă permit să efectuați operațiuni tipice de stivă, cum ar fi push , peek și pop .
  • boolean add(element) adaugă un element la coada Deque. Returnează true la succes, aruncă o IllegalStateException dacă nu există spațiu disponibil în prezent.
  • addFirst(element) adaugă un element la capul Deque.
  • addLast(element) adaugă un element la coada Deque.
  • offer(element) adaugă un element la coadă și returnează un boolean pentru a explica dacă inserarea a avut succes.
  • offerFirst(element) adaugă un element la cap și returnează un boolean pentru a explica dacă inserarea a avut succes.
  • offerLast(element) adaugă un element la coadă și returnează un boolean pentru a explica dacă inserarea a avut succes.
  • iterator() returnează un iterator pentru deque.
  • descendingIterator() returnează un iterator care are ordinea inversă pentru acest deque.
  • push(element) adaugă un element la cap.
  • pop(element) elimină un element din cap și îl returnează.
  • removeFirst() elimină elementul din cap.
  • removeLast() elimină elementul de la coadă.
  • poll() preia și îndepărtează capul de coadă reprezentat de acest deque (cu alte cuvinte, primul element al acestui deque), sau returnează null dacă acest deque este gol.
  • pollFirst() preia și elimină primul element al acestui deque, sau returnează null dacă acest deque este gol.
  • pollLast() preia și elimină ultimul element al acestui deque, sau returnează null dacă acest deque este gol.
  • peek() preia, dar nu elimină, capul cozii reprezentat de acest deque (cu alte cuvinte, primul element al acestui deque), sau returnează null dacă acest deque este gol.
  • peekFirst() preia, dar nu elimină, primul element al acestui deque, sau returnează null dacă acest deque este gol.
  • peekLast() preia, dar nu elimină, ultimul element al acestui deque sau returnează null dacă acest deque este gol.
Aici, în tabelul de mai jos, toate metodele sunt împărțite pe grupuri. După cum puteți vedea, există multe metode diferite de a adăuga și de a elimina un element. De exemplu, atât removeFirst() cât și pop() elimină primul element din deque. Al doilea „a venit” din stivă. Asta înseamnă că dacă folosiți ArrayDeque numai ca stivă, utilizați pop() pentru a elimina, push() pentru a adăuga și peek() pentru a examina. Acest lucru face codul dvs. mai sensibil pentru alți dezvoltatori.
Primul element (cap) Ultimul element (coada)
Operațiune Aruncă excepție Valoare specială Aruncă excepție Valoare specială
Inserare addFirst(e)/push(e) oferFirst(e) addLast(e) oferLast()
Elimina removeFirst()/pop() pollFirst() removeLast() sondajLast()
Examina getFirst() peekFirst()/peek() getLast() peekLast()

Implementări Deque

Java Deque este o interfață și are implementări în API-ul Java Collections:
  • java.util.LinkedList //Implementarea Listă și Deque
  • java.util.ArrayDeque //Implementare Deque, biblioteca Java
Interfață Java Deque - 5Clasa LinkedList folosește o listă dublu legată intern pentru a modela o coadă sau un deque. Clasa ArrayDeque stochează elementele intern într-o matrice. Dacă numărul de elemente depășește volumul matricei, o nouă matrice este alocată și toate elementele sunt mutate. Asta înseamnă că ArrayDeque crește în funcție de nevoi.

Clasa ArrayDeque

Clasa ArrayDeque <E> este o coadă generală în două direcții, care moștenește funcționalitatea din clasa AbstractCollection și utilizează interfața Deque. ArrayDeque oferă facilitatea de a utiliza deque și resizable-array. Inițial, matricea este inițializată cu dimensiunea 16. Este implementată ca o coadă bidirecțională, unde suportă doi pointeri, și anume capul și coada. Moștenește clasa AbstractCollection și implementează interfața Deque . Punctele importante despre clasa ArrayDeque sunt:
  • Puteți adăuga sau elimina elemente din coada și capul ArrayDeque
  • Elementele nule nu sunt permise
  • ArrayDeque nu este thread safe, în absența sincronizării externe.
  • ArrayDeque nu are restricții de capacitate.

Constructorii clasei ArrayDeque

  • ArrayDeque() creează o coadă goală.
  • ArrayDeque (colecția <? Extends E>) creează o coadă plină cu elemente de colecție.
  • ArrayDeque (capacitate int) creează o coadă cu capacitatea inițială a capacității . Dacă nu specificați capacitatea inițială, capacitatea implicită este 16.

Exemplu Java Deque — ArrayDeque

Îți amintești de exemplul turnului Lego de la începutul articolului? Să creăm o clasă pentru a construi turnuri cu o singură coloană din cărămizi Lego. Cărămizile pot fi roșii, galbene sau albastre. Regula noastră de construire a Turnului: punem cărămizile roșii în partea de jos și cărămizile galbene în partea de sus. Big Java Deque Exemplu

//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 +
              '}';
   }
}
Iată clasa noastră Tower. Initiem un turn. Turnul inițiat depinde de cantitatea de roșu și galben. Putem adăuga cărămidă la turn sau o putem elimina. Adăugăm cărămidă deasupra dacă este galbenă și o adăugăm în partea de jos dacă este roșie.

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();

   }

}
Rezultatul rulării acestui program:

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
Stai ce?? De ce sunt roșii în partea de sus? Nu, ei nu. Tocmai au imprimat pe consolă începând de la primul (de jos) până la ultimul (de sus). Deci, dacă doriți să vedeți ceva ca în imaginea cu cărămizile de mai sus, puteți schimba metoda drawTower din clasa LegoTower. Este o sarcină foarte ușoară!

LinkedList

Interfața Listă păstrează secvența de adăugare a articolelor și permite accesul la articol după index. Deque este o coadă bidirecțională și acceptă adăugarea și eliminarea elementelor din ambele părți. Interfață Java Deque - 6LinkedList este cunoscută în principal ca o implementare List, dar și această clasă implementează Deque și ne permite să creăm o coadă bidirecțională constând din orice obiecte, inclusiv null. LinkedList este o colecție de elemente. O putem vedea în sursa de cod a clasei, de data aceasta acordați atenție câmpurilor: Aici adăugăm un exemplu, dar dacă doriți să aflați mai multe despre LinkedList, bine ați venit la acest articol CodeGym .

Implementarea listelor legate în Java, adăugarea și eliminarea elementelor. Exemplu

Să încercăm aceste operațiuni în practică. În primul rând, implementarea Java LinkedList: crearea unei LinkedList de șiruri, adăugând acolo 3 elemente. Apoi scoateți unul, apoi adăugați unul în mijloc.

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);
   }
Rezultatul rulării acestui program:

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]