Почему я должен использовать Deque над Stack?

Мне нужна структура данных Stack для моего варианта использования. Я должен иметь возможность вставлять элементы в структуру данных, и я хочу только извлечь последний элемент из Stack. JavaDoc для стека говорит:

Более полный и последовательный набор операций стека LIFO предоставляемые интерфейсом Deque и его реализациями, которые должны используется для этого класса. Например:

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

Мне определенно не нужно синхронизировать поведение, поскольку я буду использовать эту структуру данных локально для метода. Помимо этого, почему я предпочитаю Deque над Stack здесь?

P.S: Джавадок из Deque говорит:

Deques также может использоваться как стеки LIFO (Last-In-First-Out). Эта интерфейс следует использовать вместо старого класса Stack.

Ответы

Ответ 1

С одной стороны, это более разумно с точки зрения наследования. Тот факт, что Stack расширяет Vector, на мой взгляд, действительно странный. В начале Java наследование было перерасходовано IMO - еще один пример - Properties.

Для меня ключевое слово в документах, которые вы цитировали, является последовательным. Deque предоставляет набор операций, которые предназначены для возможности извлечения/добавления/удаления элементов из начала или конца коллекции, итерации и т.д. - и тому подобное. Умышленно нет способа получить доступ к элементу по позиции, который предоставляет Stack поскольку он является подклассом Vector.

Да, и у Stack нет интерфейса, поэтому, если вы знаете, что вам нужны операции со Stack вы в конечном итоге фиксируете определенный конкретный класс, что обычно не является хорошей идеей.

Также, как указано в комментариях, Stack и Deque имеют обратный порядок итераций:

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

что также объясняется в JavaDocs для Deque.iterator():

Возвращает итератор для элементов в этой deque в правильной последовательности. Элементы будут возвращены в порядке от первого (голова) до последнего (хвост).

Ответ 2

Вот моя интерпретация несогласованности, упомянутая в описании класса Stack.

Если вы посмотрите на универсальные реализации здесь - вы увидите, что существует последовательный подход к реализации набора, карты и списка.

  • Для множества и отображения у нас есть 2 стандартных реализации с хэш-картами и деревьями. Первый используется наиболее часто, а второй используется, когда нам нужна упорядоченная структура (а также реализует собственный интерфейс - SortedSet или SortedMap).

  • Мы можем использовать предпочтительный стиль объявления типа Set<String> set = new HashSet<String>();, чтобы увидеть причины здесь.

Но класс Stack: 1) не имеет собственного интерфейса; 2) является подклассом класса Vector, который основан на изменяемом массиве; поэтому где связанная реализация списка стека?

В интерфейсе Deque у нас нет таких проблем, включая две реализации (resizable array - ArrayDeque, связанный список - LinkedList).

Ответ 3

Еще одна причина использовать Dequeue поверх стека состоит в том, что Dequeue имеет возможность использовать преобразование потоков в список с сохранением концепции LIFO, в то время как Stack этого не делает.

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]

Ответ 4

Для меня эта конкретная точка отсутствовала: Stack - это Threadsafe, поскольку он получен из Vector, тогда как большинство реализаций deque не являются и, следовательно, быстрее, если вы используете его только в одном потоке.

Ответ 5

Производительность может быть причиной. Алгоритм, который я использовал, сократился с 7,6 до 1,5 минут, просто заменив Stack на Deque.

Ответ 6

Используется Deque - ситуация, когда вы хотите извлекать элементы из головы и хвоста. Если вам нужен простой стек, нет необходимости идти на деку.