Which class from the Java runtime environment you should use when you need a stack.
The package java.util
contains a few classes suitable for pushing, poping, and
peeking in stack style.
| push | pop | peek | |
|---|---|---|---|
| Stack | s.push(e) |
s.pop() |
s.peek() |
| ArrayList | s.add(e) |
s.remove(s.size()-1) |
s.get(s.size()-1) |
| LinkedList | s.addFirst(e) |
s.removeFirst() |
s.peekFirst() |
| ArrayDeque | s.addFirst(e) |
s.removeFirst() |
s.peekFirst() |
All but ArrayDeque implement
the widely used and known interface List.
Let's see how efficient are the implementations in JRE6, in relative units.
| time | space | |
|---|---|---|
| Stack | x2.09 | x1.6 |
| ArrayList | x1.15 | x1.3 |
| LinkedList | x1.27 | x3.02 |
| ArrayDeque | 1 | 1 |
Yep, ArrayDeque is best
both in terms of time and speed. If you need a subtype of
List then go with
ArrayList. If you want
to eat memory like crazy for no good reason then try
LinkedList. And if you
have a thing for names like Vector
(which Stack extends) then,
well, go for it. Just don't say I told you to use it.
Finally, if you are a speed junkie and you know in advance the
maximum possible size of the stack, then you can implement
your own for a x1.2 speed-up (compared to ArrayDeque).
Just for the record, a basic stack operation for ArrayDeque takes about 15ns on my
old laptop.
Good bye, and stay tuned for the next useless microbenchmark results.