Java Collections (LIFO Structure)

问题:

I am looking in the Collections framework of Java for a LIFO Structure (Stack) without any success. Basically I want a really simple stack; my perfect option would be a Deque, but I am in Java 1.5.

I would like not to have to add another class to my structure but I am wondering if that is possible:

1. Is there any class in the Collections framework (1.5) that does the job?

2. If not, is there any way to turn a Queue in a LIFO Queue (aka Stack) without reimplementation?

3. If not, which Interface or class should I extend for this task? I guess that keep the way that the guys of Sun have made with the Deque is a good start.

Thanks a lot.

EDIT: I forgot to say about the Stack class: I have my doubts about this class when I saw that it implements the Vector class, and the Vector class is a little bit obsolete, isn't it?

回答1:

There's actually a Stack class: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Stack.html

If you don't want to use that, the LinkedList class (http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html) has addFirst and addLast and removeFirst and removeLast methods, making it perfect for use as a stack or queue class.

回答2:

Stack class is slowly: methods are synchronized + Stack extends synchronized Vector

回答3:

I realize I'm late to the party here, but java.util.Collections (Java 7) has a static 'asLifoQueue' that takes a Deque argument and returns (obviously) a LIFO queue view of the deque. I'm not sure what version this was added.

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

回答4:

There is a Stack class in the API. Will this meet your needs?

回答5:

While this was asked a while ago it might be wise to provide a JDK6+ answer which now provides a Deque (deck) interface which is implemented by the ArrayDeque data structure and the LinkedList was updated to implement this interface. Specialised forms for concurrent access also exist and are implemented by ConcurrentLinkedDeque and LinkedBlockingDeque.

The one thing that is great about a deque is that it provides both LIFO (stack) and FIFO (queue) support it can cause confusion as to which methods are for queue operations and which are for stack operations for newcomers.

IMHO the JDK should have a Stack interface and a Queue interface that could still be implemented by the likes of ArrayDeque but only expose the subset of methods required for that structure, i.e. a LIFO could define pop(), push() and peek(), then in the context of

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

only stack operations are exposed which stops someone accidentally calling add(E) when push(E) was intended.

回答6:

Just for the sake of completeness I'm providing a Dequeue and a pure LinkedList example.

Using the Dequeue interface in combination with a LinkedList (recommended):

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

Backing up a Dequeue by a LinkedList is great for performance, since inserting and removing elements from it is done in constant time (O(1)).

Using a LinkedList alone:

    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:

[WRONG ANSWER PERFORMANCE-WISE] I'm only keeping it for people to learn that this is not a good solution.

Simplest answer would be to use an ArrayList, and just add objects at the 0 index.

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

adding objects at 0 index will add to the top of the list, and shifts the rest of the list. Now you have a simple functioning LIFO data structure.

EDIT: Using a LinkedList is faster than using an ArrayList. So using LinkedList.addFirst() is better.