Класс Stack в Java

Для стэка рекомендуется использовать реализации интерфейса 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 по умолчанию.

Также есть стандартный класс 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<Integer> stack = new ArrayDeque<Integer>();

Более полный и согласованный набор LIFO операций предоставляется через интерфейс Deque и его реализации, которые должны использоваться вместо этого класса. Например: Deque<Integer> stack = new ArrayDeque<Integer>();

т.е. класс сохранен для обратной совместимости, но вместо него нужно использовать реализации 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?

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