Коллекции Java (структура LIFO)

Я ищу в структуре коллекций Java для структуры LIFO (Stack) без каких-либо успехов. В принципе, я хочу действительно простой стек; мой идеальный вариант был бы Deque, но я нахожусь в Java 1.5.

Я бы не хотел добавлять другой класс в свою структуру, но мне интересно, возможно ли это:

  • Есть ли какой-либо класс в структуре Collections (1.5), который выполняет задание?

  • Если нет, есть ли способ превратить очередь в очереди LIFO (иначе Stack) без повторной реализации?

  • Если нет, какой интерфейс или класс следует расширять для этой задачи? Я предполагаю, что сохранить способ, которым ребята из Sun сделали с Deque, - хорошее начало.

Большое спасибо.

EDIT: Я забыл сказать о классе Stack: у меня есть сомнения относительно этого класса, когда я увидел, что он реализует класс Vector, а класс Vector немного устарел, не так ли?

Ответы

Ответ 2

Стек медленно: методы синхронизированы + Stac k продолжается синхронно Вектор

Ответ 3

Я понимаю, что я опаздываю на вечеринку здесь, но java.util.Collections(Java 7) имеет статический "asLifoQueue", который принимает аргумент Deque и возвращает (очевидно) представление очереди LIFO для deque. Я не уверен, какая версия была добавлена.

http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#asLifoQueue(java.util.Deque)

Ответ 4

Существует класс Stack в API. Будет ли это соответствовать вашим потребностям?

Ответ 5

Хотя это было задано некоторое время назад, было бы разумно предоставить ответ JDK6 +, который теперь предоставляет интерфейс Deque (колода), который реализуется структурой данных ArrayDeque, а LinkedList был обновлен для реализации этого интерфейса. Специализированные формы для одновременного доступа также существуют и реализуются ConcurrentLinkedDeque и LinkedBlockingDeque.

Одна вещь, которая хороша в отношении deque, заключается в том, что она обеспечивает поддержку как LIFO (стек), так и FIFO (queue), может вызвать путаницу в отношении того, какие методы предназначены для операций с очередями и какие операции стека для новичков.

IMHO JDK должен иметь интерфейс Stack и интерфейс Queue, который все еще может быть реализован такими ArrayDeque но только выставляют подмножество методов, необходимых для этой структуры, то есть LIFO может определять pop(), push() и peek(), а затем в контексте

LIFO<String> stack = new ArrayDeque<>();

отображаются только операции стека, которые останавливают случайного вызова add (E), когда push (E).

Ответ 6

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 :

    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());

Ответ 7

[НЕПРАВИЛЬНО ОТВЕТИТЬ НА ВЫПОЛНЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ] Я только оставляю людям возможность узнать, что это не хорошее решение.

Самый простой ответ - использовать ArrayList и просто добавить объекты с индексом 0.

List<String> arrayList = new ArrayList<>();
arrayList.add(0, "three");
arrayList.add(0, "two");
arrayList.add(0, "one");

// Prints: [one, two, three]
System.out.println(arrayList);

добавление объектов с индексом 0 добавит в начало списка и сместит остальную часть списка. Теперь у вас есть простая структура данных LIFO.

РЕДАКТИРОВАТЬ: Использование LinkedList быстрее, чем использование ArrayList. Так что лучше использовать LinkedList.addFirst().