Deque as Stack — Use Deque (ArrayDeque) as a stack (push/pop/peek) (recommended) - Java

SECTION 1

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.

1946 • Stack Concept Invented

Alan Turing described a stack-based subroutine-return mechanism, establishing LIFO as a fundamental computing pattern.

1996 • Java 1.0 — java.util.Stack

Java shipped with a Stack class extending Vector. It worked but carried synchronization baggage and exposed random-access methods that violated the stack abstraction.

2004 • Java 5 — Generics & Queue Interface

Generics arrived, and the Queue interface was introduced, but a proper double-ended queue was still missing from the standard library.

2006 • Java 6 — Deque & ArrayDeque

The 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."

Today • Industry Standard

Modern Java style guides and AP CS resources recommend 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?

SECTION 2

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

A stack only allows access to the most recently added element. You push items onto the top and pop them off the top. No skipping or reaching to the bottom.

Deque Interface

A double-ended queue supports adding and removing elements from both ends. When you restrict yourself to one end, a Deque naturally acts as a stack.

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.

✦

KEY TAKEAWAY

Think of a Deque used as a stack like a Pringles can: you can only reach the chip on top. The 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.

SECTION 3

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.

Left panel: 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.

SECTION 4

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.

TIME COMPLEXITY — STACK OPERATIONS

push(e): O(1) amortized | pop(): O(1) | peek(): O(1)

All three operations run in constant time. The 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.

SPACE COMPLEXITY

O(n) where n = number of elements in the stack

ArrayDeque stores elements contiguously in an array. There is no per-element overhead for node objects or pointers, unlike a LinkedList-based approach.

RESIZE STRATEGY

new capacity = old capacity × 2

When the internal array fills up, ArrayDeque allocates a new array of double the size and copies all elements into it. The default initial capacity is 16.

💡

Why Not LinkedList?

Java's 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.

SECTION 5

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

Mapping classic stack operations to Deque interface methods

The left panel shows the stack view where only the top (first) end is used. The right panel shows the full Deque with two ends. When you limit yourself to the first end only, the Deque becomes a stack.

⚠

Watch Out: null Values

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.

SECTION 6

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.

Reversing "HELLO" Using ArrayDeque as a Stack

1
Step 1 — Declare and Import

Import the necessary classes and declare the stack using the 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<>();

An empty stack of Character objects is created.
2
Step 2 — Push Each Character

Loop through the string "HELLO" and push each character onto the stack: String word = "HELLO"; for (char c : word.toCharArray()) { stack.push(c); }

Stack from bottom to top: [H, E, L, L, O]. The 'O' is on top.
3
Step 3 — Pop to Build Reversed String

Pop each character and append it to a StringBuilder: StringBuilder reversed = new StringBuilder(); while (!stack.isEmpty()) { reversed.append(stack.pop()); }

Pop order: O → L → L → E → H. The reversed string is "OLLEH".
4
Step 4 — Verify with peek() (optional)

Before popping, you could use 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.

Final output: "OLLEH"

💡

Code Tip: Declare as Deque, Instantiate as ArrayDeque

Always write 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.

SECTION 7

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

Comparison of three stack implementations in Java

✦

KEY TAKEAWAY

Imagine you need a container to hold books in LIFO order. 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.

SECTION 8

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

How ArrayDeque stack skills connect to advanced CS topics

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.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why the Java documentation recommends ArrayDeque over the legacy Stack class. Name at least two specific drawbacks of the Stack class.

Show answer

The legacy Stack class has two major drawbacks. First, it extends Vector, which means every operation is synchronized — an unnecessary performance cost in single-threaded programs. Second, because it inherits Vector's methods like get(int index), users can access elements in the middle of the stack, which violates the LIFO abstraction. ArrayDeque avoids both problems: it is not synchronized (faster) and does not expose random-access methods.

Question 2: BASIC

Given the following code, what is printed? 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());

Show answer

The output is: 30 20 2 After pushing 10, 20, and 30, the top of the stack is 30. pop() removes and returns 30. Then peek() returns 20 (the new top) without removing it. Finally, size() returns 2 because only 10 and 20 remain. Note that peek() does not change the stack's size — only pop() does.

Question 3: INTERMEDIATE

Write a method 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.

Show answer

Push each character of the lowercase string onto the stack. Then iterate through the original lowercase string, popping one character at a time and comparing it with the current character. If any pair doesn't match, return false. Here is one solution: boolean isPalindrome(String s) { s = s.toLowerCase(); Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) stack.push(c); for (char c : s.toCharArray()) { if (stack.pop() != c) return false; } return true; } Because the stack reverses the order of characters, comparing popped characters with the original forward order effectively checks both halves of the string simultaneously.

Question 4: APPLIED

A simple text editor supports an Undo feature. Every time the user types a character, it is pushed onto a stack. When the user presses Undo, the most recent character is popped. Given the sequence of actions below, what does the final text look like? Type 'J', Type 'a', Type 'v', Undo, Type 'v', Type 'a', Undo, Undo, Type 'a'

Show answer

Let's trace the stack state after each action: • push('J') → [J] • push('a') → [J, a] • push('v') → [J, a, v] • Undo (pop) → removes 'v' → [J, a] • push('v') → [J, a, v] • push('a') → [J, a, v, a] • Undo (pop) → removes 'a' → [J, a, v] • Undo (pop) → removes 'v' → [J, a] • push('a') → [J, a, a] Reading from bottom to top (in insertion order), the final text is "Jaa". This demonstrates how a stack naturally supports undo by reversing the most recent action first.

Question 5: CRITICAL THINKING

A student argues: "Since 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?

Show answer

The student raises a valid point: ArrayDeque does expose methods beyond strict stack operations. However, the argument is only partially correct. Unlike Stack, ArrayDeque does not offer random-access indexing like get(i), so it is a significant improvement. Still, if you want a truly strict stack interface, you could wrap ArrayDeque in your own class that only exposes push, pop, peek, isEmpty, and size. This is called the Adapter design pattern. In practice, most Java developers accept the trade-off because ArrayDeque's performance and API convenience outweigh the risk of someone accidentally using the wrong method.

SUMMARY

Lesson Summary

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.