DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
Building Scalable Real-Time Apps with AstraDB and Vaadin
Register Now

Trending

  • Build a Simple Chat Server With gRPC in .Net Core
  • How To Scan and Validate Image Uploads in Java
  • Demystifying SPF Record Limitations
  • How Agile Works at Tesla [Video]

Trending

  • Build a Simple Chat Server With gRPC in .Net Core
  • How To Scan and Validate Image Uploads in Java
  • Demystifying SPF Record Limitations
  • How Agile Works at Tesla [Video]
  1. DZone
  2. Data Engineering
  3. Data
  4. Why Future Generations Will Hate You for Using java.util.Stack

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

Arun Manivannan user avatar by
Arun Manivannan
·
Sep. 13, 12 · Interview
Like (0)
Save
Tweet
Share
18.53K Views

Join the DZone community and get the full member experience.

Join For Free

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.

Stack Options

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

Data structure Implementation

Published at DZone with permission of Arun Manivannan, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Trending

  • Build a Simple Chat Server With gRPC in .Net Core
  • How To Scan and Validate Image Uploads in Java
  • Demystifying SPF Record Limitations
  • How Agile Works at Tesla [Video]

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com

Let's be friends: