Коллекции Java (структура LIFO)
Я безуспешно ищу в структуре коллекций Java структуру LIFO (стек). В основном мне нужен действительно простой стек; мой идеальный вариант - Deque, но я использую Java 1.5.
Я бы не хотел добавлять в свою структуру еще один класс, но мне интересно, возможно ли это:
Есть ли в структуре коллекций (1.5) какой-либо класс, который выполняет эту работу?
Если нет, есть ли способ превратить очередь в очередь LIFO (также известную как стек) без повторной реализации?
Если нет, то какой интерфейс или класс мне следует расширить для этой задачи? Я думаю, что сохранить путь, который ребята из Sun сделали с Deque, - хорошее начало.
Большое спасибо.
Обновлено: Я забыл сказать о классе Stack: у меня возникли сомнения по поводу этого класса, когда я увидел, что он реализует класс Vector, а класс Vector немного устарел, не так ли?
Ответы 6
Есть Класс стека в API. Отвечает ли это вашим потребностям?
Извините, я забыл сказать о классе Stack и своем мнении о нем, но я думаю, что это, вероятно, лучшее решение, чем реализация моего собственного класса. не так ли?
Не используйте класс Stack. Он расширяет Vector, который сохраняется только для обратной совместимости.
На самом деле есть класс стека: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Stack.html
Если вы не хотите использовать это, класс LinkedList (http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html) имеет методы addFirst и addLast, removeFirst и removeLast, что делает его идеальным для использования в качестве класса стека или очереди.
LinkedList также предоставляет определение Deque, которое является вашей желаемой коллекцией.
Да, я думаю, что LinkedList - это тот, который я искал, потому что при первом взгляде на него я не понимал о методах Addfirst и removeFirst. Большое спасибо.
@SpencerKormos ... и LinkedList также поддерживает нулевые элементы в отличие от ArrayDeque.
Stack был заменен более современными классами, как объясняется в документации Javadoc: Более полный и последовательный набор операций стека LIFO обеспечивается интерфейсом Deque и его реализациями, которые следует использовать вместо этого класса. См. Текущее решение в Ответ Бретта Райана и Ответ Ивана.
Класс Куча медленно: методы синхронизированы + Stack расширяет синхронизированный Вектор
Я понимаю, что опаздываю на вечеринку, но java.util.Collections (Java 7) имеет статический asLifoQueue, который принимает аргумент Deque и возвращает (очевидно) представление очереди LIFO для двухсторонней очереди. Я не уверен, какая версия была добавлена.
http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#asLifoQueue(java.util.Deque)
Deque, ArrayDeque и LinkedList
Хотя это было задано некоторое время назад, было бы разумно предоставить ответ JDK6 +, который теперь предоставляет интерфейс Deque (колода), который реализуется структурой данных ArrayDeque, а LinkedList был обновлен для реализации этого интерфейса.
ConcurrentLinkedDeque и LinkedBlockingDeque
Также существуют специализированные формы для одновременного доступа, которые реализуются с помощью ConcurrentLinkedDeque и LinkedBlockingDeque.
LIFO против FIFO
В двухсторонней очереди замечательно то, что она обеспечивает поддержку как LIFO (стек), так и FIFO (очереди), что может вызвать путаницу относительно того, какие методы предназначены для операций с очередью, а какие - для операций со стеком для новичков.
IMHO, JDK должен иметь интерфейс Stack и интерфейс Queue, который все еще может быть реализован такими, как ArrayDeque, но раскрывать только подмножество методов, необходимых для этой структуры, то есть LIFO может определять pop(), push() и peek(), а затем в контексте
LIFO<String> stack = new ArrayDeque<>();
доступны только операции со стеком, что предотвращает случайный вызов добавить (E), когда толкнуть (E) был предназначен.
Deque и LinkedList
Для полноты картины я привожу пример с использованием интерфейса Deque и реализации LinkedList.
Deque<String> deque = new LinkedList<>();
deque.add("first");
deque.add("last");
// returns "last" without removing it
System.out.println(deque.peekLast());
// removes and returns "last"
System.out.println(deque.pollLast());
Резервное копирование Deque с помощью LinkedList отлично подходит для производительности, поскольку вставка и удаление элементов из него выполняется за постоянное время (O (1)).
LinkedList<String> list = new LinkedList<>();
list.add("first");
list.add("last");
// returns "last" without removing it
System.out.println(list.getLast());
// removes and returns "last"
System.out.println(list.removeLast());
В исходном сообщении использовалась очередь, которая, очевидно, была FIFO, а не LIFO, поэтому я обновил свой ответ.
Основная проблема с Vector заключается в том, что весь доступ синхронизируется независимо от того, нужен он вам или нет. Он так же «актуален», как и любой другой сборник, но получил плохую репутацию из-за проблемы с синхронизацией.