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

Question

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

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

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

2. Если нет, есть ли способ превратить очередь в очередь LIFO (иначе говоря, в стек) без повторной реализации?

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

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

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

Answer 1

На самом деле есть класс стека: 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 методы, что делает его идеальным для использования в качестве стека класс очереди.

Answer 2

Я понимаю, что опоздал на вечеринку здесь, но 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)

Answer 3

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

Answer 4

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

Единственное, что замечательно в deque, это то, что он обеспечивает поддержку как LIFO (стек), так и FIFO (очередь), так как это может привести к путанице в отношении того, какие методы предназначены для операций очереди, а какие - для операций со стеком для новичков. *

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

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

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

Answer 5

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

Answer 6

[НЕПРАВИЛЬНЫЙ ОТВЕТ НА ВЫПОЛНЕНИЕ] Я только сохраняю это для людей, чтобы узнать, что это не хорошее решение.

Самый простой ответ - использовать 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 ().

Answer 7

Просто для полноты картины я предоставляю Dequeue и чистый пример LinkedList.

Использование интерфейса Dequeue в сочетании с LinkedList (рекомендуется):

    Deque<String> dequeue = new LinkedList<>();
    dequeue.add("first");
    dequeue.add("last");

    // returns "last" without removing it
    System.out.println(dequeue.peekLast());

    // removes and returns "last"
    System.out.println(dequeue.pollLast());

Резервное копирование Dequeue с помощью 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());