Java Deque-Schnittstelle

Java Deque ist eine Datenstruktur, die eine gewöhnliche Warteschlange und einen Stapel kombiniert. Sie können sowohl am Kopf als auch am Ende des Deque Elemente hinzufügen und entfernen. In der „traditionellen“ Warteschlange fügen Sie Elemente am Ende der Zeile (nach dem letzten Element) hinzu und entfernen Elemente am Anfang der Warteschlange. Dieses Prinzip wird First In First Out (FIFO) genannt und funktioniert wie jede normale Kundenlinie im wirklichen Leben. In Java ist Queue eine Schnittstelle, ein Teil des Collections Framework. Es gibt auch eine wichtige Datenstruktur namens Stack, eine Liste, die mit Elementen nach dem völlig umgekehrten Prinzip LIFO arbeitet – last in, first out. Es ähnelt einem Tellerstapel, das Hinzufügen oder Entfernen ist nur von oben möglich.

Warteschlange gegen Deque

Deque ist eine etwas seltsame Art von Warteschlange: Sie können sowohl am Ende als auch am Kopf der Zeile neue Elemente hinzufügen. Das Gleiche gilt für das Entfernen: Sie können das letzte oder das erste Element aus dieser Struktur entfernen. Daher scheint es sich um eine Mischung aus Stack und Queue zu handeln. Der Name „Deque“ bedeutet „Doppelendige Warteschlange“. „Deque“ wird wie ein „Kartenspiel“ ausgesprochen, und wissen Sie was? Es ähnelt in gewisser Weise einem echten Kartenspiel: Sie können eine Karte von der Unterseite oder der Oberseite eines solchen Kartenspiels nehmen. Möchten Sie Elemente auf beiden Seiten einer linearen Struktur hinzufügen oder entfernen? Benutze Deque. Java 8 oder fast jede andere Version unterstützt es. Stellen Sie sich einen typischen Legostein und einsäulige „Türme“ aus den Steinen vor. Sie können oben oder unten am Turm einen neuen Stein anbringen. Sie können einen Ziegel auch von beiden Seiten entfernen. Hier haben wir ein Beispiel: Wir fügen alle gelben Steine ​​oben und alle roten Steine ​​unten hinzu. Wir werden dieses Beispiel bald mit Java-Code demonstrieren. Sie können also von beiden Enden einer Java-Deque-Warteschlange aus in die Warteschlange ein- und aussteigen, das heißt, Sie können eine Deque sowohl als Warteschlange als auch als Stapel verwenden. Lesen Sie mehr über Stack in Java: Java Stack 101: Eintauchen in die Stack-Klasse. Lesen Sie mehr über Queue in Java: Java Queue Interface und seine Implementierungen

Deques Gesichtszüge

• Deque ist in Java eine Schnittstelle, deren Implementierungen die Unterstützung eines skalierbaren Arrays bieten. So verfügen Sie über ein uneingeschränktes Kapazitätsangebot und können je nach Bedarf neue Elemente hinzufügen.
• Der gleichzeitige Zugriff durch mehrere Threads wird von Deque nicht unterstützt
• Deque ist nicht threadsicher, wenn keine externe Synchronisierung erfolgt.
• In der Array-Deque sind keine Nullelemente zulässig.

Deque Java Interface-Deklaration

public interface Deque<E> extends Queue<E>

Java-Deque-Methoden

java.util.Deque ist eine Schnittstelle, die die Java-Warteschlangenschnittstelle erweitert und eine doppelendige Warteschlange darstellt. Sie können also alle Java Queue-Methoden verwenden, während Sie mit einer Deque arbeiten. Obwohl Deque die Stack-Schnittstelle nicht erweitert, definiert die Deque-Schnittstelle Methoden, die es Ihnen ermöglichen, typische Stack-Operationen wie push , peek und pop auszuführen .

• boolean add(element) fügt ein Element zum Ende der Deque hinzu. Gibt bei Erfolg „true“ zurück und löst eine IllegalStateException aus, wenn derzeit kein Speicherplatz verfügbar ist.
• addFirst(element) fügt dem Kopf der Deque ein Element hinzu.
• addLast(element) fügt ein Element zum Ende der Deque hinzu.
• offer(element) fügt dem Ende ein Element hinzu und gibt einen booleschen Wert zurück, um zu erklären, ob die Einfügung erfolgreich war.
• offerFirst(element) fügt dem Kopf ein Element hinzu und gibt einen booleschen Wert zurück, um zu erklären, ob die Einfügung erfolgreich war.
• offerLast(element) fügt dem Ende ein Element hinzu und gibt einen booleschen Wert zurück, um zu erklären, ob die Einfügung erfolgreich war.
• iterator() gibt einen Iterator für die Doppelschlange zurück.
• DescendingIterator() gibt einen Iterator zurück, der für diese Deque die umgekehrte Reihenfolge hat.
• push(element) fügt dem Kopf ein Element hinzu.
• pop(element) entfernt ein Element aus dem Kopf und gibt es zurück.
• removeFirst() entfernt das Element am Kopf.
• removeLast() entfernt das Element am Ende.
• poll() ruft den Kopf der durch diese Deque repräsentierten Warteschlange ab und entfernt ihn (mit anderen Worten: das erste Element dieser Deque) oder gibt null zurück, wenn diese Deque leer ist.
• pollFirst() ruft das erste Element dieser Deque ab und entfernt es oder gibt null zurück, wenn diese Deque leer ist.
• pollLast() ruft das letzte Element dieser Deque ab und entfernt es oder gibt null zurück, wenn diese Deque leer ist.
• peek() ruft den Kopf der durch diese Deque dargestellten Warteschlange (mit anderen Worten das erste Element dieser Deque) ab, entfernt ihn jedoch nicht, oder gibt null zurück, wenn diese Deque leer ist.
• peekFirst() ruft das erste Element dieser Deque ab, entfernt es jedoch nicht, oder gibt null zurück, wenn diese Deque leer ist.
• peekLast() ruft das letzte Element dieser Deque ab, entfernt es jedoch nicht, oder gibt null zurück, wenn diese Deque leer ist.

Hier in der Tabelle unten sind alle Methoden nach Gruppen unterteilt. Wie Sie sehen, gibt es viele verschiedene Methoden zum Hinzufügen und Entfernen eines Elements. Beispielsweise entfernen sowohl „removeFirst()“ als auch „pop()“ das erste Element aus der Deque. Der zweite „kam“ vom Stapel. Das heißt, wenn Sie Ihre ArrayDeque nur als Stapel verwenden, verwenden Sie pop() zum Entfernen, push() zum Hinzufügen und peek() zum Untersuchen. Dadurch wird Ihr Code für andere Entwickler sinnvoller.

Deque-Implementierungen

Java Deque ist eine Schnittstelle und verfügt über Implementierungen in der Java Collections API:

• java.util.LinkedList //List- und Deque-Implementierung
• java.util.ArrayDeque //Deque-Implementierung, Java-Bibliothek

Die LinkedList-Klasse verwendet intern eine doppelt verknüpfte Liste, um eine Warteschlange oder eine Doppelschlange zu modellieren. Die ArrayDeque-Klasse speichert die Elemente intern in einem Array. Wenn die Anzahl der Elemente das Volumen des Arrays überschreitet, wird ein neues Array zugewiesen und alle Elemente werden verschoben. Das bedeutet, dass ArrayDeque je nach Bedarf wächst.

ArrayDeque-Klasse

Die ArrayDeque <E> -Klasse ist eine allgemeine zweidirektionale Warteschlange, die Funktionalität von der AbstractCollection-Klasse erbt und die Deque-Schnittstelle verwendet. ArrayDeque bietet die Möglichkeit, Deque und Resizable-Array zu verwenden. Das Array wird zunächst mit der Größe 16 initialisiert. Es ist als bidirektionale Warteschlange implementiert und unterstützt zwei Zeiger, nämlich den Kopf und den Schwanz. Es erbt die AbstractCollection- Klasse und implementiert die Deque- Schnittstelle. Die wichtigen Punkte zur ArrayDeque-Klasse sind:

• Sie können Elemente am Ende und am Kopf der ArrayDeque hinzufügen oder daraus entfernen
• Nullelemente sind nicht zulässig
• ArrayDeque ist ohne externe Synchronisierung nicht threadsicher.
• Für ArrayDeque gibt es keine Kapazitätsbeschränkungen.

Konstruktoren der ArrayDeque-Klasse

• ArrayDeque() erstellt eine leere Warteschlange.
• ArrayDeque (Collection <? Extends E> Collection) erstellt eine Warteschlange, die mit Collection-Collection-Elementen gefüllt ist.
• ArrayDeque (int Capacity) erstellt eine Warteschlange mit anfänglicher Kapazität . Wenn Sie die Anfangskapazität nicht angeben, beträgt die Standardkapazität 16.

Beispiel für eine Java-Deque – ArrayDeque

Erinnern Sie sich an das Legoturm-Beispiel vom Anfang des Artikels? Erstellen wir eine Klasse zum Bauen einsäuliger Türme aus Legosteinen. Ziegel können rot, gelb oder blau sein. Unsere Turmbauregel: Wir legen die roten Ziegelsteine ​​nach unten und die gelben Ziegelsteine ​​nach oben. Beispiel für ein großes 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 +
              '}';
   }
}

Hier ist unsere Tower-Klasse. Wir initiieren einen Turm. Der eingeleitete Turm hängt von der Menge der Rot- und Gelbtöne ab. Wir können Ziegel zum Turm hinzufügen oder entfernen. Wir fügen Ziegelsteine ​​oben hinzu, wenn sie gelb sind, und fügen sie unten hinzu, wenn sie rot sind.

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

   }

}

Das Ergebnis der Ausführung dieses Programms:

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

Warte was?? Warum sind die Rottöne oben? Nein, das tun sie nicht. Sie wurden einfach vom ersten (unten) bis zum letzten (oben) auf der Konsole ausgedruckt. Wenn Sie also etwas wie im Bild mit den Steinen oben sehen möchten, können Sie die Methode drawTower der Klasse LegoTower ändern. Es ist eine sehr einfache Aufgabe!

LinkedList

Die List-Schnittstelle behält die Reihenfolge des Hinzufügens von Elementen bei und ermöglicht den Zugriff auf das Element über den Index. Deque ist eine bidirektionale Warteschlange und unterstützt das Hinzufügen und Entfernen von Elementen auf beiden Seiten. LinkedList ist hauptsächlich als List-Implementierung bekannt, aber diese Klasse implementiert auch die Deque und ermöglicht es uns, eine bidirektionale Warteschlange zu erstellen, die aus beliebigen Objekten einschließlich Null besteht. LinkedList ist eine Sammlung von Elementen. Wir können es in der Codequelle der Klasse sehen, dieses Mal achten wir auf die Felder: Hier fügen wir ein Beispiel hinzu, aber wenn Sie mehr über LinkedList erfahren möchten, willkommen zu diesem CodeGym- Artikel.

Implementierung einer verknüpften Liste in Java, Hinzufügen und Entfernen von Elementen. Beispiel

Lassen Sie uns diese Vorgänge in der Praxis ausprobieren. Zuerst die Java LinkedList-Implementierung: Erstellen einer LinkedList von Strings und Hinzufügen von drei Elementen. Dann entfernen Sie einen und fügen dann einen in der Mitte hinzu.

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

Das Ergebnis der Ausführung dieses Programms:

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]