deque java deque implementation
Ten samouczek zawiera szczegółowe wyjaśnienie Deque lub „podwójnie zakończonej kolejki” w języku Java. Dowiesz się o interfejsie Deque, metodach API, implementacji itp .:
Deque lub „podwójna kolejka” w Javie to struktura danych, w której możemy wstawiać lub usuwać elementy z obu końców. Deque jest interfejsem w Javie należącym do pakietu java.util i implementuje interfejs java.queue.
Deque możemy zaimplementować jako strukturę stosu (Last In, First Out) lub jako kolejkę (first-in-first-out). Deque jest szybszy niż Stack i / lub LinkedList. Deque wymawia się jako „talię”, podobnie jak w „talii kart”.
=> Zajrzyj tutaj, aby zobaczyć A-Z samouczków szkoleniowych Java tutaj.
Czego się nauczysz:
Około Java
Typowa kolekcja deque będzie wyglądać tak, jak pokazano poniżej:
5 przykładów języków programowania wysokiego poziomu
Deque jest najczęściej używany do implementacji struktur danych stosu, kolejki lub listy. Może być również używany do realizacji kolejek priorytetowych. Funkcje cofania lub historii występujące głównie w przeglądarkach internetowych można zaimplementować za pomocą deques.
Interfejs Java Deque
Poniższy diagram przedstawia hierarchię podwójnie zakończonej kolejki lub deque. Jak pokazano na poniższym diagramie, interfejs Deque rozciąga się na interfejs Queue, który z kolei rozszerza interfejs Collection.
Aby użyć interfejsu deque w naszym programie, musimy zaimportować pakiet, który zawiera funkcjonalność deque, używając instrukcji import, jak pokazano poniżej.
import java.util.deque;
lub
import java.util.*;
Ponieważ deque jest interfejsem, potrzebujemy konkretnych klas do implementacji funkcjonalności interfejsu deque.
Dwie poniższe klasy implementują interfejs deque.
- ArrayDeque
- Połączona lista
Dlatego możemy tworzyć obiekty deque przy użyciu tych dwóch klas, jak pokazano poniżej:
Deque numdeque = new ArrayDeque (); Deque strDeque = new LinkedList ();
Tak więc, gdy powyższe obiekty deque zostaną pomyślnie utworzone, mogą korzystać z funkcjonalności interfejsu deque.
Poniżej podano kilka ważnych punktów, na które należy zwrócić uwagę na temat deque:
- Interfejs Deque obsługuje tablice o zmiennym rozmiarze, które mogą rosnąć zgodnie z wymaganiami.
- Array deques nie pozwalają na użycie wartości Null.
- Deque nie obsługuje równoczesnego dostępu przez więcej niż jeden wątek.
- Deque nie jest bezpieczny wątkowo, chyba że zapewniona jest synchronizacja zewnętrzna.
ArrayDeque w Javie
ArrayDeque należy do pakietu java.util. Implementuje interfejs deque. Klasa ArrayDeque wykorzystuje wewnętrznie tablicę z możliwością dynamicznej zmiany rozmiaru, która rośnie wraz ze wzrostem liczby elementów.
Poniższy diagram przedstawia hierarchię dla klasy ArrayDeque:
Jak pokazano na diagramie, klasa ArrayDeque dziedziczy klasę AbstractCollection i implementuje interfejs Deque.
najlepsze usługi hostingowe w Indiach
Możemy stworzyć obiekt deque za pomocą klasy ArrayDeque, jak pokazano poniżej:
Deque deque_obj = new ArrayDeque ();
i przykład
Poniższy program w języku Java przedstawia prosty przykład, aby lepiej zrozumieć deque. W tym przypadku użyliśmy klasy ArrayDeque do utworzenia wystąpienia interfejsu deque. Właśnie dodaliśmy kilka elementów do obiektu deque, a następnie wydrukowaliśmy je za pomocą pętli forEach.
import java.util.*; public class Main { public static void main(String() args) { //Creat a Deque and add elements Deque cities_deque = new ArrayDeque(); cities_deque.add('Delhi'); cities_deque.add('Mumbai'); cities_deque.add('Bangaluru'); System.out.println('Deque Contents:'); //Traverse the Deque for (String str : cities_deque) { System.out.print(str + ' '); } } }
Wynik:
Java API i metody
Ponieważ interfejs deque implementuje interfejs kolejki, obsługuje wszystkie metody interfejsu kolejki. Poza tym interfejs deque udostępnia następujące metody, których można używać do wykonywania różnych operacji na obiekcie deque.
Podsumujmy te metody w poniższej tabeli.
metoda | Prototyp metody | Opis |
---|---|---|
getFirst | E getFirst () | Odzyskaj pierwszy element deque bez usuwania go. |
Dodaj | add boolean (E e) | Dodaje dany element e do deque (na końcu) bez naruszania ograniczeń pojemności i zwraca wartość true, jeśli zakończy się sukcesem. Zgłasza wyjątek IllegalStateException, jeśli w deque nie ma miejsca. |
addFirst | void addFirst (E e) | Dodaje dany element e na początek kolejki bez naruszania ograniczeń pojemności. |
addLast | void addLast (E e) | Dodaje element e do ostatniego elementu deque bez naruszania ograniczeń pojemności. |
zawiera | boolean zawiera (obiekt o) | Sprawdza, czy deque zawiera dany element o. Zwraca wartość true, jeśli tak. |
descendingIterator | Iterator malejącoIterator () | Ta metoda zwraca iterator odwrotnej kolejności dla deque. |
element | Element E () | Zwraca pierwszy element lub nagłówek deque. Zauważ, że nie usuwa to elementu. |
getLast | E getLast () | Pobiera ostatni element deque bez usuwania go. |
iterator | Iterator iterator () | Zwraca standardowy iterator po elementach deque. |
oferta | oferta logiczna (E e) | Dodaje dany element e do deque (jako ogon) bez naruszania ograniczeń wydajności. Zwraca wartość true w przypadku sukcesu i false w przypadku niepowodzenia. |
offerFirst | oferta logicznaFirst (E e) | Wstaw podany element e na przód deque bez naruszania ograniczeń wydajności. |
offerLast | oferta logicznaOstatni (E e) | Wstaw podany element e na końcu deque bez naruszania ograniczeń wydajności. |
zerkać | E peek () | Zwraca nagłówek deque (pierwszy element) lub null, jeśli kolejka jest pusta. ** nie usuwa głowy |
peekFirst | E peekFirst () | Zwraca pierwszy element w deque bez usuwania go. Zwraca null, jeśli deque jest pusty. |
peekLast | E peekLast () | Pobiera ostatni element z deque bez usuwania go. Zwraca null, jeśli deque jest pusty. |
głosowanie | E ankieta () | Usuwa i zwraca głowę deque. Zwraca null, jeśli deque jest pusty. |
pollFirst | E pollFirst () | Zwraca i usuwa pierwszy element deque. Zwraca null, jeśli deque jest pusty. |
ankietaLast | E ankietaLast () | Zwraca i usuwa ostatni element deque. Zwraca null, jeśli deque jest pusty. |
Muzyka pop | E pop () | Zdejmij element ze stosu, który jest reprezentowany za pomocą deque. |
Pchać | void push (E e) | Wepchnij dany element e do stosu reprezentowanego przez deque bez naruszania ograniczeń pojemności. Zwraca true w przypadku sukcesu lub IllegalStateException, jeśli nie ma wolnego miejsca na deque. |
usunąć | E usuń () | Usuń i odłóż głowę deque. |
usunąć | boolean remove (Object o) | Usuń pierwsze wystąpienie danego elementu o z deque. |
removeFirst | E usuńFirst () | Usuń i zwróć pierwszy element deque. |
removeFirstOccurrence | boolean removeFirstOccurrence (Object o) | Usuwa pierwsze wystąpienie danego elementu o z deque. |
usuńLast | E usuńOstatni () | Pobiera i usuwa ostatni element w deque. |
removeLastOccurrence | boolean removeLastOccurrence (Object o) | Usuwa ostatnie wystąpienie danego elementu o z deque. |
rozmiar | rozmiar int () | Zwraca rozmiar lub liczbę elementów w deque. |
I implementacja w Javie
Zaimplementujmy teraz program w języku Java, aby zademonstrować niektóre z głównych metod deque omówionych powyżej.
W tym programie używamy deque typu String, a następnie dodajemy elementy do tego deque za pomocą różnych metod, takich jak add, addFirst, addLast, push, offer, offerFirst itd. Następnie wyświetlamy deque. Następnie definiujemy standardowe i odwrotne iteratory dla deque i przechodzimy przez deque, aby wydrukować elementy.
Używamy również innych metod, takich jak include, pop, push, peek, poll, remove itp.
import java.util.*; public class Main { public static void main(String() args) { //Declare Deque object Deque deque = new LinkedList(); // add elements to the queue using various methods deque.add('One'); //add () deque.addFirst('Two'); //addFirst () deque.addLast('Three'); //addLast () deque.push('Four'); //push () deque.offer('Five'); //offer () deque.offerFirst('Six'); //offerFirst () deque.offerLast('Seven'); //offerLast () System.out.println('Initial Deque:'); System.out.print(deque + ' '); // Iterate using standard iterator System.out.println('
Deque contents using Standard Iterator:'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Iterate using Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Deque contents using Reverse Iterator:'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek () method System.out.println('
Deque Peek:' + deque.peek()); System.out.println('
Deque,After peek:' + deque); // Pop () method System.out.println('
Deque Pop:' + deque.pop()); System.out.println('
Deque,After pop:' + deque); // contains () method System.out.println('
Deque Contains Three: ' + deque.contains('Three')); deque.removeFirst(); //removeFirst () deque.removeLast(); //removeLast () System.out.println('
Deque, after removing ' + 'first and last elements: ' + deque); } }
Wynik:
Często Zadawane Pytania
Pytanie 1) Czy Deque obsługuje wątki Java?
Odpowiedź: ArrayDeque nie jest bezpieczny dla wątków. Ale interfejs BlockingDeque w klasie java.util.concurrent reprezentuje deque. Ten deque jest bezpieczny dla wątków.
Pytanie nr 2) Dlaczego Deque jest szybszy niż stack?
Odpowiedź: Interfejs ArrayDeque, który implementuje interfejs deque, jest wydajny pod względem pamięci, ponieważ nie musi śledzić poprzednich ani następnych węzłów. Jest to również implementacja o zmiennym rozmiarze. Tak więc deque jest szybszy niż stack.
Pytanie nr 3) Czy Deque jest stosem?
Odpowiedź: Deque to kolejka dwustronna. Pozwala na zachowanie LIFO i dlatego może być implementowany jako stos, chociaż nie jest stosem.
Pytanie 4) Gdzie jest używany Deque?
Odpowiedź: Deque jest najczęściej używany do implementowania funkcji, takich jak cofanie i historia.
P # 5) Czy Deque jest okrągła?
Odpowiedź: Tak, Deque jest okrągły.
Wniosek
To kończy nasz samouczek dotyczący interfejsu Deque w Javie. Interfejs deque jest implementowany przez strukturę danych deque, która jest kolekcją, która może wstawiać i usuwać elementy z obu końców.
Dwie klasy, tj. ArrayDeque i LinkedList, implementują interfejs deque. Możemy użyć tych klas do implementacji funkcjonalności interfejsu deque.
=> Odwiedź tutaj ekskluzywną serię samouczków szkoleniowych Java.
rekomendowane lektury
- Podwójnie zakończona kolejka (Deque) w C ++ z przykładami
- Kolejka Java - metody kolejki, implementacja kolejki z przykładami
- Samouczek dotyczący kolejki priorytetowej Java - implementacja i przykłady
- Struktura danych kolejki priorytetowej w C ++ z ilustracjami
- Struktura danych kolejki w C ++ z ilustracjami
- Struktura danych kolejek cyklicznych w C ++: wdrażanie i aplikacje
- Samouczek JAVA dla początkujących: ponad 100 praktycznych samouczków wideo Java
- Kolejka priorytetowa w STL