Why Future Generations Will Hate You for Using java.util.Stack

Before I kill you with some meaningless tautology, here is the gist

1. If your application is near real time or you are sending your code to Mars, you need to keep off the default Stack implementation in Java. Write your own version based on LinkedList.

2. Again, if your application is mission critical and your Stack is expected to be manipulated by concurrent threads, then use a ConcurrentLinkedDeque or write your own Stack based on LinkedList - just make sure your add and remove operations are thread safe. While doing so, consider concurrency locks.

3. You just need raw power and are not bothered by occasional hiccups during the push process AND your Stack is not manipulated by concurrent threads, then use an ArrayDeque or go ahead and write your own Stack based on an ArrayList.

4. If multithreaded, then write your own Stack based on ArrayQueue and util.concurrent locks.

5. If you refuse to read the Java Stack API and the Java Deque API and you are simply a crazy person, then use the default implementation. And I promise, no mercy will be shown to you when the bots take over the world.

Note : The truth is unless, for some reason, you would want to name your implementation class as ’Stack’, you are pretty much free to use all the Deque implementations as a Stack directly.

Now that enough mud had been thrown against the default implementation and I have your attention for a couple of minutes, let me sum things up fast.

We know that Stack in Java Collection API extends from Vector which internally uses an array. In other words, Java uses an array based implementation for its Stack.

So, let’s see why, between the two most popular Stack implementation - arrays and linkedlists, Java chose arrays.

Some answers were quite obvious, some weren’t :

Fair Play

A cursory look over the add and remove methods of arrays and linkedlist, which are the pillars of push and pop methods of the Stack has a constant time retrieval across the board.

Growth issues

It’s no news that arrays are fixed size and that the growth of an array is achieved by just copying the array to a bigger array. In case of our default implementation of Stack using Vector, the increment capacity is just double.

It just means if we are adding 80 elements to a stack, the internal array gets copied 4 times - at 10, 20, 40 and 80. So, say, when we are adding the 80th element, the push operation actually takes O(N) time and since our N is 80 in this case, that is going to make atleast a little pause on your program with that cruel deep copy - those valuable little cycles that you could save for some other ride.

Too bad, unlike Vectors, you wont be able to specify the initial size or the increment factor for the java.util.Stack because there are no overloaded constructors.

On the other hand, though growth hiccups frequent an ArrayQueue, ArrayQueues have a sweet overloaded constructor for initial capacity which comes in handy if you have an approximate idea on how big you stack is going to be. Also, the default initial capacity is 16 for an ArrayQueue as against 10 for a Vector.

Time and Place, my friend. Time and Place

To be fair with arrays, the objects stored in the array based stack are just references to the actual object in the heap (in case of objects) or actual values (in case of primitives).

On the other hand, in case of LinkedList, there is a Node wrapper over the top of the stored item. On an average that should cost you ~40 bytes extra space in the heap per stored object (including Node object inner class, link to the next Node and the reference to the item itself).

So, ArrayQueue or LinkedList ?

Arrays are preferred for most purposes because they offer much better speed of access due to their unique advantage of occupying sequential memory and getting to the actual object is just pointer arithmetic. However, push and pop operations on the threshold item (the item that triggers resize), takes O(n) time. However, on an average, it takes constant time (amortized constant time if you will).

On the other hand, with LinkedList, add operations are slower than arrays due to the extra time taken to construct new nodes and pointing to the new ones. Needless to mention that new nodes consume heap space other than the space consumed by the actual object. However, since there are no resizing (or need for sequential memory) and it always has a reference to the first element, it has a worst case guarantee of constant time.

Now, while you revisit the first part of this blog, feel free to say Damn you, default implementation !!!

References :

http://onjava.com/pub/a/onjava/2001/10/23/optimization.html

http://www.javaworld.com/javatips/jw-javatip130.html?page=1

http://docs.oracle.com/javase/7/docs/api/java/util/RandomAccess.html

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/Vector.java