Home » Java » Core Java » Stacks and Queues in Java

About Shaun Abram

Shaun Abram

Stacks and Queues in Java

I have been working on some Java code recently that required both a stack and a queue. The choices to use aren’t immediately obvious. There is a Queue interface, but no clear concrete implementation to use. There is also a Stack class, but the javadocs point out that other classes “should be used in preference to this class”. So, what implementation do you use for stacks and queues in Java?

I found my quick rule of thumb to be that you can use the ArrayDeque class for both Stack and Queues, but some more details are below.

Common Definitions

First, let’s start with some definitions. In common usage of the word, a queue is FIFO (first-in-first-out). Just like the first person in line at the post office gets served first. A stack is LIFO (last in first out). Think of a stack of books – the last book you put on the stack is the first book you take off.

Choices in Java

In Java, things are a little more complicated, but the same principles apply. There is the aforementioned Queue interface which has the expected methods to add, remove and look at elements. (Actually, those methods come in two flavors: one throws an exception if the operation fails, the other returns a special value such as null or false; see more here).

There is also a sub-interface of Queue called Deque, short for “double ended queue” and is usually pronounced “deck”. This interface defines methods to access the elements at both ends of the collection. This functionality makes Deque a useful base for both queue and stack implementations.

However, both Queue and Deque are interfaces, so we still haven’t found a concrete implementation to use yet…

The shortlist: ArrayDeque & LinkedList

The 2 main choices are: ArrayDeque and LinkedList. There are a couple of other implementation of Deque such as ConcurrentLinkedDeque and LinkedBlockingDeque, and a plethora of implementations of Queue such as DelayQueue, LinkedBlockingDeque and PriorityQueue. Since those are more specialized (and I haven’t used them much), I won’t go into here.


From the javadocs, ArrayDeque is a resizable-array implementation of the Deque interface. Most ArrayDeque operations run in amortized constant time (i.e. slower “once in a while”, but on average constant) except for remove*, contains* and the bulk operations, all of which run in linear time. The docs point out that this class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. It is this statement that leads me to use ArrayDeque as my default implmentation for both stacks and queues.


The LinkedList class implements the List, Queue and Deque interfaces. In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue.

LinkedList vs ArrayDeque

So, when would you use a LinkedList over an ArrayDeque?

Pros of a LinkedList implementation are:

  • more flexible than the ArrayDeque implementation, as it
    • implements all optional list operations.
    • allows null elements (not allowed in ArrayDeque)
  • well suited when you need to remove/insert items in the middle of the list frequently (something that can result in large array copies for the ArrayDeque).

Cons of a LinkedList implementation:

  • not ideal when iterating over items in general
  • consumes more memory than the ArrayDeque implementation


In terms of efficiency, ArrayDeque is more efficient than the LinkedList for iteration and add/remove operation at both ends. So, as the javadocs point out, in general, ArrayDeque is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

Reference: Stacks and Queues in Java from our JCG partner Shaun Abram at the Shaun Abram’s blog blog.
(0 rating, 0 votes)
You need to be a registered member to rate this.
3 Comments Views Tweet it!
Do you want to know how to develop your skillset to become a Java Rockstar?
Subscribe to our newsletter to start Rocking right now!
To get you started we give you our best selling eBooks for FREE!
1. JPA Mini Book
2. JVM Troubleshooting Guide
3. JUnit Tutorial for Unit Testing
4. Java Annotations Tutorial
5. Java Interview Questions
6. Spring Interview Questions
7. Android UI Design
and many more ....
I agree to the Terms and Privacy Policy

Leave a Reply

2 Comment threads
1 Thread replies
Most reacted comment
Hottest comment thread
2 Comment authors
John MathewsRey Mark Joy Z. Tamayo Recent comment authors

This site uses Akismet to reduce spam. Learn how your comment data is processed.

newest oldest most voted
Notify of
Rey Mark Joy Z. Tamayo
Rey Mark Joy Z. Tamayo

sir give more examples for these problem because it is useful to us as an IT student for today.

Rey Mark Joy Z. Tamayo
Rey Mark Joy Z. Tamayo

..or leave some information about STACK AND QUEUES.,
Thank You.

John Mathews
John Mathews

Thank you for the tutorial. I found this resource for a java stacks queues tutorial. They cover an implementation through a linked list. Does it matter if you build it from scratch or through a linked list?