Java Deque Interface

Java Deque er en datastruktur, der kombinerer en almindelig kø og stak. Du kan tilføje og fjerne elementer både til hovedet og bagenden af ​​Deque. I den "traditionelle" kø tilføjer du elementer til linjens hale (efter det sidste element) og fjerner elementer fra køens hoved. Dette princip kaldes First In First Out (FIFO), og det fungerer som enhver almindelig kundekreds i det virkelige liv. I Java Queue er en grænseflade, en del af Collections Framework. Der er også en vigtig datastruktur kaldet Stack, en liste, der arbejder med elementer i et totalt omvendt princip, LIFO — sidst ind, først ud. Det ligner en stak plader, tilføjelse eller fjernelse er kun muligt øverst.

Kø vs Deque

Deque er en lidt underlig type kø: du kan tilføje nye elementer både til halen og hovedet af linjen. Den samme historie med fjernelse: du kan fjerne det sidste eller det første element fra denne struktur. Derfor ser det ud til at være en blanding af stak og kø. Navnet "Deque" betyder "Double Ended Queue". "Deque" udtales som et "dæk" af kort, og ved du hvad? Det minder lidt om et rigtigt sæt kort: du kan tage et kort fra bunden eller toppen af ​​et sådant sæt. Vil du tilføje eller fjerne elementer fra begge sider af en lineær struktur? Brug Deque. Java 8 eller næsten enhver anden version understøtter det. Forestil dig en typisk legoklods og en-søjle "tårne" lavet af klodserne. Du kan tilføje en ny klods til toppen af ​​tårnet eller til bunden. Du kan også fjerne en mursten fra begge sider. Her har vi et eksempel: vi tilføjer alle gule klodser til toppen og alle røde til bunden. Vi vil snart demonstrere dette eksempel med Java-kode. Så du kan sætte i kø og sætte i kø fra begge ender af en Java Deque, det betyder, at du kan bruge en Deque som både kø og stak. Læs om Stack in Java: Java Stack 101: Delving into the Stack Class Læs om Queue in Java: Java Queue Interface og dets implementeringer

Deques funktioner

• Deque i Java er en grænseflade, hvilke implementeringer understøtter et array, der kan ændres størrelse. Så du har en række begrænsningsfri kapacitet, og du kan tilføje nye elementer efter dine behov.
• Samtidig adgang fra flere tråde understøttes ikke af Deque
• Deque er ikke trådsikker i tilfælde af fravær af ekstern synkronisering.
• Ingen nul-elementer tilladt i array-deque.

Deque Java Interface erklæring

public interface Deque<E> extends Queue<E>

Java Deque-metoder

java.util.Deque er en grænseflade, der udvider Java Queue Interface og repræsenterer en dobbeltkø. Så du kan bruge alle Java Queue-metoderne, mens du arbejder med en Deque. På trods af at Deque ikke udvider Stack-grænsefladen, definerer Deque-grænsefladen metoder, der sætter dig i stand til at udføre typiske stak-operationer såsom push , peek og pop .

• boolean add(element) tilføjer et element til halen af ​​Deque. Returnerer sand ved succes, kaster en IllegalStateException, hvis der ikke er plads i øjeblikket.
• addFirst(element) tilføjer et element til hovedet af Deque.
• addLast(element) tilføjer et element til halen af ​​Deque.
• offer(element) tilføjer et element til halen og returnerer en boolean for at forklare, om indsættelsen var vellykket.
• offerFirst(element) tilføjer et element til hovedet og returnerer en boolean for at forklare, om indsættelsen lykkedes.
• offerLast(element) tilføjer et element til halen og returnerer en boolean for at forklare, om indsættelsen var vellykket.
• iterator() returnerer en iterator for deque.
• descendingIterator() returnerer en iterator, der har den omvendte rækkefølge for denne deque.
• push(element) tilføjer et element til hovedet.
• pop(element) fjerner et element fra hovedet og returnerer det.
• removeFirst() fjerner elementet i hovedet.
• removeLast() fjerner elementet ved halen.
• poll() henter og fjerner hovedet i køen repræsenteret af denne deque (med andre ord, det første element i denne deque), eller returnerer null, hvis denne deque er tom.
• pollFirst() henter og fjerner det første element i denne deque, eller returnerer null, hvis denne deque er tom.
• pollLast() henter og fjerner det sidste element i denne deque, eller returnerer null, hvis denne deque er tom.
• peek() henter, men fjerner ikke, køens hoved, repræsenteret af denne deque (med andre ord, det første element i denne deque), eller returnerer null, hvis denne deque er tom.
• peekFirst() henter, men fjerner ikke, det første element i denne deque, eller returnerer null, hvis denne deque er tom.
• peekLast() henter, men fjerner ikke, det sidste element i denne deque, eller returnerer null, hvis denne deque er tom.

Her i tabellen nedenfor er alle metoder inddelt efter grupper. Som du kan se, er der mange forskellige metoder til at tilføje og fjerne et element. For eksempel fjerner både removeFirst() og pop() det første element fra deque. Den anden "kom" fra stakken. Det betyder, at hvis du kun bruger din ArrayDeque som en stack, skal du bruge pop() for at fjerne, push() for at tilføje og peek() for at undersøge. Dette gør din kode mere fornuftig for andre udviklere.

Deque implementeringer

Java Deque er en grænseflade og har implementeringer i Java Collections API:

• java.util.LinkedList //List og Deque implementering
• java.util.ArrayDeque //Deque-implementering, Java-bibliotek

LinkedList-klassen bruger en dobbelt-linket liste internt til at modellere en kø eller en deque. ArrayDeque-klassen gemmer elementerne internt i et array. Hvis antallet af elementer overstiger arrayets volumen, tildeles et nyt array, og alle elementer flyttes over. Det betyder, at ArrayDeque vokser efter behov.

ArrayDeque klasse

ArrayDeque <E> -klassen er en generel to-retningskø, der arver funktionalitet fra klassen AbstractCollection og bruger Deque-grænsefladen. ArrayDeque giver mulighed for at bruge deque og resizable-array. Indledningsvis initialiseres arrayet med størrelse 16. Det implementeres som en tovejskø, hvor det understøtter to pointere, nemlig hovedet og halen. Det arver AbstractCollection- klassen og implementerer Deque- grænsefladen. De vigtige punkter om ArrayDeque-klassen er:

• Du kan tilføje eller fjerne elementer fra halen og hovedet af ArrayDeque
• Null-elementer er ikke tilladt
• ArrayDeque er ikke trådsikkert i mangel af ekstern synkronisering.
• ArrayDeque har ingen kapacitetsbegrænsninger.

ArrayDeque klasse konstruktører

• ArrayDeque() opretter en tom kø.
• ArrayDeque (Collection <? Extends E> collection) opretter en kø fyldt med Collection collection-elementer.
• ArrayDeque (int kapacitet) opretter en kø med initial kapacitetskapacitet . Hvis du ikke angiver den oprindelige kapacitet, er standardkapaciteten 16.

Java Deque Eksempel — ArrayDeque

Husker du Lego Tower-eksemplet fra begyndelsen af ​​artiklen? Lad os oprette en klasse til at bygge tårne ​​med én kolonne lavet af legoklodser. Mursten kan være røde, gule eller blå. Vores tårnbygningsregel: vi sætter de røde klodser til bunden og gule klodser til toppen. Big Java Deque Eksempel

//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 +
              '}';
   }
}

Her er vores Tower-klasse. Vi igangsætter et tårn. Det igangsatte tårn afhænger af mængden af ​​røde og gule farver. Vi kan tilføje mursten til tårnet eller fjerne det. Vi tilføjer mursten til toppen, hvis den er gul, og tilføjer den til bunden, hvis den er rød.

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

   }

}

Resultatet af at køre dette 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

Vent, hvad?? Hvorfor er de røde på toppen? Nej, det gør de ikke. De har lige printet ud til konsollen fra den første (nederst) til den sidste (øverst). Så hvis du vil se noget som på billedet med klodserne ovenfor, kan du ændre drawTower-metoden i LegoTower-klassen. Det er en meget nem opgave!

LinkedList

Listegrænsefladen bevarer rækkefølgen af ​​tilføjelse af elementer og giver adgang til elementet efter indeks. Deque er en to-vejs kø, og den understøtter tilføjelse og fjernelse af elementer fra begge sider. LinkedList er hovedsageligt kendt som en List-implementering, men også denne klasse implementerer Deque, og den giver os mulighed for at oprette en tovejskø bestående af alle objekter inklusive null. LinkedList er en samling af elementer. Vi kan se det i klassens kodekilde, denne gang skal du være opmærksom på felterne: Her tilføjer vi et eksempel, men hvis du vil lære mere om LinkedList, så velkommen til denne CodeGym- artikel .

Linket listeimplementering i Java, tilføjelse og fjernelse af elementer. Eksempel

Lad os prøve disse operationer af i praksis. Først Java LinkedList implementering: oprettelse af en LinkedList af strenge, tilføjelse af 3 elementer. Fjern derefter en, og tilføj derefter en i midten.

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

Resultatet af at køre dette 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]