Класс Stack в Java

#java #list #коллекции #stack

Какой класс лучше использовать для использования стека в java и почему он лучше?
    

Ответы

Ответ 1

Deque

Для стэка рекомендуется использовать реализации интерфейса Deque. Интерфейс включает
методы стэка: push, poll и peek.

Стандартные реализации перечислены в документации, например:


ArrayDeque — дэк на основе массива;
LinkedList — связный список;
ConcurrentLinkedDeque — потокобезопасная реализация.


Выбор класса зависит от логики приложения (какие операции выполняются и как часто,
как изменяется размер стэка) и потребует оценки производительности. 

В документации к ArrayDeque  утверждается, что в качестве очереди он, скорее всего,
будет быстрее LinkedList:


  ... This class is likely to be faster than Stack when used as a stack, and faster
than LinkedList when used as a queue.


так что, если не требуется доступ из нескольких потоков, разумно будет использовать
ArrayDeque по умолчанию.

Методы poll и peek в Deque унаследованы от Queue и работают в последовательности
для очереди (FIFO). Для симуляции работы стэка можно использовать вместо них методы
pollLast и peekLast.

Queue

Более удобный вариант: с помощью метода Collections.asLifoQueue преобразовать Deque
в объект Queue, который ведет себя как стэк (LIFO). В этом случае будут корректно работать
все методы и итераторы. Также не будут доступны лишние, не допустимые для стэка операции:

 Queue stack = Collections.asLifoQueue(new ArrayDeque<>());
 stack.addAll(Arrays.asList("a", "b", "c", "d", "e"));
 //edcba
 stack.forEach(element -> System.out.println(element));


Stack не рекомендуется использовать

Также есть стандартный класс java.util.Stack, но его не рекомендуется использовать.
Из документации:


  A more complete and consistent set of LIFO stack operations is provided by the
Deque interface and its implementations, which should be used in preference to this
class. For example: Deque stack = new ArrayDeque();
  
  Более полный и согласованный набор LIFO операций предоставляется через интерфейс
Deque и его реализации, которые должны использоваться вместо этого класса. Например:
Deque stack = new ArrayDeque();


т.е. класс сохранен для обратной совместимости, но вместо него нужно использовать
реализации Deque. Это вызвано историческими причинами: в первой версии Java в реализации
Stack допущены ошибки, например: 


Stack — конкретный класс, в отличие от остальных базовых коллекций, которые представлены
интерфейсами: Set, List, Queue;
класс наследуется от Vector, что концептуально неверно (поддерживаются лишние операции).


Подробнее о проблемах Stack:


Why Stack extends Vector in JDK?
What are the negative aspects of Java class Stack inheriting from Vector?


Ответ 2

Мне кажется стоит использовать ArrayList или LinkedList. Второй будет использовать
больше памяти, но зато операция добавления элемента в нём работает честные O(1), в
отличии от ArrayList, у которого O(1) амортизированные. Не следует использовать класс
Stack, потому что в нём все методы помечены как synchronized, что замедляет производительность
в случае, если ваш стек использует только один поток (почти всегда именно так и происходит).


Ответ 3

Есть мнение - авторитетное - от одного из авторов красно-черных деревьев, что встроенные
коллекции в java очень наворочены. Они напоминают швейцарские ножи - многое умеют.
Но обратная сторона этого - не все операции имеют одинаковую алгоритмическую сложность.
Поэтому лучше использовать коллекции с меньшим количеством методов, но которые хорошо
используются именно вашей задаче. Посмотрите альтернативные реализации стека - не останавливайтесь
на стандартной библиотеке.