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 !!!

Related links :

Reference: Why Future Generations Will Hate You for Using java.util.Stack from our JCG partner Arun Manivannan at the Rerun.me blog.

Related Whitepaper:

Bulletproof Java Code: A Practical Strategy for Developing Functional, Reliable, and Secure Java Code

Use Java? If you do, you know that Java software can be used to drive application logic of Web services or Web applications. Perhaps you use it for desktop applications? Or, embedded devices? Whatever your use of Java code, functional errors are the enemy!

To combat this enemy, your team might already perform functional testing. Even so, you're taking significant risks if you have not yet implemented a comprehensive team-wide quality management strategy. Such a strategy alleviates reliability, security, and performance problems to ensure that your code is free of functionality errors.Read this article to learn about this simple four-step strategy that is proven to make Java code more reliable, more secure, and easier to maintain.

Get it Now!  

Leave a Reply

9 + = thirteen

Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

15,153 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books