Java Deque-grensesnitt

Java Deque er en datastruktur som kombinerer en vanlig kø og stabel. Du kan legge til og fjerne elementer både i hodet og på halen av Deque. I den "tradisjonelle" køen legger du til elementer i halen av linjen (etter det siste elementet) og fjerner elementer fra toppen av køen. Dette prinsippet kalles First In First Out (FIFO) og det fungerer som alle vanlige kunder i det virkelige liv. I Java Queue er et grensesnitt, en del av Collections Framework. Det er også en viktig datastruktur kalt Stack, en liste som fungerer med elementer i totalt omvendt prinsipp, LIFO — sist inn, først ut. Det ligner på en stabel med plater, å legge til eller fjerne er kun mulig på toppen.

Kø vs Deque

Deque er en litt merkelig type kø: du kan legge til nye elementer både i halen og hodet på linjen. Den samme historien med fjerning: du kan fjerne det siste eller det første elementet fra denne strukturen. Derfor ser det ut til å være en blanding av Stack og Queue. Navnet "Deque" betyr "Double Ended Queue". "Deque" uttales som en "bunke" med kort, og vet du hva? Det ligner litt på en ekte kortstokk: du kan ta et kort fra bunnen eller toppen av en slik kortstokk. Vil du legge til eller fjerne elementer fra begge sider av en lineær struktur? Bruk Deque. Java 8 eller nesten hvilken som helst annen versjon støtter det. Se for deg en typisk legokloss og "tårn" med én kolonne laget av klossene. Du kan legge til en ny murstein på toppen av tårnet eller til bunnen. Du kan også fjerne en murstein fra begge sider. Her har vi et eksempel: vi legger alle gule klosser til toppen og alle røde til bunnen. Vi vil snart demonstrere dette eksemplet med Java-kode. Så du kan sette i kø og sette i kø fra begge ender av en Java Deque, det betyr at du kan bruke en Deque som både kø og stabel. Les om Stack in Java: Java Stack 101: Delving into the Stack Class Les om Queue in Java: Java Queue Interface og implementeringene av det

Deques funksjoner

• Deque in Java er et grensesnitt, som implementeringer gir støtte for en matrise som kan endres størrelse. Så du har en rekke restriksjonsfri kapasitet, og du kan legge til nye elementer i henhold til dine behov.
• Samtidig tilgang fra flere tråder støttes ikke av Deque
• Deque er ikke trådsikker i tilfelle fravær av ekstern synkronisering.
• Ingen null-elementer tillatt i array-deque.

Deque Java Interface-erklæring

public interface Deque<E> extends Queue<E>

Java Deque-metoder

java.util.Deque er et grensesnitt som utvider Java Queue Interface og representerer en dobbel endt kø. Så du kan bruke alle Java Queue-metodene mens du arbeider med en Deque. Til tross for at Deque ikke utvider Stack-grensesnittet, definerer Deque-grensesnittet metoder som lar deg utføre typiske stackoperasjoner som push , peek og pop .

• boolean add(element) legger til et element i halen av Deque. Returnerer sant ved suksess, kaster et IllegalStateException hvis ingen plass er tilgjengelig for øyeblikket.
• addFirst(element) legger til et element til toppen av Deque.
• addLast(element) legger til et element i halen av Deque.
• offer(element) legger til et element i halen og returnerer en boolsk for å forklare om innsettingen var vellykket.
• offerFirst(element) legger til et element i hodet og returnerer en boolsk for å forklare om innsettingen var vellykket.
• offerLast(element) legger til et element i halen og returnerer en boolsk for å forklare om innsettingen var vellykket.
• iterator() returnerer en iterator for dequen.
• descendingIterator() returnerer en iterator som har omvendt rekkefølge for denne deque.
• push(element) legger til et element til hodet.
• pop(element) fjerner et element fra hodet og returnerer det.
• removeFirst() fjerner elementet ved hodet.
• removeLast() fjerner elementet ved halen.
• poll() henter og fjerner hodet på køen representert av denne deque (med andre ord, det første elementet i denne deque), eller returnerer null hvis denne deque er tom.
• pollFirst() henter og fjerner det første elementet i denne deque, eller returnerer null hvis denne deque er tom.
• pollLast() henter og fjerner det siste elementet i denne deque, eller returnerer null hvis denne deque er tom.
• peek() henter, men fjerner ikke, lederen av køen representert av denne deque (med andre ord, det første elementet i denne deque), eller returnerer null hvis denne deque er tom.
• peekFirst() henter, men fjerner ikke, det første elementet i denne deque, eller returnerer null hvis denne deque er tom.
• peekLast() henter, men fjerner ikke, det siste elementet i denne dequen, eller returnerer null hvis denne dequen er tom.

Her i tabellen nedenfor er alle metoder delt inn etter grupper. Som du kan se er det mange forskjellige metoder for å legge til og fjerne et element. For eksempel fjerner både removeFirst() og pop() det første elementet fra deque. Den andre "kom" fra stabelen. Det betyr at hvis du bare bruker ArrayDeque som en stabel, bruk pop() for å fjerne, push() for å legge til og kikke() for å undersøke. Dette gjør koden din mer fornuftig for andre utviklere.

Deque-implementeringer

Java Deque er et grensesnitt og har implementeringer i Java Collections API:

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

LinkedList-klassen bruker en dobbeltlenket liste internt for å modellere en kø eller en deque. ArrayDeque-klassen lagrer elementene internt i en matrise. Hvis antallet elementer overstiger volumet til matrisen, tildeles en ny matrise, og alle elementene flyttes over. Det betyr at ArrayDeque vokser etter behov.

ArrayDeque-klassen

ArrayDeque <E> -klassen er en generell to-retningskø, som arver funksjonalitet fra AbstractCollection-klassen og bruker Deque-grensesnittet. ArrayDeque gir muligheten til å bruke deque og resizable-array. Til å begynne med initialiseres matrisen med størrelse 16. Den implementeres som en toveiskø, hvor den støtter to pekere, nemlig hodet og halen. Den arver AbstractCollection- klassen og implementerer Deque- grensesnittet. De viktige punktene om ArrayDeque-klassen er:

• Du kan legge til eller fjerne elementer fra halen og hodet på ArrayDeque
• Null-elementer er ikke tillatt
• ArrayDeque er ikke trådsikker, i fravær av ekstern synkronisering.
• ArrayDeque har ingen kapasitetsbegrensninger.

ArrayDeque klasse konstruktører

• ArrayDeque() oppretter en tom kø.
• ArrayDeque (Collection <? Extends E> collection) lager en kø fylt med samlingselementer.
• ArrayDeque (int kapasitet) oppretter en kø med innledende kapasitetskapasitet . Hvis du ikke spesifiserer den opprinnelige kapasiteten, er standardkapasiteten 16.

Java Deque Eksempel — ArrayDeque

Husker du Lego Tower-eksemplet fra begynnelsen av artikkelen? La oss lage en klasse for å bygge tårn med én kolonne laget av legoklosser. Murstein kan være rød, gul eller blå. Tårnbyggeregelen vår: vi legger de røde klossene til bunnen og gule klossene til toppen. Eksempel på stort 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 +
              '}';
   }
}

Her er tårnklassen vår. Vi setter i gang et tårn. Det initierte tårnet avhenger av mengden røde og gule. Vi kan legge murstein til tårnet eller fjerne det. Vi legger murstein til toppen hvis den er gul og legger den til bunnen 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 av å kjøre dette programmet:

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, hva?? Hvorfor er de røde på toppen? Nei, det gjør de ikke. De skrev nettopp ut til konsollen fra den første (nederst) til den siste (øverst). Så hvis du vil se noe som på bildet med klossene ovenfor, kan du endre drawTower-metoden til LegoTower-klassen. Det er en veldig enkel oppgave!

LinkedList

Liste-grensesnittet beholder sekvensen for å legge til elementer og gir tilgang til elementet etter indeks. Deque er en toveiskø, og den støtter å legge til og fjerne elementer fra begge sider. LinkedList er hovedsakelig kjent som en List-implementering, men også denne klassen implementerer Deque, og den lar oss lage en toveis kø bestående av alle objekter inkludert null. LinkedList er en samling av elementer. Vi kan se det i kodekilden til klassen, denne gangen ta hensyn til feltene: Her legger vi til ett eksempel, men hvis du vil lære mer om LinkedList, velkommen til denne CodeGym- artikkelen .

Koblet listeimplementering i Java, legge til og fjerne elementer. Eksempel

La oss prøve disse operasjonene i praksis. Først, Java LinkedList-implementering: lage en LinkedList of Strings, og legge til 3 elementer. Fjern deretter en, og legg deretter til 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 av å kjøre dette programmet:

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]