Interfejs Java Deque

Java Deque to struktura danych, która łączy zwykłą kolejkę i stos. Możesz dodawać i usuwać elementy zarówno na głowie, jak i na ogonie Deque. W kolejce „tradycyjnej” dodajesz elementy na końcu linii (po ostatnim elemencie) i usuwasz elementy z początku kolejki. Zasada ta nosi nazwę First In First Out (FIFO) i działa jak każda zwykła linia klientów w prawdziwym życiu. W Java Queue jest interfejsem, częścią Collections Framework. Istnieje również ważna struktura danych o nazwie Stack, lista, która działa z elementami na całkowicie odwrotnej zasadzie, LIFO — ostatnie weszło, pierwsze wyszło. Jest podobny do stosu talerzy, dodawanie lub usuwanie jest możliwe tylko od góry.

Kolejka kontra Deque

Deque jest dość dziwnym rodzajem kolejki: możesz dodawać nowe elementy zarówno na końcu, jak i na początku linii. Ta sama historia z usuwaniem: możesz usunąć ostatni lub pierwszy element z tej struktury. Dlatego wydaje się, że jest to mieszanka stosu i kolejki. Nazwa „Deque” oznacza „podwójnie zakończoną kolejkę”. „Deque” wymawia się jak „talia” kart i wiesz co? Jest to trochę podobne do prawdziwej talii kart: możesz wziąć kartę z dołu lub z góry takiej talii. Chcesz dodać lub usunąć elementy z obu stron jakiejś struktury liniowej? Użyj Deque. Obsługuje ją Java 8 lub prawie każda inna wersja. Wyobraź sobie typowy klocek lego i jednokolumnowe „wieże” zbudowane z klocków. Możesz dodać nowy klocek na szczyt wieży lub na dół. Możesz także usunąć cegłę z obu stron. Oto przykład: dodajemy wszystkie żółte klocki na górę i wszystkie czerwone na dół. Wkrótce zademonstrujemy ten przykład z kodem Java. Możesz więc kolejkować i usuwać z kolejki z obu końców Java Deque, co oznacza, że ​​możesz używać Deque zarówno jako kolejki, jak i stosu. Przeczytaj o Stack w Javie: Java Stack 101: Zagłębianie się w klasę Stack Przeczytaj o Queue w Javie: Java Queue Interface i jego implementacje

Cechy Deque

• Deque w Javie to interfejs, którego implementacje zapewniają obsługę tablicy o zmiennym rozmiarze. Masz więc szereg pojemności bez ograniczeń i możesz dodawać nowe elementy zgodnie ze swoimi potrzebami.
• Jednoczesny dostęp przez wiele wątków nie jest obsługiwany przez Deque
• Deque nie jest bezpieczny dla wątków w przypadku braku zewnętrznej synchronizacji.
• Żadne elementy Null nie są dozwolone w tablicy deque.

Deklaracja interfejsu Deque Java

public interface Deque<E> extends Queue<E>

Metody Deque w Javie

java.util.Deque to interfejs rozszerzający interfejs kolejki Java i reprezentujący kolejkę dwustronną. Możesz więc używać wszystkich metod Java Queue podczas pracy z Deque. Mimo że Deque nie rozszerza interfejsu Stack, interfejs Deque definiuje metody, które umożliwiają wykonywanie typowych operacji na stosie, takich jak push , peek i pop .

• boolean add(element) dodaje element do ogona Deque. Zwraca true w przypadku sukcesu, zgłasza wyjątek IllegalStateException, jeśli aktualnie nie ma dostępnego miejsca.
• addFirst(element) dodaje element do nagłówka Deque.
• addLast(element) dodaje element do ogona Deque.
• Offer(element) dodaje element do ogona i zwraca wartość logiczną, aby wyjaśnić, czy wstawienie się powiodło.
• OfferFirst(element) dodaje element do nagłówka i zwraca wartość logiczną, aby wyjaśnić, czy wstawienie się powiodło.
• OfferLast(element) dodaje element do ogona i zwraca wartość logiczną, aby wyjaśnić, czy wstawienie się powiodło.
• iterator() zwraca iterator dla deque.
• maleingIterator() zwraca iterator, który ma odwrotną kolejność dla tej deque.
• push(element) dodaje element do głowy.
• pop(element) usuwa element z głowy i zwraca go.
• removeFirst() usuwa element w nagłówku.
• removeLast() usuwa element na końcu.
• poll() pobiera i usuwa nagłówek kolejki reprezentowanej przez tę deque (innymi słowy, pierwszy element tej deque) lub zwraca null, jeśli ta deque jest pusta.
• pollFirst() pobiera i usuwa pierwszy element tej deque lub zwraca null, jeśli ta deque jest pusta.
• pollLast() pobiera i usuwa ostatni element tej deque lub zwraca null, jeśli ta deque jest pusta.
• peek() pobiera, ale nie usuwa, nagłówek kolejki reprezentowanej przez tę deque (innymi słowy, pierwszy element tej deque) lub zwraca null, jeśli ta deque jest pusta.
• peekFirst() pobiera, ale nie usuwa, pierwszy element tej deque lub zwraca wartość null, jeśli ta deque jest pusta.
• peekLast() pobiera, ale nie usuwa, ostatni element tej deque lub zwraca null, jeśli ta deque jest pusta.

W poniższej tabeli wszystkie metody są podzielone na grupy. Jak widać, istnieje wiele różnych metod dodawania i usuwania elementu. Na przykład zarówno removeFirst(), jak i pop() usuwają pierwszy element z deque. Drugi „poszedł” ze stosu. Oznacza to, że jeśli używasz ArrayDeque tylko jako stosu, użyj pop() do usunięcia, push() do dodania i peek() do sprawdzenia. Dzięki temu Twój kod jest bardziej zrozumiały dla innych programistów.

Implementacje Deque

Java Deque jest interfejsem i ma implementacje w Java Collections API:

• implementacja java.util.LinkedList //List i Deque
• java.util.ArrayDeque // Implementacja Deque, biblioteka Java

Klasa LinkedList używa wewnętrznie podwójnie połączonej listy do modelowania kolejki lub deque. Klasa ArrayDeque przechowuje elementy wewnętrznie w tablicy. Jeśli liczba elementów przekracza objętość tablicy, przydzielana jest nowa tablica, a wszystkie elementy są przenoszone. Oznacza to, że ArrayDeque rośnie wraz z potrzebami.

Klasa ArrayDeque

Klasa ArrayDeque <E> to ogólna kolejka dwukierunkowa, dziedzicząca funkcjonalność z klasy AbstractCollection i korzystająca z interfejsu Deque. ArrayDeque zapewnia możliwość korzystania z deque i resizable-array. Początkowo tablica jest inicjowana rozmiarem 16. Jest zaimplementowana jako kolejka dwukierunkowa, w której obsługuje dwa wskaźniki, a mianowicie głowę i ogon. Dziedziczy klasę AbstractCollection i implementuje interfejs Deque . Ważne punkty dotyczące klasy ArrayDeque to:

• Możesz dodawać lub usuwać elementy z ogona i głowy ArrayDeque
• Elementy zerowe nie są dozwolone
• ArrayDeque nie jest bezpieczny dla wątków przy braku synchronizacji zewnętrznej.
• ArrayDeque nie ma ograniczeń pojemności.

Konstruktory klasy ArrayDeque

• ArrayDeque() tworzy pustą kolejkę.
• ArrayDeque (kolekcja Collection <? Extends E>) tworzy kolejkę wypełnioną elementami kolekcji Collection.
• ArrayDeque (int Capacity) tworzy kolejkę z początkową pojemnością . Jeśli nie określisz początkowej pojemności, domyślna pojemność to 16.

Przykład Java Deque — ArrayDeque

Pamiętasz przykład Lego Tower z początku artykułu? Stwórzmy klasę do budowania jednokolumnowych wież z klocków Lego. Cegły mogą być czerwone, żółte lub niebieskie. Nasza zasada budowania Wieży: czerwone cegły kładziemy na dole, a żółte na górze. Przykład Big 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 +
              '}';
   }
}

Oto nasza klasa Tower. Inicjujemy wieżę. Zainicjowana wieża zależy od ilości czerwonych i żółtych. Możemy dołożyć cegłę do wieży lub ją usunąć. Cegłę dodajemy na górę, jeśli jest żółta, a na dół, jeśli jest czerwona.

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

   }

}

Wynik działania tego programu:

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

Czekaj, co?? Dlaczego czerwone są na górze? Nie, oni nie. Właśnie wydrukowali na konsoli, zaczynając od pierwszego (na dole) do ostatniego (na górze). Jeśli więc chcesz zobaczyć coś takiego jak na powyższym obrazku z klockami, możesz zmienić metodę drawTower klasy LegoTower. To bardzo łatwe zadanie!

Połączona lista

Interfejs List zachowuje kolejność dodawania elementów i umożliwia dostęp do elementu według indeksu. Deque jest kolejką dwukierunkową i obsługuje dodawanie i usuwanie elementów z obu stron. LinkedList jest znany głównie jako implementacja List, ale także ta klasa implementuje Deque i pozwala nam tworzyć dwukierunkową kolejkę składającą się z dowolnych obiektów, w tym null. LinkedList to zbiór elementów. Widzimy to w źródle kodu klasy, tym razem zwróćmy uwagę na pola: Tutaj dodajemy jeden przykład, ale jeśli chcesz dowiedzieć się więcej o LinkedList, zapraszamy do tego artykułu CodeGym .

Implementacja list połączonych w Javie, dodawanie i usuwanie elementów. Przykład

Wypróbujmy te operacje w praktyce. Najpierw implementacja Java LinkedList: utworzenie LinkedList of Strings, dodanie tam 3 elementów. Następnie usuń jeden, a następnie dodaj jeden na środku.

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

Wynik działania tego programu:

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]