Dlaczego powinienem używać Deque over Stack?

Potrzebuję Stackstruktury danych dla mojego przypadku użycia. Powinienem być w stanie wepchnąć elementy do struktury danych i chcę pobrać tylko ostatni element ze stosu. JavaDoc na stosie mówi:

Bardziej kompletny i spójny zestaw operacji na stosie LIFO zapewnia interfejs Deque i jego implementacje, które powinny być używane zamiast tej klasy. Na przykład:

Deque<Integer> stack = new ArrayDeque<>();

Zdecydowanie nie chcę tutaj zsynchronizowanego zachowania, ponieważ będę używał tej struktury danych lokalnie dla metody. Niezależnie od tego, dlaczego wolę Dequeponad Stacktutaj?

PS: javadoc firmy Deque mówi:

Deques mogą być również używane jako stosy LIFO (Last-In-First-Out). Ten interfejs powinien być używany zamiast starszej klasy Stack.

Po pierwsze, jest to bardziej rozsądne pod względem dziedziczenia. Fakt, że się Stackrozciąga, Vectorjest moim zdaniem naprawdę dziwny. We wczesnej Javie dziedziczenie było nadużywane IMO - co Propertiesjest kolejnym przykładem.

Dla mnie kluczowe słowo w cytowanych przez ciebie dokumentach jest spójne . Dequeujawnia zestaw operacji, który polega na możliwości pobierania / dodawania / usuwania elementów z początku lub końca kolekcji, iteracji itp. - i to wszystko. Celowo nie ma możliwości uzyskania dostępu do elementu według pozycji, co Stackujawnia, ponieważ jest to podklasa Vector.

Aha, i też Stacknie ma interfejsu, więc jeśli wiesz, że potrzebujesz Stackoperacji, ostatecznie zatwierdzasz określoną konkretną klasę, co zwykle nie jest dobrym pomysłem.

Również jak wskazano w komentarzach Stacki Dequemają odwrotną kolejność iteracji:

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(new ArrayList<>(stack)); // prints 1, 2, 3


Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(new ArrayList<>(deque)); // prints 3, 2, 1

co jest również wyjaśnione w JavaDocs dla Deque.iterator () :

Zwraca iterator po elementach w tym deque w odpowiedniej kolejności. Elementy zostaną zwrócone w kolejności od pierwszego (początek) do ostatniego (koniec).

Oto moja interpretacja niespójności wspomnianej w opisie klasy Stack.

Jeśli spojrzysz tutaj na Implementacje ogólnego przeznaczenia - zobaczysz, że istnieje spójne podejście do implementacji zbioru, mapy i listy.

• Dla set and map mamy 2 standardowe implementacje z mapami mieszania i drzewami. Pierwsza z nich jest najczęściej używana, a druga jest używana, gdy potrzebujemy uporządkowanej struktury (a także implementuje własny interfejs - SortedSet lub SortedMap).

• Możemy użyć preferowanego stylu deklarowania, jak Set<String> set = new HashSet<String>();zobacz powody tutaj .

Ale klasa Stack: 1) nie ma własnego interfejsu; 2) jest podklasą klasy Vector - opartej na tablicy skalowalnej; więc gdzie jest implementacja listy połączonej stosu?

W interfejsie Deque takich problemów nie mamy, uwzględniając dwie implementacje (tablica o zmiennym rozmiarze - ArrayDeque; lista połączona - LinkedList).

Kolejnym powodem używania Dequeue over Stack jest to, że Dequeue ma możliwość używania strumieni konwertowanych na listę z zachowaniem koncepcji LIFO, podczas gdy Stack nie.

Stack<Integer> stack = new Stack<>();
Deque<Integer> deque = new ArrayDeque<>();

stack.push(1);//1 is the top
deque.push(1)//1 is the top
stack.push(2);//2 is the top
deque.push(2);//2 is the top

List<Integer> list1 = stack.stream().collect(Collectors.toList());//[1,2]

List<Integer> list2 = deque.stream().collect(Collectors.toList());//[2,1]

Oto kilka powodów, dla których Deque jest lepszy niż Stack:

Projektowanie zorientowane obiektowo - dziedziczenie, abstrakcja, klasy i interfejsy: stos to klasa, Deque to interfejs. Tylko jedna klasa może być rozszerzona, podczas gdy dowolna liczba interfejsów może być implementowana przez jedną klasę w Javie (wielokrotne dziedziczenie typu). Użycie interfejsu Deque usuwa zależność od konkretnej klasy Stack i jej przodków i daje większą elastyczność, np. Swobodę rozszerzania innej klasy lub zamiany różnych implementacji Deque (takich jak LinkedList, ArrayDeque).

Niespójność: Stack rozszerza klasę Vector, która umożliwia dostęp do elementu według indeksu. Jest to niezgodne z tym, co faktycznie powinien robić Stack, dlatego preferowany jest interfejs Deque (nie zezwala na takie operacje) - jego dozwolone operacje są zgodne z tym, na co powinna pozwalać struktura danych FIFO lub LIFO.

Wydajność: Klasa Vector, którą rozszerza Stack, jest w zasadzie „bezpieczną wątkowo” wersją klasy ArrayList. Synchronizacje mogą potencjalnie spowodować znaczny spadek wydajności aplikacji. Ponadto rozszerzanie innych klas o niepotrzebne funkcje (jak wspomniano w punkcie 2) powoduje nadużywanie obiektów, co może kosztować dużo dodatkowej pamięci i narzut wydajności.

Dla mnie brakowało tego konkretnego punktu: Stos jest bezpieczny dla wątków, ponieważ pochodzi z Vector, podczas gdy najbardziej deque implementacje nie są, a zatem szybsze, jeśli używasz go tylko w jednym wątku.

Wydajność może być powodem. Algorytm, którego użyłem, skrócił się z 7,6 minuty do 1,5 minuty, po prostu zastępując Stack Deque.

Deque jest używany w sytuacji, gdy chcesz pobrać elementy zarówno z głowy, jak i ogona. Jeśli chcesz mieć prosty stack, nie musisz sięgać po deque.