Por que devo usar Deque sobre Stack?

Eu preciso de uma Stackestrutura de dados para o meu caso de uso. Devo poder enviar itens para a estrutura de dados e só quero recuperar o último item da Pilha. O JavaDoc for Stack diz:

Um conjunto mais completo e consistente de operações de pilha LIFO é fornecido pela interface Deque e suas implementações, que devem ser usadas preferencialmente a esta classe. Por exemplo:

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

Definitivamente, não quero comportamento sincronizado aqui, pois usarei essa estrutura de dados local para um método. Para além disto por que eu deveria preferir Dequemais Stackaqui?

PS: O javadoc do Deque diz:

O Deques também pode ser usado como pilhas LIFO (Last-In-First-Out). Essa interface deve ser usada de preferência à classe Stack herdada.

Por um lado, é mais sensato em termos de herança. O fato de que Stackse estende Vectoré realmente estranho, na minha opinião. No início de Java, a herança era usada em excesso IMO - Propertiessendo outro exemplo.

Para mim, a palavra crucial nos documentos que você citou é consistente . Dequeexpõe um conjunto de operações cujo objetivo é buscar / adicionar / remover itens do início ou final de uma coleção, iterar etc. - e é isso. Deliberadamente, não há como acessar um elemento por posição, o que é Stackexposto porque é uma subclasse de Vector.

Ah, e também Stacknão possui interface, portanto, se você sabe que precisa de Stackoperações, acaba comprometendo-se com uma classe concreta específica, o que geralmente não é uma boa ideia.

Também conforme indicado nos comentários, Stacke Dequetem ordens de iteração reversa:

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

o que também é explicado no JavaDocs for Deque.iterator () :

Retorna um iterador sobre os elementos neste deque na sequência correta. Os elementos serão retornados em ordem do primeiro (cabeça) ao último (cauda).

Aqui está minha interpretação da inconsistência mencionada na descrição da classe Stack.

Se você observar as Implementações de uso geral aqui - verá uma abordagem consistente para a implementação de conjunto, mapa e lista.

• Para definir e mapear, temos 2 implementações padrão com mapas de hash e árvores. O primeiro é o mais usado e o segundo é usado quando precisamos de uma estrutura ordenada (e também implementa sua própria interface - SortedSet ou SortedMap).

• Podemos usar o estilo preferido de declarar como Set<String> set = new HashSet<String>();ver os motivos aqui .

Mas a classe Stack: 1) não possui interface própria; 2) é uma subclasse da classe Vector - que é baseada em uma matriz redimensionável; Então, onde está a implementação da lista vinculada da pilha?

Na interface Deque, não temos esses problemas, incluindo duas implementações (matriz redimensionável - ArrayDeque; lista vinculada - LinkedList).

Mais um motivo para usar o desenfileiramento sobre a pilha é que o desenfileiramento tem a capacidade de usar fluxos convertidos em lista, mantendo o conceito LIFO aplicado, enquanto o Stack não o faz.

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]

Aqui estão algumas razões pelas quais o Deque é melhor que o Stack:

Design orientado a objetos - herança, abstração, classes e interfaces: Stack é uma classe, Deque é uma interface. Somente uma classe pode ser estendida, enquanto qualquer número de interfaces pode ser implementado por uma única classe em Java (herança múltipla do tipo). O uso da interface Deque remove a dependência da classe Stack concreta e de seus ancestrais e oferece mais flexibilidade, por exemplo, a liberdade de estender uma classe diferente ou trocar diferentes implementações do Deque (como LinkedList, ArrayDeque).

Inconsistência: a pilha estende a classe Vector, que permite acessar o elemento pelo índice. Isso é inconsistente com o que uma pilha realmente deve fazer, e é por isso que a interface Deque é preferida (não permite tais operações) - suas operações permitidas são consistentes com o que uma estrutura de dados FIFO ou LIFO deve permitir.

Desempenho: a classe Vector que Stack estende é basicamente a versão "thread-safe" de um ArrayList. As sincronizações podem causar um impacto significativo no desempenho do seu aplicativo. Além disso, estender outras classes com funcionalidades desnecessárias (conforme mencionado no item 2) incha seus objetos, potencialmente custando muita memória extra e sobrecarga de desempenho.

Para mim, esse ponto específico estava ausente: Stack é Threadsafe, pois é derivado de Vector, enquanto as implementações mais deque não são e, portanto, mais rápidas se você a usar apenas em um único thread.

O desempenho pode ser uma razão. Um algoritmo que usei caiu de 7,6 para 1,5 minutos, substituindo apenas Stack por Deque.

Deque é usado é a situação em que você deseja recuperar elementos da cabeça e da cauda. Se você quer uma pilha simples, não há necessidade de fazer um deque.