Java Stack

A stack is a last-in-first-out collection: you push an item on, and the next pop returns whatever you put on most recently. Java has two ways to build one — the legacy java.util.Stack class from 1995, and the modern recommendation of Deque<E> (typically ArrayDeque). Both work, both have the same conceptual operations, but the official Javadoc on Stack itself tells you to prefer Deque. This chapter shows you what Stack looks like, why the JDK now points elsewhere, and how to use the recommended replacement.

What a stack is for

Stacks show up in any algorithm that's naturally last-in-first-out:

• Undo / redo histories — each new action is pushed; undo pops the latest.
• Parser and interpreter state — expression evaluation, balanced-bracket checks, call frames.
• Depth-first traversal — push successors, pop the next node to visit.
• Reversing things — push every element of a sequence, then pop them off.

The shape is always the same: push, pop, peek, isEmpty, size. Five operations.

The legacy Stack class

java.util.Stack<E> extends Vector<E>, which means it inherits everything in the previous chapter — including the per-method synchronized, the legacy method names, and the awkward fact that it's a List. A Stack is, by inheritance, an indexable list — you can call stack.get(3) on it, which is exactly the kind of API mistake that motivates the recommendation to use Deque.

Stack<String> s = new Stack<>();
s.push(\"a\");
s.push(\"b\");
s.push(\"c\");
System.out.println(s.peek());   // c
System.out.println(s.pop());    // c
System.out.println(s.size());   // 2
System.out.println(s.empty());  // false  (note: empty(), not isEmpty())

Six methods specific to Stack:

• E push(E item) — add to top. Returns the item.
• E pop() — remove and return the top. Throws EmptyStackException if empty.
• E peek() — top without removing. Same exception.
• boolean empty() — note the lower-case spelling, distinct from Collection.isEmpty().
• int search(Object o) — 1-based distance from the top, or -1 if not present. Odd choice — the result is "how many pops to reach o," which is rarely useful.

Everything else is inherited from Vector and List.

Why the Javadoc points you to Deque

Open the actual Javadoc for Stack in any modern JDK and you'll find the line:

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

The reasons line up with the previous chapter on Vector:

• Stack is synchronised on every method. You pay the lock cost even in single-threaded code, and the synchronisation is at the wrong granularity for any compound op.
• Stack is a List. Indexed access on a stack is a category error — it lets you peek into the middle, which violates the LIFO discipline the class is supposed to enforce.
• The five stack ops you actually want are already on Deque (push, pop, peek, isEmpty, size), and ArrayDeque is the fastest implementation in the JDK.

In short: Stack works, but it's a 1995 design wedged into a 1998 framework. New code should use Deque.

The recommended replacement

The idiom is one line:

Deque<String> stack = new ArrayDeque<>();

Then call push, pop, peek. The Deque interface defines them as addFirst, removeFirst, peekFirst under the hood, so the top of the stack is the head of the deque.

Deque<String> calls = new ArrayDeque<>();
calls.push(\"main\");
calls.push(\"parseArgs\");
calls.push(\"split\");
System.out.println(calls.peek());      // split
System.out.println(calls.pop());       // split
System.out.println(calls);              // [parseArgs, main]

Three details to know:

1. peek() on a Deque returns null when empty; peek() on Stack throws. peekFirst() is the same null-returning form. If you'd rather have the exception, call getFirst() (or element()).
2. The same pop() / removeFirst() distinction applies: pop() throws when empty.
3. ArrayDeque rejects null elements. Use it for non-null values only — which is the usual case for stacks.

When Stack is acceptable in new code

Almost never, and the bar is low:

• Maintaining old code that already uses it — don't churn just to swap the class.
• Working with an API that requires Stack specifically — extremely rare. The Swing classes that used Vector and friends don't tend to require Stack.

For everything else, declare Deque<E> and instantiate ArrayDeque<>.

A worked example: parentheses matcher, two ways

The program below uses both Stack and Deque<Character> to solve the classic balanced-parentheses puzzle. Same algorithm, two implementations — read it side by side, then look at the Deque form and decide which you'd rather read in three months.

What's worth noticing:

• The two functions are identical apart from the type name and empty() vs isEmpty(). There's no algorithmic reason to prefer Stack — the code reads the same.
• The "Stack-specific API" block at the bottom is the case against the legacy class: empty() is a different name from the rest of the framework, search() returns a 1-based distance (rare in the rest of Java), and get(0) lets you reach into the middle of a stack — defeating the whole point of the abstraction.

What's next

You've now seen the three workhorse List implementations (ArrayList, LinkedList, Vector) and the LIFO specialisation built on top of Vector. The next four chapters cover the parallel story for things-you-add-and-take-out-in-order: the Queue interface, PriorityQueue, ArrayDeque, and the more general Deque contract.

Practice