Java Deque-interface

Java Deque is een datastructuur die een gewone Queue en Stack combineert. U kunt zowel aan de kop als aan de staart van de Deque elementen toevoegen en verwijderen. In de “traditionele” wachtrij voeg je elementen toe aan de staart van de regel (na het laatste element) en verwijder je elementen aan de kop van de wachtrij. Dit principe wordt First In First Out (FIFO) genoemd en werkt zoals elke gewone klantenlijn in het echte leven. In Java is Queue een interface, een onderdeel van het Collections Framework. Er is ook een belangrijke gegevensstructuur genaamd Stack, een lijst die met elementen werkt volgens het totaal omgekeerde principe, LIFO - last in, first out. Het is vergelijkbaar met een stapel borden, toevoegen of verwijderen kan alleen bovenaan.

Wachtrij versus Deque

Deque is een beetje raar type Queue: je kunt zowel aan de staart als aan de kop van de lijn nieuwe elementen toevoegen. Hetzelfde verhaal met verwijderen: u mag het laatste of het eerste element van deze structuur verwijderen. Daarom lijkt het een mix te zijn van Stack en Queue. De naam "Deque" betekent "Double Ended Queue". "Deque" wordt uitgesproken als een "pak" kaarten en weet je wat? Het lijkt een beetje op een echt kaartspel: je mag een kaart van de onder- of bovenkant van zo'n kaartspel nemen. Wilt u elementen aan beide zijden van een lineaire structuur toevoegen of verwijderen? Gebruik Deque. Java 8 of bijna elke andere versie ondersteunt het. Stel je een typische legosteen voor en 'torens' met één kolom gemaakt van de stenen. Je kunt een nieuwe steen toevoegen aan de bovenkant van de toren of aan de onderkant. Je kunt een steen ook aan beide kanten verwijderen. Hier hebben we een voorbeeld: we voegen alle gele stenen toe aan de bovenkant en alle rode stenen aan de onderkant. We zullen dit voorbeeld binnenkort demonstreren met Java-code. U kunt dus aan beide uiteinden van een Java-deque in- en uit de wachtrij plaatsen, wat betekent dat u een deque zowel als wachtrij als stapel kunt gebruiken. Lees over Stack in Java: Java Stack 101: Duiken in de Stack Class Lees over Queue in Java: Java Queue Interface en zijn implementaties

Deque's kenmerken

• Deque in Java is een interface, waarvan de implementaties de ondersteuning bieden van een aanpasbare array. U beschikt dus over een onbeperkte capaciteit en u kunt naar behoefte nieuwe elementen toevoegen.
• Oncurrente toegang door meerdere threads wordt niet ondersteund door Deque
• Deque is niet thread-safe in geval van afwezigheid van externe synchronisatie.
• Geen Null-elementen toegestaan ​​in array deque.

Deque declaratie Java-interface

public interface Deque<E> extends Queue<E>

Java Deque-methoden

java.util.Deque is een interface die de Java Queue-interface uitbreidt en een dubbele wachtrij vertegenwoordigt. U kunt dus alle Java Queue-methoden gebruiken terwijl u met een Deque werkt. Ondanks dat Deque de Stack-interface niet uitbreidt, definieert de Deque-interface methoden waarmee u typische stack-bewerkingen kunt uitvoeren, zoals push , peek en pop .

• boolean add(element) voegt een element toe aan de staart van de Deque. Retourneert waar bij succes, genereert een IllegalStateException als er momenteel geen ruimte beschikbaar is.
• addFirst(element) voegt een element toe aan de kop van de Deque.
• addLast(element) voegt een element toe aan de staart van de Deque.
• offer(element) voegt een element toe aan de staart en geeft een boolean terug om uit te leggen of het invoegen succesvol was.
• offerFirst(element) voegt een element toe aan de kop en retourneert een booleaanse waarde om uit te leggen of het invoegen succesvol was.
• offerLast(element) voegt een element toe aan de staart en retourneert een booleaanse waarde om uit te leggen of het invoegen succesvol was.
• iterator() retourneert een iterator voor de deque.
• downhillIterator() retourneert een iterator die de omgekeerde volgorde heeft voor deze deque.
• push(element) voegt een element toe aan het hoofd.
• pop(element) verwijdert een element uit het hoofd en geeft het terug.
• removeFirst() verwijdert het element aan de kop.
• removeLast() verwijdert het element aan de staart.
• poll() haalt de kop van de wachtrij die door deze deque wordt vertegenwoordigd op en verwijdert deze (met andere woorden, het eerste element van deze deque), of retourneert null als deze deque leeg is.
• pollFirst() haalt het eerste element van deze deque op en verwijdert deze, of retourneert null als deze deque leeg is.
• pollLast() haalt het laatste element van deze deque op en verwijdert deze, of geeft null terug als deze deque leeg is.
• peek() haalt de kop van de wachtrij die door deze deque wordt vertegenwoordigd op, maar verwijdert deze niet (met andere woorden, het eerste element van deze deque), of retourneert null als deze deque leeg is.
• peekFirst() haalt het eerste element van deze deque op, maar verwijdert het niet, of geeft null terug als deze deque leeg is.
• peekLast() haalt het laatste element van deze deque op, maar verwijdert het niet, of geeft null terug als deze deque leeg is.

Hier in de onderstaande tabel zijn alle methodes onderverdeeld in groepen. Zoals je kunt zien zijn er veel verschillende methodes om een ​​element toe te voegen en te verwijderen. Zowel removeFirst() als pop() verwijderen bijvoorbeeld het eerste element uit deque. De tweede "kwam" van de stapel. Dat betekent dat als u uw ArrayDeque alleen als stapel gebruikt, u pop() gebruikt om te verwijderen, push() om toe te voegen en peek() om te onderzoeken. Dit maakt uw code verstandiger voor andere ontwikkelaars.

Deque-implementaties

Java Deque is een interface en heeft implementaties in Java Collections API:

• java.util.LinkedList //List en Deque implementatie
• java.util.ArrayDeque //Deque-implementatie, Java-bibliotheek

De klasse LinkedList gebruikt intern een dubbel gekoppelde lijst om een ​​wachtrij of een deque te modelleren. De klasse ArrayDeque slaat de elementen intern op in een array. Als het aantal elementen het volume van de array overschrijdt, wordt een nieuwe array toegewezen en worden alle elementen verplaatst. Dat betekent dat ArrayDeque groeit naar behoefte.

ArrayDeque-klasse

De klasse ArrayDeque <E> is een algemene wachtrij in twee richtingen, die functionaliteit overneemt van de klasse AbstractCollection en de Deque-interface gebruikt. ArrayDeque biedt de mogelijkheid om deque en resizable-array te gebruiken. Aanvankelijk wordt de array geïnitialiseerd met grootte 16. Het is geïmplementeerd als een tweerichtingswachtrij, waar het twee aanwijzers ondersteunt, namelijk de kop en de staart. Het erft de klasse AbstractCollection en implementeert de Deque- interface. De belangrijke punten over de klasse ArrayDeque zijn:

• U kunt elementen toevoegen aan of verwijderen uit de staart en de kop van de ArrayDeque
• Null-elementen zijn niet toegestaan
• ArrayDeque is niet thread-safe, bij gebrek aan externe synchronisatie.
• ArrayDeque heeft geen capaciteitsbeperkingen.

ArrayDeque-klasse Constructors

• ArrayDeque() maakt een lege wachtrij.
• ArrayDeque (Collection <? Extends E> collection) maakt een wachtrij gevuld met Collection-collectie-elementen.
• ArrayDeque (int capacity) creëert een wachtrij met initiële capaciteitscapaciteit . Als u de initiële capaciteit niet opgeeft, is de standaardcapaciteit 16.

Java Deque-voorbeeld — ArrayDeque

Herinner je je het Lego Tower-voorbeeld aan het begin van het artikel nog? Laten we een klasse maken om torens met één kolom te bouwen, gemaakt van legostenen. Bakstenen kunnen rood, geel of blauw zijn. Onze torenbouwregel: we plaatsen de rode stenen op de bodem en de gele stenen bovenaan. Big Java Deque-voorbeeld

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

Hier is onze Torenklas. We initiëren een toren. De geïnitieerde toren hangt af van de hoeveelheid rood en geel. We kunnen baksteen aan de toren toevoegen of verwijderen. We voegen baksteen toe aan de bovenkant als deze geel is en aan de onderkant als deze rood is.

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

   }

}

Het resultaat van het uitvoeren van dit 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

Wacht wat?? Waarom staan ​​de roden bovenaan? Nee, dat doen ze niet. Ze zijn zojuist afgedrukt naar de console, beginnend bij de eerste (onder) tot de laatste (boven). Dus als u iets wilt zien zoals op de afbeelding met de stenen hierboven, kunt u de methode drawTower van de klasse LegoTower wijzigen. Het is een zeer gemakkelijke taak!

Gelinkte lijst

De List-interface houdt de volgorde van het toevoegen van items bij en biedt toegang tot het item per index. Deque is een tweerichtingswachtrij en ondersteunt het toevoegen en verwijderen van elementen van beide kanten. LinkedList is vooral bekend als een List-implementatie, maar deze klasse implementeert ook de Deque, en stelt ons in staat om een ​​bidirectionele wachtrij te maken die bestaat uit alle objecten, inclusief null. LinkedList is een verzameling elementen. We kunnen het zien in de codebron van de klas, let deze keer op de velden: Hier voegen we een voorbeeld toe, maar als je meer wilt weten over LinkedList, welkom bij dit CodeGym- artikel .

Implementatie van gekoppelde lijsten in Java, elementen toevoegen en verwijderen. Voorbeeld

Laten we deze bewerkingen in de praktijk uitproberen. Eerst Java LinkedList-implementatie: een LinkedList of Strings maken, daar 3 elementen aan toevoegen. Verwijder er vervolgens een en voeg er dan een in het midden toe.

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

Het resultaat van het uitvoeren van dit 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]