Почему стек реализуют через ArrayDeque, а не java.util.Stack?
- Чем плох java.util.Stack?
- Почему для стека и очереди рекомендуют ArrayDeque?
- Почему для стека и очереди рекомендуют ArrayDeque, а не Stack и LinkedList?
Стек и очередь в одном потоке — ArrayDeque (кольцевой массив, O(1) по краям, данные подряд). Stack наследует Vector: synchronized на каждой операции и доступ по индексу в середину — нарушает абстракцию стека.
- push/pop/peek для стека, offer/poll/peek для очереди
- LinkedList тоже Deque, но платит узлом на элемент и промахами кэша
- ArrayDeque не допускает null
А ещё Потокобезопасные — ConcurrentLinkedDeque, LinkedBlockingDeque
Подробно
java.util.Stack — класс Java 1.0, наследник Vector. Каждая операция синхронизирована (бесполезная цена для локального стека), и от Vector унаследованы get(i), add(i, x), remove(i) — можно залезть в середину стека. Документация сама рекомендует Deque.
ArrayDeque — кольцевой буфер на массиве с указателями головы и хвоста. Добавление и снятие с обоих концов — амортизированно O(1), элементы лежат подряд (хорошо для кэша), нет объекта-узла на элемент. Растёт удвоением.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.pop(); // 2
Deque<Task> queue = new ArrayDeque<>();
queue.offer(t1); queue.offer(t2); queue.poll(); // t1LinkedList как очередь — медленнее ArrayDeque: узел на каждый элемент, промахи кэша, нагрузка на GC.
Многопоточно — ConcurrentLinkedDeque (без блокировок), LinkedBlockingDeque и ArrayBlockingQueue (с ожиданием).
Что хотят услышать
- Проблемы Stack: синхронизация и наследование Vector.
- Устройство ArrayDeque и сложность.
- Почему не LinkedList.
Частые ошибки
- Использовать Stack в новом коде.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗Stack удалён из JDK, ArrayDeque — единственный вариант
- ✗Stack хранит элементы в связном списке, поэтому медленнее и расходует больше памяти
- ✗ArrayDeque потокобезопасен, а Stack — нет
- ✓Stack наследует Vector и синхронизирует каждую операцию; ArrayDeque быстрее
Что спросят дальше
- Почему ArrayDeque быстрее LinkedList как очередь?
- Что такое кольцевой буфер?
- Что выбрать, если очередь нужна между потоками?
- Почему PriorityQueue не гарантирует порядок при итерации?
Разбор темы
- Очереди и стек: ArrayDeque и PriorityQueue
ArrayDeque как кольцевой буфер и замена Stack, PriorityQueue как бинарная куча и её неотсортированная итерация.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.