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
publicinterfaceDeque<E>extendsQueue<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.
Eerste element (hoofd)
Laatste element (staart)
Operatie
Gooit uitzondering
Speciale waarde
Gooit uitzondering
Speciale waarde
Plaatsing
addFirst(e)/push(e)
aanbiedingeerste(e)
addLast(e)
aanbiedingLaatste()
Verwijderen
verwijderEerste()/pop()
peilingEerst()
verwijderLaatste()
peilingLaatste()
Onderzoeken
haaleerst()
peekFirst()/peek()
word laatste()
kijkjeLaatste()
Deque-implementaties
Java Deque is een interface en heeft implementaties in Java Collections API:
java.util.LinkedList //List en Deque implementatie
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 colorspublicenumColor{RED,YELLOW,BLUE;}//class for the standard Lego Brick. You can connect or disconnect the Brick, it has colorpublicclassLegoBrick{Color color;boolean isConnected;publicvoidconnect(){System.out.println("This brick is connected");this.isConnected =true;}publicvoiddisconnect(){System.out.println("Disconnected");
isConnected =false;}publicLegoBrick(Color color,boolean isConnected){this.color = color;this.isConnected = isConnected;}publicColorgetColor(){return color;}publicbooleanisConnected(){return isConnected;}@OverridepublicStringtoString(){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.
importjava.util.ArrayDeque;publicclassLegoTower{ArrayDeque<LegoBrick> myTower;int quantityOfReds;int quantityOfYellows;publicvoidaddBrickToTower(LegoBrick newLegoBrick){if(newLegoBrick.getColor()==Color.YELLOW){this.myTower.offerLast(newLegoBrick);
quantityOfYellows++;}//we can use addFirst(e)/push(e) instead of offerFirst hereif(newLegoBrick.getColor()==Color.RED){
myTower.offerFirst(newLegoBrick);
quantityOfReds++;}}publicvoid removeBrickFromTower (LegoBrick legoBrick){if(legoBrick.getColor()==Color.YELLOW){this.myTower.removeLast();
quantityOfYellows--;}if(legoBrick.getColor()==Color.RED){
myTower.removeFirst();
quantityOfReds--;}
legoBrick.isConnected =false;}publicLegoTower(int quantityOfReds,int quantityOfYellows){
myTower =newArrayDeque<>();this.quantityOfReds = quantityOfReds;this.quantityOfYellows = quantityOfYellows;for(int i =0; i < quantityOfReds; i++){LegoBrick redLegoBrick =newLegoBrick(Color.RED,false);
myTower.addFirst(redLegoBrick);
redLegoBrick.isConnected =true;}for(int i =0; i < quantityOfYellows; i++){LegoBrick yellowLegoBrick =newLegoBrick(Color.YELLOW,false);
myTower.addLast(yellowLegoBrick);
yellowLegoBrick.isConnected =true;}}publicvoidsetMyTower(ArrayDeque<legobrick> myTower){this.myTower = myTower;}publicvoidsetQuantityOfReds(int quantityOfReds){this.quantityOfReds = quantityOfReds;}publicvoidsetQuantityOfYellows(int quantityOfYellows){this.quantityOfYellows = quantityOfYellows;}@OverridepublicStringtoString(){return"LegoTower{"+"myTower="+ myTower +", quantityOfReds="+ quantityOfReds +", quantityOfYellows="+ quantityOfYellows +'}';}publicvoiddrawTower(){for(LegoBrick i : myTower){System.out.println(i.color);}}}publicclassMain{publicstaticvoidmain(String[] args){LegoBrick legoBrick1 =newLegoBrick(Color.YELLOW,false);
legoBrick1.connect();System.out.println(legoBrick1.toString());
legoBrick1.disconnect();System.out.println(legoBrick1.toString());LegoBrick legoBrick2 =newLegoBrick(Color.YELLOW,false);LegoBrick legoBrick3 =newLegoBrick(Color.RED,false);LegoBrick legoBrick4 =newLegoBrick(Color.RED,false);LegoBrick legoBrick5 =newLegoBrick(Color.YELLOW,false);LegoTower legoTower =newLegoTower(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.
publicclassMyLinkedTest{publicstaticvoidmain(String[] args){String h1 ="my";String h2 ="favorite";String h3 ="book";// LinkedList implementation in JavaLinkedList<string> linkedList =newLinkedList();
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]
0
Opmerkingen
Populair
Nieuw
Oud
Je moet ingelogd zijn om opmerkingen te kunnen maken