Ctrl+Z does not search the document for “the last change.” A brace matcher does not scan the file looking for a partner. A method return does not hunt the heap for “whoever called me.” Each of those jobs only ever needs the most recent unfinished item. That is not three structures. It is one contract.
A stack is last-in, first-out: the item you just pushed is the only one you can pop. The Data Structures Roadmap already defined ADT versus implementation and amortized versus worst-case. This post stays on the LIFO contract, the two layouts that deliver it, the JDK type you actually want, and the jobs that are the same shape.
The ADT: push, pop, peek
Four operations. That is the whole interface:
| Operation | Contract |
|---|---|
push(x) | Put x on top. |
pop() | Remove and return the top. Empty is an error. |
peek() | Return the top without removing it. Empty is an error. |
isEmpty() | True when there is nothing to pop. |
LIFO is the rule, not a performance hint. You cannot reach the third item without popping the two above it. If that sounds like a limitation, it is — and it is the limitation that makes undo, braces, and call frames cheap. You never search. You never index. You only ever touch the top.
A tiny session of edits shows the order without any Java type yet:
push("type Hello")
push("bold Hello")
push("delete o")
pop() -> "delete o" (undo that)
peek() -> "bold Hello" (still there)
pop() -> "bold Hello"
pop() -> "type Hello"
pop() -> empty — stopThe oldest item sits at the bottom until everything newer is gone. That is the whole ADT.
Two layouts, same contract
An ADT is a promise. An implementation is a layout. Two layouts keep the top cheap.
Contiguous. A growable array with the top at the end. push appends. pop drops the last slot. Index i is unused — you never ask for it. Append is amortized O(1) because the backing array sometimes doubles; the hub already covered that average. Between growths, push and pop are pointer arithmetic on one block.
Linked. A singly linked list with the top at the head. push allocates a node and points it at the old head. pop walks one pointer. No sliding, no doubling. You pay a node object and a pointer chase per item, and you lose the cache-friendly scan an array gives you.
Both are O(1) at the top. They differ on constants, growth, and what else you might later ask of the storage:
Array (top at end) Linked (top at head)
push amortized O(1) O(1)
pop / peek O(1) O(1)
extra space unused array slots one node per item
growth copy on doubling none
random access you could, but don't walk from the headReach for the array layout unless you have a reason the linked one is cheaper — a hard cap on allocations, or a node you already hold for some other structure. In Java you almost never hand-roll either. You pick a type that already is the array layout.
Java: ArrayDeque, not Stack
The type that matches “stack” in the JDK is ArrayDeque used through Deque:
Deque<String> undo = new ArrayDeque<>();
undo.push("type Hello");
undo.push("bold Hello");
String last = undo.pop(); // "bold Hello"
String next = undo.peek(); // "type Hello"push / pop / peek sit on Deque. They operate at the head of a circular array. That is still LIFO and still amortized O(1) — the textbook “top at the high index” picture is the same layout with a different end labelled top. You do not need a class named Stack.
java.util.Stack is a synchronized subclass of Vector. The name matches the textbook. The layout is a 1990s growable array with a lock on every call, an inheritance relationship nobody asked for, and an API that predates Deque. Vector is the same family: a synchronized list.
Prefer the Deque constructor:
Deque<Edit> undo = new ArrayDeque<>();
// Avoid as a default
Stack<Edit> undo = new Stack<>();Note: ArrayDeque rejects null. push(null) throws NullPointerException. That is a feature: you cannot confuse “empty” with “a null on top.” Model a missing payload as a real type, not as null.
ArrayDeque also has no capacity tax you have to think about on day one. It grows like an ArrayList. For a stack of edits, tokens, or frames, that is the right bill.
Undo is a stack of inverse actions
An editor does not store “the whole document as of step 47.” It stores the inverse of each change, in the order the changes happened. Undo pops one inverse and applies it. Redo is a second stack that receives what undo popped — still LIFO, just the other direction.
sealed interface Inverse permits Restore, Remove {}
record Restore(int at, String text) implements Inverse {}
record Remove(int at, int length) implements Inverse {}
final class Editor {
private final StringBuilder doc = new StringBuilder();
private final Deque<Inverse> undo = new ArrayDeque<>();
void insert(int at, String text) {
doc.insert(at, text);
undo.push(new Remove(at, text.length()));
}
void delete(int at, int length) {
String gone = doc.substring(at, at + length);
doc.delete(at, at + length);
undo.push(new Restore(at, gone));
}
void undo() {
if (undo.isEmpty()) {
return;
}
switch (undo.pop()) {
case Restore(var at, var text) -> doc.insert(at, text);
case Remove(var at, var length) -> doc.delete(at, at + length);
}
}
}The document is not a stack. The history is. Searching a list of edits for “the last one the user cares about” would be a different job, and a worse layout for Ctrl+Z.
Braces are a stack of unfinished openers
A parser does not need random access into the source. It needs to know, at each closer, which opener is still unmatched. Push on '(', '[', '{'. Pop on the matching closer. A mismatch or a leftover opener is a syntax error.
boolean balanced(String source) {
Deque<Character> open = new ArrayDeque<>();
for (int i = 0; i < source.length(); i++) {
char c = source.charAt(i);
switch (c) {
case '(', '[', '{' -> open.push(c);
case ')' -> {
if (open.isEmpty() || open.pop() != '(') {
return false;
}
}
case ']' -> {
if (open.isEmpty() || open.pop() != '[') {
return false;
}
}
case '}' -> {
if (open.isEmpty() || open.pop() != '{') {
return false;
}
}
default -> { }
}
}
return open.isEmpty();
}Walk a few inputs so the empty-stack cases are obvious:
"(a[b]{c})" push ( [ { pop } ] ) empty -> true
"(a[b)]" push ( [ pop sees ) top is [ -> false
"((a)" push ( ( leftover ( -> false
")" pop on empty -> falseThe same walk parses nested XML tags, indentation blocks, and “this if owns that else.” You are not searching. You are matching the most recent unfinished opener. That is LIFO again.
Call frames are a stack the runtime already owns
Every method call pushes a frame: locals, arguments, return address. return pops it. Recursion is the same machine with the same frame shape, repeated. StackOverflowError is the array (or native stack segment) running out of slots, not a mysterious JVM curse.
You do not implement this with ArrayDeque. The JVM already did. The reason to mention it here is the shape: the callee cannot finish before the caller, and the caller cannot see the callee’s locals without a protocol that is still “the top frame.” Debugging “who called this?” is peeking. Tail-call elimination, when a runtime has it, is the special case that reuses the top frame instead of pushing — which is how you know the default is a stack.
If you simulate recursion yourself — a depth-first walk, an expression evaluator, a backtracking search — you push a frame-like record onto ArrayDeque and pop when that node is done. Same ADT. Same O(1) top.
Complexity at the top
For the ADT operations on ArrayDeque (array layout, top at the head of the deque):
| Operation | Cost |
|---|---|
push | Amortized O(1) |
pop | O(1) |
peek | O(1) |
isEmpty / size | O(1) |
| Search for a value | O(n) — you are using the wrong structure |
Hot path is always the top. Amortized growth on push is the only asterisk, and it is the same asterisk as ArrayList.add. If you need a hard O(1) with no doubling — a real-time loop with a known bound — pre-size the deque or use a fixed array of frames. Most backend code never needs that.
Linked-list stacks are also O(1) push/pop. They lose on locality and on the extra node per item. In the JDK, LinkedList implements Deque too; it is the wrong default for a stack for the same reason it is the wrong default for a queue unless you already need the list API.
When not to use a stack
A stack is the wrong layout the moment the hot operation is not “the most recent item.”
You need FIFO. Work arrives in order and must leave in the same order: request queues, bounded buffers, “next customer.” That is a queue. Using a stack silently reverses the order. The jobs look similar in code — push versus offer, pop versus poll — and the bug is a reordering you only see under load.
You need random access. “Give me edit 17,” “the third unmatched brace,” “frame i in a dump you will index.” A stack can only answer those by popping, which destroys the structure, or by cheating and treating the backing array as a list. If you need index i, you wanted a list.
You need to search or dedupe. “Have we already seen this token?” is a set. “Which request id is in flight?” is a map. Walking a stack to find a value is O(n) and throws away the LIFO reason you picked it.
You need both ends. Undo and “drop the oldest” on a bounded history is a deque used as a deque, not as a stack. Stay here if you only ever touch the top. When both ends are hot, the next layout in this series is the one that names both ends on purpose — until that post ships, ArrayDeque already is that type; just call addLast / removeFirst instead of push / pop.
Do not reach for a stack as a “faster list.” It is not. It is a list with most of the API deleted so the remaining operations stay honest.
Cheat sheet
ADT: LIFO — push, pop, peek, isEmpty
Layout: array (top at end) or linked (top at head)
JDK: Deque<E> stack = new ArrayDeque<>();
Avoid: java.util.Stack, Vector
push / pop: O(1) (push amortized on the array layout)
Jobs: undo, brace/tag matching, call frames, DFS/backtracking
Not jobs: FIFO, index i, search, uniqueness
null: ArrayDeque rejects itDo:
- Name the hot operation first. If it is “the most recent unfinished item,” you want a stack.
- Use
ArrayDequethroughDequeand thepush/pop/peeknames so the code reads as LIFO. - Treat empty
pop/peekas a bug in the caller, or checkisEmptywhen “nothing to undo” is a valid user action.
Don’t:
- Construct
new Stack<>()ornew Vector<>()because the textbook said “stack.” - Push
nulland then wonder whetherpeek() == nullmeans empty. - Walk the stack to find a value, or index into it, and still call it a stack.
- Use LIFO for work that must leave in arrival order.
Wrap-up
Undo, brace matching, and the call stack are the same job: only the top unfinished item is legal to finish next. That job is a stack — LIFO as an ADT, O(1) at the top, array layout in practice, ArrayDeque in Java.
The glossary for ADT versus implementation, amortized growth, and the rest of the JDK map lives on the Data Structures Roadmap. Come back here when a feature is secretly “the most recent thing” and someone has stored it in a list they search on every keystroke.