Historical Context & Motivation
The concept of a stack — a collection where the last item added is the first item removed — is one of the oldest ideas in computer science. Think of a stack of cafeteria trays: you always grab the tray on top, and new trays go on top as well. This Last-In, First-Out (LIFO) behavior powers everything from the "Undo" button in your text editor to the way your computer tracks method calls while running a program.
Java has offered a Stack class since its very first release in 1996. However, that original class has well-known design flaws — it extends Vector, which adds unnecessary synchronization overhead and exposes methods that break the stack abstraction. Over the years, Java's designers introduced better alternatives, culminating in the recommendation to use ArrayDeque whenever you need stack behavior.
Stack class extending Vector. It worked but carried synchronization baggage and exposed random-access methods that violated the stack abstraction.Queue interface was introduced, but a proper double-ended queue was still missing from the standard library.Deque interface and its array-backed implementation ArrayDeque were added. Official Javadoc stated: "This class is likely to be faster than Stack when used as a stack."ArrayDeque as the go-to stack implementation. The legacy Stack class is considered effectively deprecated.So the question this lesson addresses is straightforward: how do you use ArrayDeque to get clean, efficient stack behavior in Java — and why should you prefer it over the legacy Stack class?
Core Principles & Definitions
Before writing any code, you need to understand three key ideas: what a stack does, what a Deque (pronounced "deck") is, and why ArrayDeque is the recommended implementation. These concepts build on each other, so let's take them one at a time.
LIFO — Last-In, First-Out
Deque Interface
ArrayDeque Implementation
ArrayDeque stores elements in a resizable circular array. It has no synchronization overhead and never wastes memory on node pointers, making it faster and leaner than alternatives.Three Core Operations
push(e) adds to the top, pop() removes from the top, and peek() looks at the top without removing it. All three run in O(1) — constant time.Deque interface is the can's shape (it technically has two ends), but when you use only push, pop, and peek, you're choosing to open only one end — giving you a perfect LIFO stack.Visual Explanation — Stack Operations
The diagram below illustrates how an ArrayDeque behaves when used as a stack. Each operation interacts only with the top of the stack, which maps to the first position of the underlying deque. Follow the three panels from left to right to see push, peek, and pop in action.
push("C") places a new element on top of the stack. Center panel: peek() returns the top element without changing the stack. Right panel: pop() removes and returns the top element, shrinking the stack by one.Notice that every operation targets only the top of the stack. Internally, ArrayDeque maps "top" to the first position of its circular array. The methods push, pop, and peek are actually aliases for addFirst, removeFirst, and peekFirst. This means the "top" of your stack lives at index 0 of the deque.
How ArrayDeque Works Internally
Understanding the mechanism behind ArrayDeque will help you see why it is so efficient. At its heart, the class maintains a circular array (also called a ring buffer) and two integer pointers: head and tail. When you push an element, the head pointer moves backward to make room; when you pop, it moves forward. Because the array is circular, the pointer wraps around when it reaches the beginning, reusing empty slots without shifting elements.
push operation is "amortized" O(1) because the array occasionally needs to double in size, but that resize cost averages out to O(1) per operation over many pushes.ArrayDeque stores elements contiguously in an array. There is no per-element overhead for node objects or pointers, unlike a LinkedList-based approach.ArrayDeque allocates a new array of double the size and copies all elements into it. The default initial capacity is 16.LinkedList also implements the Deque interface, so technically you could use it as a stack. However, each node in a linked list allocates a separate object with two pointers, consuming extra memory and causing more cache misses. ArrayDeque stores everything in a single contiguous array, which modern CPUs can access much faster. For stack usage, ArrayDeque is almost always the better choice.Method Mapping — Deque Methods as Stack Methods
One of the trickiest parts of using ArrayDeque as a stack is remembering which Deque methods correspond to the classic stack operations. The table below maps the familiar stack vocabulary to the Deque interface methods. It also shows what happens when the stack is empty — some methods throw exceptions while others return null.
| Stack Operation | Deque Method (throws) | Deque Method (returns null) | Description |
|---|---|---|---|
push(e) | addFirst(e) | offerFirst(e) | Adds element to the top of the stack |
pop() | removeFirst() | pollFirst() | Removes and returns the top element |
peek() | getFirst() | peekFirst() | Returns the top element without removal |
isEmpty() | — | — | Returns true if the stack has no elements |
size() | — | — | Returns the number of elements in the stack |
ArrayDeque does not allow null elements. This is actually a safety feature — it means that when peek() returns null, you know for certain the stack is empty, with no ambiguity about whether a null was actually stored.Worked Example — Reversing a String with a Stack
One classic application of a stack is reversing a sequence. Because a stack outputs elements in the opposite order they were inserted (LIFO), pushing each character of a string and then popping them all produces the reversed string. Let's walk through a complete Java program using ArrayDeque.
Deque interface as the variable type. This is a best practice called "programming to the interface."
import java.util.ArrayDeque;
import java.util.Deque;
Deque<Character> stack = new ArrayDeque<>();Character objects is created."HELLO" and push each character onto the stack:
String word = "HELLO";
for (char c : word.toCharArray()) {
stack.push(c);
}StringBuilder:
StringBuilder reversed = new StringBuilder();
while (!stack.isEmpty()) {
reversed.append(stack.pop());
}"OLLEH".stack.peek() to check the top element without removing it. For example, after all pushes, stack.peek() would return 'O'. After all pops, stack.peek() would return null because the stack is empty."OLLEH"Deque<Type> stack = new ArrayDeque<>(); rather than ArrayDeque<Type> stack = new ArrayDeque<>();. Using the interface type on the left side of the assignment makes your code more flexible — you could swap in a different Deque implementation later without changing any other line.ArrayDeque vs. Stack vs. LinkedList
Java gives you three common ways to implement stack behavior: the legacy Stack class, LinkedList (which implements Deque), and ArrayDeque. The table below compares them across several important dimensions. As you'll see, ArrayDeque comes out ahead in almost every category.
| Feature | java.util.Stack | LinkedList | ArrayDeque ✓ |
|---|---|---|---|
| Underlying structure | Synchronized resizable array (Vector) | Doubly-linked list | Resizable circular array |
| push / pop speed | O(1) amortized, but synchronization adds overhead | O(1), but allocates a new node object each time | O(1) amortized — fastest in practice |
| Memory efficiency | Moderate — no extra node overhead | Poor — each element needs a node with two pointers | Best — compact contiguous array |
| Thread safety | Synchronized (rarely needed) | Not synchronized | Not synchronized |
| Allows null? | Yes | Yes | No — cleaner semantics |
| Breaks stack abstraction? | Yes — inherits random-access get(i) from Vector | Partially — exposes queue and list methods | Partially — exposes both ends, but no random access |
| Recommended? | No — legacy class | Only if you also need linked list features | Yes — official recommendation |
Stack is like an old, heavy wooden crate with a padlock (synchronized) that also has a side door letting anyone grab a book from the middle. LinkedList is a chain of small boxes — flexible but uses extra chain links (pointers). ArrayDeque is a lightweight spring-loaded tray dispenser — fast, compact, and designed so you can only access the top.Connection to Advanced Topics
Once you are comfortable using ArrayDeque as a stack, you have a tool that shows up in many advanced algorithms and real-world applications. The table below previews some of these connections, so you know where your stack knowledge is headed next.
| This Lesson | Advanced Topic |
|---|---|
| push / pop / peek basics | Balanced parentheses checker — use a stack to match opening and closing brackets in expressions like ((a + b) * c) |
| LIFO order | Depth-First Search (DFS) — graph traversal uses an explicit stack (or recursion, which uses the call stack internally) |
| Reversing sequences | Undo/Redo systems — two stacks can track actions and their reversals in text editors and drawing apps |
| Deque as stack (one end) | Deque as queue (both ends) — the same ArrayDeque can serve as a FIFO queue by using addLast / removeFirst |
| Single-threaded stack | Concurrent stacks — ConcurrentLinkedDeque for multi-threaded environments |
The most important takeaway for your future studies is that the stack abstraction is everywhere. Method calls, expression evaluation, backtracking algorithms, and even your web browser's "Back" button all rely on LIFO behavior. Mastering ArrayDeque now gives you a reliable, efficient tool that you will use over and over as you advance in computer science.
Practice Problems
ArrayDeque over the legacy Stack class. Name at least two specific drawbacks of the Stack class.Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println(stack.pop());
System.out.println(stack.peek());
System.out.println(stack.size());boolean isPalindrome(String s) that uses an ArrayDeque as a stack to determine whether a given string reads the same forwards and backwards. Ignore case. For example, isPalindrome("Racecar") should return true.ArrayDeque exposes methods for both ends of the deque (like addLast and removeLast), it doesn't truly enforce the stack abstraction. It's just as broken as Stack." Evaluate this argument. Is the student correct? How could you design around this concern?Lesson Summary
When you need stack (LIFO) behavior in Java, the recommended approach is to declare a Deque variable and instantiate it with ArrayDeque. The three core operations — push(e) to add an element to the top, pop() to remove the top element, and peek() to view the top without removing it — all run in O(1) constant time. Internally, ArrayDeque uses a resizable circular array, which is both memory-efficient and CPU-cache-friendly.
Avoid the legacy java.util.Stack class because it inherits synchronized methods and random-access indexing from Vector, both of which are undesirable for stack use. Likewise, while LinkedList implements Deque, its per-node memory overhead makes it slower in practice. The pattern Deque<Type> stack = new ArrayDeque<>(); is the modern, idiomatic Java way to create a stack — commit it to memory and use it whenever LIFO processing is needed.