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

Question

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

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

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

Спасибо

Answer 1

• A стек - это абстрактный тип данных, характеризуемый поведением LIFO или операциями push / pop
• A list - это абстрактный тип данных, характеризующийся наличиемего элементы доступны через числовой индекс.
• массив - низкоуровневая реализация списка
• 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

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

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