Java Deque-gränssnitt

Java Deque är en datastruktur som kombinerar en vanlig kö och stack. Du kan lägga till och ta bort element både till huvudet och svansen av Deque. I den "traditionella" kön lägger du till element i slutet av linjen (efter det sista elementet) och tar bort element från köns huvud. Denna princip kallas First In First Out (FIFO) och den fungerar som alla vanliga kunder i verkligheten. I Java Queue är ett gränssnitt, en del av Collections Framework. Det finns också en viktig datastruktur som heter Stack, en lista som fungerar med element i helt omvänd princip, LIFO — sist in, först ut. Det liknar en bunt tallrikar, lägga till eller ta bort är bara möjligt på toppen.

Kö vs Deque

Deque är en ganska konstig typ av kö: du kan lägga till nya element både i svansen och huvudet på linjen. Samma historia med att ta bort: du kan ta bort det sista eller det första elementet från denna struktur. Därför verkar det vara en blandning av Stack och Queue. Namnet "Deque" betyder "Double Ended Queue". "Deque" uttalas som en "lek" med kort och vet du vad? Det är lite likt en riktig kortlek: du kan ta ett kort från botten eller toppen av en sådan kortlek. Vill du lägga till eller ta bort element från båda sidorna av någon linjär struktur? Använd Deque. Java 8 eller nästan vilken annan version som helst stöder det. Föreställ dig en typisk legokloss och enkolumniga "torn" gjorda av klossarna. Du kan lägga till en ny tegelsten på toppen av tornet eller längst ner. Du kan också ta bort en tegelsten från båda sidor. Här har vi ett exempel: vi lägger till alla gula tegelstenar till toppen och alla röda längst ner. Vi kommer snart att demonstrera detta exempel med Java-kod. Så du kan köa och ställa i kö från båda ändarna av en Java Deque, det betyder att du kan använda en Deque som både kö och stack. Läs om Stack i Java: Java Stack 101: Fördjupa dig i Stack Class Läs om Queue in Java: Java Queue Interface och dess implementeringar

Deques funktioner

• Deque i Java är ett gränssnitt, vilka implementeringar ger stöd för en storleksändringsbar array. Så du har en mängd begränsningsfri kapacitet och du kan lägga till nya element enligt dina behov.
• Samtidig åtkomst av flera trådar stöds inte av Deque
• Deque är inte trådsäkert i händelse av frånvaro av extern synkronisering.
• Inga Null-element tillåtna i array-deque.

Deque Java Interface deklaration

public interface Deque<E> extends Queue<E>

Java Deque-metoder

java.util.Deque är ett gränssnitt som utökar Java Queue Interface och representerar en dubbel kö. Så du kan använda alla Java Queue-metoder medan du arbetar med en Deque. Trots att Deque inte utökar Stack-gränssnittet, definierar Deque-gränssnittet metoder som gör att du kan utföra typiska stackoperationer som push , peek och pop .

• boolean add(element) lägger till ett element i svansen av Deque. Returnerar sant vid framgång, kastar ett IllegalStateException om inget utrymme för närvarande är tillgängligt.
• addFirst(element) lägger till ett element till huvudet på Deque.
• addLast(element) lägger till ett element i svansen av Deque.
• offer(element) lägger till ett element i svansen och returnerar en boolean för att förklara om infogningen lyckades.
• offerFirst(element) lägger till ett element i huvudet och returnerar en boolean för att förklara om infogningen lyckades.
• offerLast(element) lägger till ett element i svansen och returnerar en boolean för att förklara om infogningen lyckades.
• iterator() returnerar en iterator för dequen.
• descendingIterator() returnerar en iterator som har omvänd ordning för denna deque.
• push(element) lägger till ett element till huvudet.
• pop(element) tar bort ett element från huvudet och returnerar det.
• removeFirst() tar bort elementet i huvudet.
• removeLast() tar bort elementet vid svansen.
• poll() hämtar och tar bort huvudet på kön som representeras av denna deque (med andra ord, det första elementet i denna deque), eller returnerar null om denna deque är tom.
• pollFirst() hämtar och tar bort det första elementet i denna deque, eller returnerar null om denna deque är tom.
• pollLast() hämtar och tar bort det sista elementet i denna deque, eller returnerar null om denna deque är tom.
• peek() hämtar, men tar inte bort, huvudet på kön som representeras av denna deque (med andra ord, det första elementet i denna deque), eller returnerar null om denna deque är tom.
• peekFirst() hämtar, men tar inte bort, det första elementet i denna deque, eller returnerar null om denna deque är tom.
• peekLast() hämtar, men tar inte bort, det sista elementet i denna deque, eller returnerar null om denna deque är tom.

Här i tabellen nedan är alla metoder indelade efter grupper. Som du kan se finns det många olika metoder att lägga till och ta bort ett element. Till exempel tar både removeFirst() och pop() bort det första elementet från deque. Den andra "kom" från stack. Det betyder att om du bara använder din ArrayDeque som en stack, använd pop() för att ta bort, push() för att lägga till och peek() för att undersöka. Detta gör din kod mer förnuftig för andra utvecklare.

Deque implementeringar

Java Deque är ett gränssnitt och har implementeringar i Java Collections API:

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

Klassen LinkedList använder en dubbellänkad lista internt för att modellera en kö eller en deque. ArrayDeque-klassen lagrar elementen internt i en array. Om antalet element överstiger arrayens volym tilldelas en ny array och alla element flyttas över. Det betyder att ArrayDeque växer med behov.

ArrayDeque klass

Klassen ArrayDeque <E> är en allmän tvåriktad kö, som ärver funktionalitet från klassen AbstractCollection och använder Deque-gränssnittet. ArrayDeque ger möjligheten att använda deque och resizable-array. Inledningsvis initieras arrayen med storlek 16. Den implementeras som en tvåvägskö, där den stöder två pekare, nämligen huvudet och svansen. Den ärver klassen AbstractCollection och implementerar Deque- gränssnittet. De viktiga punkterna om ArrayDeque-klassen är:

• Du kan lägga till eller ta bort element från svansen och huvudet på ArrayDeque
• Null-element är inte tillåtna
• ArrayDeque är inte trådsäkert i avsaknad av extern synkronisering.
• ArrayDeque har inga kapacitetsbegränsningar.

ArrayDeque klass Konstruktörer

• ArrayDeque() skapar en tom kö.
• ArrayDeque (Collection <? Extends E> collection) skapar en kö fylld med samlingselement.
• ArrayDeque (int kapacitet) skapar en kö med initial kapacitetskapacitet . Om du inte anger den ursprungliga kapaciteten är standardkapaciteten 16.

Java Deque Exempel — ArrayDeque

Kommer du ihåg Lego Tower-exemplet från början av artikeln? Låt oss skapa en klass för att bygga torn med en kolumn gjorda av legoklossar. Tegelstenar kan vara röda, gula eller blå. Vår tornbyggnadsregel: vi lägger de röda tegelstenarna till botten och gula tegelstenarna till toppen. Big Java Deque Exempel

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

Här är vår Tower-klass. Vi initierar ett torn. Det initierade tornet beror på mängden röda och gula. Vi kan lägga till tegel i tornet eller ta bort det. Vi lägger till tegel på toppen om den är gul och lägger till den i botten om den är 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 av att köra detta 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

Vänta, va?? Varför är de röda på toppen? Nej, det gör de inte. De skrev bara ut till konsolen från den första (nederst) till den sista (överst). Så om du vill se något som på bilden med klossarna ovan kan du ändra drawTower-metoden för LegoTower-klassen. Det är en väldigt lätt uppgift!

Länkad lista

Listgränssnittet behåller sekvensen för att lägga till objekt och tillåter åtkomst till objektet via index. Deque är en tvåvägskö, och den stöder att lägga till och ta bort element från båda sidor. LinkedList är huvudsakligen känd som en List-implementering, men även denna klass implementerar Deque, och den tillåter oss att skapa en dubbelriktad kö som består av alla objekt inklusive null. LinkedList är en samling element. Vi kan se det i klassens kodkälla, den här gången var uppmärksam på fälten: Här lägger vi till ett exempel, men om du vill lära dig mer om LinkedList, välkommen till denna CodeGym- artikel .

Länkad listimplementering i Java, lägga till och ta bort element. Exempel

Låt oss prova dessa operationer i praktiken. Först, Java LinkedList-implementering: skapa en LinkedList av strängar, lägga till 3 element. Ta sedan bort en och lägg sedan till en i mitten.

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 av att köra detta 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]