Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 39

Mastering Java's Stack, Queue, and Deque

Recommended resources

Welcome back! In our last lesson, we built stacks and queues from the ground up using arrays and linked lists. This gave you a solid understanding of the LIFO and FIFO principles that govern these abstract data types. While that foundational knowledge is invaluable for deep understanding, in practical coding and interviews, you'll almost always use the highly optimized, pre-built implementations provided by the Java Collections Framework.

This lesson will bridge that gap from theory to practice. Our goal is to master the use of Java's standard Stack, Queue, and Deque collections. We will explore which classes to use, what their key methods are, and most importantly, why the modern best practice for implementing a stack in Java might surprise you. This knowledge is essential for writing clean, efficient, and professional-grade code for your interview problems.

1. Java's Built-in Collections

The Java Collections Framework provides a rich set of interfaces and classes for managing groups of objects. Let's look at the standard library options for stacks and queues.

A high-level view of the Java Collections Framework. Notice how `Queue` and `List` extend `Collection`, and `Deque` extends `Queue`. We'll be focusing on the classes that implement these interfaces.

1.1. The Legacy Stack Class

Java has a class named java.util.Stack that seems like the obvious choice. It provides the methods we'd expect, directly corresponding to the operations we learned in the previous lesson.

Let's watch a quick demonstration of its basic usage.

Learn Stack data structures in 10 minutes 📚

This video from Bro Code provides a very quick tour of the java.util.Stack class and its primary methods.

First, watch the brief section showing how to declare and instantiate a Stack object. Then, review the demonstration of the core methods: push, pop, peek, and empty. Notice how these directly map to the concepts from our last lesson.

The methods are straightforward:

  • push(item): Adds an item to the top.
  • pop(): Removes and returns the top item.
  • peek(): Returns the top item without removing it.
  • empty(): Returns true if the stack is empty.

However, despite its name, java.util.Stack is a legacy class and is generally not recommended for new code. We are about to see why and what the modern alternative is.

1.2. The Queue Interface

Unlike Stack, Queue in Java is an interface. This means you cannot instantiate it directly (new Queue<>() is not valid). Instead, you create an instance of a class that implements the Queue interface, such as LinkedList or ArrayDeque. For standard FIFO queue behavior, LinkedList is a common choice.

The core Queue methods also have two "flavors": one that throws an exception on failure and another that returns a special value (null or false). For robustness, it's almost always better to use the latter.

  • Add element: offer(item) (returns false if it fails) is preferred over add(item) (throws exception).
  • Remove element: poll() (returns null if empty) is preferred over remove() (throws exception).
  • Examine element: peek() (returns null if empty) is preferred over element() (throws exception).

This video gives a clear walkthrough.

Learn Queue data structures in 10 minutes 🎟️

This video, also from Bro Code, explains why Queue is an interface and demonstrates its primary methods using a LinkedList implementation.

First, watch the segment that explains why Queue is an interface and must be instantiated using a class like LinkedList. Then, focus on the explanation of the offer, poll, and peek methods, and the reasoning for preferring them over their exception-throwing counterparts.

2. The Modern Approach: Deque and ArrayDeque

Now we arrive at the modern, recommended way to handle both stacks and queues: the Deque interface. Deque stands for "Double-Ended Queue," meaning it's a data structure that supports adding and removing elements from both ends.

Because it supports both, it can perfectly model both a LIFO stack (adding/removing from one end) and a FIFO queue (adding to one end, removing from the other). The most common and efficient implementation of Deque is ArrayDeque.

This diagram illustrates the versatility of a Deque. It can operate as a FIFO Queue by inserting at the rear and removing from the front, or as a LIFO Stack by inserting and removing from the same end (the front).

So, why is Deque preferred over the old Stack class? There are several critical reasons that are important to understand for interviews.

Java Deque vs. Stack

This Baeldung article provides an excellent, in-depth comparison and is considered a definitive source on this topic. It explains exactly why modern Java development favors Deque.

Please read the following sections carefully: Class vs. Interface: Read this section to understand the object-oriented design benefits of using an interface (Deque) over a rigid class (Stack). Performance: Read the section on synchronized Methods. It explains that Stack inherits from Vector, which makes all its methods synchronized. This introduces performance overhead that is unnecessary in the single-threaded context of most interview problems. ArrayDeque does not have this overhead. Iteration Order: The section on iteration order shows another subtle but important difference. When you iterate over a Deque used as a stack, you get elements from top to bottom, which is the intuitive order. Stack iterates from bottom to top. LIFO Contract: Finally, read about how Stack breaks the LIFO contract. Because it's a subclass of Vector, it allows indexed access (e.g., get(0) to access the bottom element), which violates the core principle of a stack.

The conclusion is clear: for stack operations, you should use a Deque implementation like ArrayDeque.

3. Your Go-To Cheat Sheet for Interviews

Let's distill this into a practical guide. When you face a problem requiring a stack or queue in a Java interview, here is what you should do.

Java Coding Interview Cheat Sheet — Complete Collections & Syntax Guide

This cheatsheet from intervu.dev gives concise, practical advice for using Java collections in an interview setting.

Read the section titled "Stack (LIFO), Queue (FIFO), and Deque". It summarizes the methods and reinforces the best practice: use ArrayDeque for stacks and either ArrayDeque or LinkedList for queues.

Here is a summary of the recommended approach:

Data Structure How to Declare Add Remove Examine
Stack (LIFO) Deque<T> stack = new ArrayDeque<>(); stack.push(e) stack.pop() stack.peek()
Queue (FIFO) Queue<T> queue = new ArrayDeque<>(); queue.offer(e) queue.poll() queue.peek()

A note on ArrayDeque vs. LinkedList for Queues:
While Queue<T> q = new LinkedList<>(); is very common and perfectly correct, ArrayDeque is often slightly more performant for queue operations due to better cache locality (being array-based). Unless the problem involves specific scenarios where you're manipulating the middle of the collection (which isn't a queue operation anyway), ArrayDeque is an excellent default choice for both stacks and queues.

Conclusion

Today, we've transitioned from the theoretical implementation of stacks and queues to their practical application using the Java Collections Framework. You now have the knowledge to choose the right tools for the job, a crucial skill for any software developer.

Key Takeaways:

  • java.util.Stack is legacy: Avoid it due to performance issues (synchronization) and design flaws (violates LIFO by allowing indexed access).
  • Queue is an interface: Use an implementing class like ArrayDeque or LinkedList. Prefer methods like offer(), poll(), and peek() that don't throw exceptions.
  • Deque is the modern, versatile choice: The ArrayDeque implementation should be your default for stack (LIFO) operations. It can also be used for queue (FIFO) operations and is often faster than LinkedList.
  • For interviews: Use Deque<T> stack = new ArrayDeque<>(); for stacks. This demonstrates your knowledge of modern Java best practices.

In the next lesson, we will immediately apply what we've learned. We'll tackle the classic "Valid Parentheses" problem, a quintessential interview question that is elegantly solved using a stack.