Java Deque felület

A Java Deque egy olyan adatstruktúra, amely egy közönséges Queue-t és Stack-et egyesít. A Deque fejéhez és farkához is hozzáadhat és eltávolíthat elemeket. A „hagyományos” sorban elemeket ad hozzá a sor végéhez (az utolsó elem után), és eltávolít elemeket a sor fejéből. Ezt az elvet First In First Out-nak (FIFO) hívják, és úgy működik, mint a való életben minden szokásos ügyfélkör. A Java Queue egy interfész, a Collections Framework része. Van egy fontos adatstruktúra is, a Stack, egy lista, amely teljesen fordított elven működik elemekkel, a LIFO – utolsó be, első ki. Hasonló egy köteg tányérhoz, hozzáadás vagy eltávolítás csak a tetején lehetséges.

Queue vs Deque

A Deque egy furcsa típusú Queue: a sor végéhez és fejéhez is hozzáadhat új elemeket. Ugyanez a történet az eltávolítással: eltávolíthatja az utolsó vagy az első elemet ebből a struktúrából. Ezért úgy tűnik, hogy a Stack és a Queue keveréke. A „Deque” név jelentése „kétvégű sor”. A „Deque” szót úgy ejtik, mint egy „kártyapakli”, és tudod mit? Némileg hasonlít egy valódi kártyapaklihoz: egy ilyen pakli aljáról vagy tetejéről is vehet egy kártyát. Szeretnél elemeket hozzáadni vagy eltávolítani valamelyik lineáris struktúra mindkét oldaláról? Használd a Deque-t. A Java 8 vagy szinte bármely más verzió támogatja. Képzeljünk el egy tipikus legókockát és a kockákból készült egyoszlopos „tornyokat”. Új téglát rakhatsz a torony tetejére vagy aljára. Mindkét oldalról eltávolíthat egy téglát. Itt van egy példa: minden sárga téglát adunk a tetejére, és minden pirosat az aljára. Ezt a példát hamarosan Java kóddal is bemutatjuk. Tehát a Java Deque mindkét végéről sorba állíthat és törölhet sorból, ami azt jelenti, hogy a Deque-t sorként és veremként is használhatja. Olvasson a Java veremről: Java Stack 101: elmélyülés a verem osztályba Olvasson a Java sorról: Java Queue Interface és megvalósításai

Deque jellemzői

• A Deque in Java egy interfész, amelynek megvalósításai támogatják az átméretezhető tömböt. Így egy sor korlátozásmentes kapacitással rendelkezik, és új elemeket adhat hozzá igényei szerint.
• A Deque nem támogatja a több szálon keresztüli egyidejű hozzáférést
• A Deque külső szinkronizálás hiánya esetén nem szálbiztos.
• A tömb deque-ben nem megengedettek Null elemek.

Deque Java Interface deklaráció

public interface Deque<E> extends Queue<E>

Java Deque Methods

A java.util.Deque egy interfész, amely kiterjeszti a Java Queue Interface-t, és egy kétvégű várólista. Így az összes Java Queue metódust használhatja, miközben a Deque-vel dolgozik. Annak ellenére, hogy a Deque nem terjeszti ki a Stack felületet, a Deque felület olyan módszereket határoz meg, amelyek lehetővé teszik a tipikus veremműveletek elvégzését, például a push , a peek és a pop .

• A boolean add(element) hozzáad egy elemet a Deque végéhez. Siker esetén igazat ad vissza, IllegalStateException kivételt dob, ha jelenleg nincs szabad hely.
• Az addFirst(elem) hozzáad egy elemet a Deque fejlécéhez.
• Az addLast(elem) hozzáad egy elemet a Deque végéhez.
• Az offer(element) hozzáad egy elemet a véghez, és egy logikai értéket ad vissza, hogy megmagyarázza, hogy a beillesztés sikeres volt-e.
• Az offerFirst(element) hozzáad egy elemet a fejhez, és egy logikai értéket ad vissza, hogy megmagyarázza, hogy a beillesztés sikeres volt-e.
• Az offerLast(element) hozzáad egy elemet a véghez, és egy logikai értéket ad vissza annak magyarázatára, hogy a beillesztés sikeres volt-e.
• Az iterator() egy iterátort ad vissza a deque-hez.
• A descendingIterator() egy olyan iterátort ad vissza, amelynek a sorrendje fordított a deque-hez.
• push(elem) hozzáad egy elemet a fejhez.
• pop(elem) eltávolít egy elemet a fejből, és visszaadja.
• RemoveFirst() eltávolítja az elemet a fejből.
• RemoveLast() eltávolítja az elemet a végén.
• A poll() lekéri és eltávolítja a deque által képviselt sor fejét (más szóval ennek a deque-nek az első elemét), vagy nullát ad vissza, ha ez a deque üres.
• A pollFirst() lekéri és eltávolítja ennek a deque-nek az első elemét, vagy nullát ad vissza, ha ez a deque üres.
• A pollLast() lekéri és eltávolítja a deque utolsó elemét, vagy nullát ad vissza, ha ez a deque üres.
• A peek() lekéri, de nem távolítja el a deque által képviselt sor fejét (más szóval ennek a deque-nek az első elemét), vagy nullát ad vissza, ha ez a deque üres.
• A peekFirst() lekéri, de nem távolítja el ennek a deque-nek az első elemét, vagy nullát ad vissza, ha ez a deque üres.
• A peekLast() lekéri, de nem távolítja el a deque utolsó elemét, vagy nullát ad vissza, ha ez a deque üres.

Az alábbi táblázatban az összes módszer csoportokra van osztva. Amint láthatja, számos különböző módszer létezik egy elem hozzáadására és eltávolítására. Például a removeFirst() és a pop() is eltávolítja az első elemet a deque-ből. A második veremből „jött”. Ez azt jelenti, hogy ha csak veremként használja az ArrayDeque-et, használja a pop()-t az eltávolításhoz, a push()-t a hozzáadáshoz és a peek()-et a vizsgálathoz. Ez értelmesebbé teszi a kódot a többi fejlesztő számára.

Deque megvalósítások

A Java Deque egy interfész, és a Java Collections API-ban van implementálva:

• java.util.LinkedList //List és Deque megvalósítás
• java.util.ArrayDeque //Deque implementáció, Java könyvtár

A LinkedList osztály belsőleg duplán csatolt listát használ a várólista vagy a deque-re modellezéséhez. Az ArrayDeque osztály belül tárolja az elemeket egy tömbben. Ha az elemek száma meghaladja a tömb térfogatát, akkor új tömb kerül kiosztásra, és az összes elem átkerül. Ez azt jelenti, hogy az ArrayDeque az igények szerint nő.

ArrayDeque osztály

Az ArrayDeque <E> osztály egy általános kétirányú várólista, amely az AbstractCollection osztálytól örökli a funkcionalitást, és a Deque felületet használja. Az ArrayDeque lehetőséget biztosít a deque és az átméretezhető tömb használatára. Kezdetben a tömb inicializálása 16-os mérettel történik. Kétirányú várakozási sorként valósítják meg, ahol két mutatót támogat, nevezetesen a fejet és a farkot. Megörökli az AbstractCollection osztályt, és megvalósítja a Deque felületet. Az ArrayDeque osztály legfontosabb pontjai a következők:

• Hozzáadhat vagy eltávolíthat elemeket az ArrayDeque végéből és fejéből
• Null elemek nem megengedettek
• Az ArrayDeque külső szinkronizálás hiányában nem szálbiztos.
• Az ArrayDeque-nek nincsenek kapacitáskorlátozásai.

ArrayDeque osztálykonstruktorok

• Az ArrayDeque() üres sort hoz létre.
• Az ArrayDeque (Collection <? Extends E> gyűjtemény) létrehoz egy sort, amely tele van Collection gyűjtemény elemekkel.
• Az ArrayDeque (int kapacitás) egy sort hoz létre kezdeti kapacitáskapacitással . Ha nem adja meg a kezdeti kapacitást, az alapértelmezett kapacitás 16.

Java Deque példa – ArrayDeque

Emlékszel a Lego Tower példára a cikk elején? Hozzunk létre egy osztályt Lego kockákból készült egyoszlopos tornyok építéséhez. A tégla lehet piros, sárga vagy kék. Toronyépítési szabályunk: a vörös téglát az aljára, a sárga téglát a tetejére tesszük. Big Java Deque példa

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

Itt van a Tower osztályunk. Tornyot kezdeményezünk. A beavatott torony a vörösek és sárgák mennyiségétől függ. Téglát rakhatunk a toronyba, vagy eltávolíthatjuk. A tetejére téglát teszünk, ha sárga, az aljára, ha piros.

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

   }

}

A program futtatásának eredménye:

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árj, mi?? Miért vannak a pirosak a tetején? Nem, nem. Csak kinyomtatták a konzolra az elsőtől (alulról) az utolsóig (felsőig). Tehát ha valami olyasmit szeretne látni, mint a képen a fenti kockákkal, akkor módosíthatja a LegoTower osztály drawTower metódusát. Ez egy nagyon könnyű feladat!

LinkedList

A Lista felület megtartja az elemek hozzáadásának sorrendjét, és lehetővé teszi az elemekhez való hozzáférést indexenként. A Deque egy kétirányú várólista, amely mindkét oldalról támogatja az elemek hozzáadását és eltávolítását. A LinkedList főként List megvalósításként ismert, de ez az osztály is megvalósítja a Deque-t, és lehetővé teszi számunkra, hogy kétirányú sort hozzunk létre, amely bármilyen objektumból áll, beleértve a nullát is. A LinkedList elemek gyűjteménye. Az osztály kódforrásában láthatjuk, ezúttal figyeljünk a mezőkre: Ide adunk egy példát, de ha többet szeretne megtudni a LinkedListről, üdvözöljük ebben a CodeGym cikkben .

Linkelt lista megvalósítása Java nyelven, elemek hozzáadása és eltávolítása. Példa

Próbáljuk ki ezeket a műveleteket a gyakorlatban. Először is, Java LinkedList megvalósítás: hozzon létre egy LinkedList of Strings listát, és adjon hozzá 3 elemet. Ezután vegyen ki egyet, majd tegyen egyet a közepébe.

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

A program futtatásának eredménye:

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]