Java и различные типы стеков

Question

В настоящее время единственный стек, о котором я ничего знаю, это Vector, я обычно использую это вместо массива, но я понимаю, что существуют другие типы стеков, и все они подходят для разных заданий.

Проект, над которым я сейчас работаю, требует, чтобы я вставлял объекты в определенную позицию внутри стека, а не всегда перед стекей, и у меня создается впечатление, что вектор не может быть лучшим классом для этой работы ,

Может ли кто-нибудь, пожалуйста, дать мне краткое описание других типов стеков, доступных мне с языком Java и их преимуществами и недостатками? Являются ли эти названия однородными? Например. Используются ли они только на языке Java или используются в качестве общих терминов в области компьютерных наук?

Спасибо

Answer 1

Я предлагаю взглянуть на this tutorial on the Java Collections Framework, который относится ко всем основным типам данных в java.util пакете, который вы могли бы использовать для таких вещей (списки, векторы, карты, деревья и т.д.).

Answer 2

Вы упомянули, что вставляете вещи в середину своего «стека». Тогда я бы рекомендовал использовать LinkedList.

Если вы уже нашли позицию, необходимую для ввода нового элемента, время для ее вставки - O(1). Для вектора это O(n), потому что вам нужно скопировать массив подложки.

LinkedList также поддерживает операции, подобные стеку, такие как добавление на конец или выпадение конца стека.

Посмотрите на javadocs, чтобы использовать структуру данных, чтобы посмотреть, что она предлагает.

Чтобы ответить на ваш последний вопрос. LinkedList - очень распространенная структура данных в компьютерной науке. Он также очень часто используется для реализации стеков, потому что операции push и pop являются постоянным временем, O(1).

Answer 3

Документация API из java.util.Stack советует вам использовать одну из реализаций интерфейса java.util.Deque, например java.util.ArrayDeque или java.util.LinkedList.

A LinkedList эффективен для вставки элементов посередине и удаления элемента из головы или хвоста (но он неэффективен для поиска случайного элемента).

Answer 4

• стек является абстрактным типом данных характеризуется поведением LIFO или толчке/поп операций
• список является абстрактным типом данных характеризуется тем, что его elemets доступны через числовой индекс.
• массив является реализация низкого уровня списка
• java.util.List является тип списка представлена ​​в виде интерфейса Java
• java.util.Deque является интерфейсом Java, что обеспечивает как LIFO и поведение очереди FIFO (и, таким образом, поведение стека в качестве подмножества)
• java.util.Vector - это устаревшая реализация списка (на основе массива с автоматическим изменением размера), который больше не должен использоваться
• java.util.ArrayList является модернизированной заменой
• java.util.Stack является устаревшей реализацией стеки, который состоит из добавления некоторых стеков подобных методов к вектору, который не является хорошим способом сделать это.
• java.util.ArrayDeque современной реализация интерфейса Deque
• java.util.LinkedList это другая реализация списка (который также реализует интерфейс Deque), который имеет ряд больших недостатков и должен использоваться только в очень конкретном (лучше, когда вам нужно вставлять или удалять элементы в списке очень часто).

В принципе, если вы хотите стек, использовать интерфейс Deque и ArrayDeque как класс реализации (за исключением редких случаев, когда LinkedList лучше). Если вы хотите получить список, используйте ArrayList