Java Stack

Java Stack

java.util.Stack<E> is Java's original LIFO (Last-In, First-Out) data structure, available since Java 1.0. Push an element to the top, pop the most recently added element, or peek at the top without removing it — these five operations define the entire Stack contract. The problem is that Stack extends Vector, which means it inherits a global lock on every operation, exposes index-based List methods that have no meaning on a pure stack, and grows at twice the memory footprint of ArrayList. The Java documentation explicitly recommends ArrayDeque as the correct replacement for all stack use cases in new code.

What Is Java Stack?

java.util.Stack<E> is a concrete class in java.util that adds five stack-specific methods on top of everything it inherits from Vector<E>. It implements the classic LIFO discipline — the last element pushed is always the first element popped.

java.lang.Iterable<E>
    └── java.util.Collection<E>
            └── java.util.List<E>
                    └── java.util.AbstractList<E>
                            └── java.util.Vector<E>          ← synchronised, legacy
                                    └── java.util.Stack<E>   ← THIS CLASS

java.util.Deque<E>
    └── java.util.ArrayDeque<E>    ← RECOMMENDED REPLACEMENT
    └── java.util.LinkedList<E>    ← also implements Deque

KEY FACTS:
  Package         : java.util
  Since           : Java 1.0  (predates Collections Framework — Java 1.2)
  Extends         : Vector<E>  (synchronised, resizable array)
  Implements      : List<E>, RandomAccess, Cloneable, Serializable
  Discipline      : LIFO — Last-In, First-Out
  Synchronisation : YES — inherits from Vector (every method locked)
  Null elements   : allowed (Vector allows nulls)
  Stack-specific methods : push, pop, peek, empty, search (5 methods only)
  Status          : LEGACY — use ArrayDeque for new code

Basic Overview — Stack Operations and the Problem

THE FIVE STACK METHODS:
  push(E item)        ← add to top; returns the item
  pop()               ← remove and return top; throws EmptyStackException if empty
  peek()              ← return top without removing; throws EmptyStackException if empty
  empty()             ← returns true if stack has no elements
  search(Object o)    ← 1-based position from top (1 = top); -1 if not found

STACK DIAGRAM — LIFO (vertical, top at right):
  Initial: []
  push("A"):  [A]           ← A is at top
  push("B"):  [A, B]        ← B is at top
  push("C"):  [A, B, C]     ← C is at top
  peek():     [A, B, C]     returns "C", stack unchanged
  pop():      [A, B]        returns "C", C removed
  pop():      [A]           returns "B", B removed
  empty():    false
  pop():      []            returns "A", A removed
  empty():    true
  pop():      throws EmptyStackException

THE DESIGN PROBLEM — Vector inheritance leaks List methods:

  Stack<String> stack = new Stack<>();
  stack.push("A"); stack.push("B"); stack.push("C");

  // LIFO stack methods — correct
  stack.pop();               // "C" — top
  stack.peek();              // "B" — top after pop

  // LEAKED Vector/List methods — break LIFO encapsulation
  stack.add(0, "INJECTED"); // inserts at BOTTOM — violates LIFO
  stack.get(0);             // random access — no meaning on a stack
  stack.remove(1);          // removes by index — not LIFO
  stack.set(0, "REPLACED"); // replaces by index — not LIFO
  stack.addElement("X");    // legacy Vector method — available on Stack!

  These methods compile, run, and silently corrupt stack semantics.
  ArrayDeque.push()/pop() exposes ONLY the Deque interface — no leakage.

When to Use Stack

DO NOT USE java.util.Stack IN NEW CODE.

The Java documentation explicitly states:
  "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."

REASONS TO AVOID Stack:
  1. Global lock on every operation (inherited from Vector)
     — push/pop/peek all acquire the object monitor
     — pure overhead in single-threaded code
     — ArrayDeque has zero synchronisation cost

  2. Index-based List methods break LIFO encapsulation
     — add(0, element) inserts at the BOTTOM of the stack
     — get(i), set(i, e), remove(i) expose arbitrary access
     — code that uses Stack can accidentally violate LIFO ordering

  3. search() is 1-based and O(n) — rarely useful
     — search(obj) returns the distance from the top, starting at 1
     — this is a non-standard O(n) scan not present on Deque

  4. Vector's doubled-capacity growth wastes memory
     — ArrayDeque uses a circular array that grows by 2x
       but also trims on removal (standard Deque behaviour)

WHEN Stack IS ENCOUNTERED:
  - Legacy Java codebases predating Java 6
  - Third-party library APIs that return Stack<E>
  - Interview questions specifically about java.util.Stack

MODERN REPLACEMENTS:
  Single-threaded LIFO stack      → ArrayDeque (push/pop/peek)
  Multi-threaded LIFO stack       → ArrayDeque + ReentrantLock or Deque
  Bounded blocking stack          → ArrayBlockingQueue (LIFO not native)
  LIFO + FIFO in same structure   → ArrayDeque (fully double-ended)

How Stack Works Internally

BACKING STRUCTURE — inherited directly from Vector:
  protected Object[] elementData;    ← the resizable array
  protected int elementCount;         ← logical size (element count)
  protected int capacityIncrement;    ← 0 = doubles on resize (Vector default)

  Stack adds NO new fields — just five methods on top of Vector.

PUSH IMPLEMENTATION:
  public E push(E item) {
      addElement(item);    ← calls Vector.addElement() — adds to END of array
      return item;
  }
  Appends to the end of the array (index = elementCount).

POP IMPLEMENTATION:
  public synchronized E pop() {
      E obj = peek();
      int len = size();
      remove(len - 1);     ← Vector.remove(lastIndex) — removes last element
      return obj;
  }
  Reads and removes the last array element.

PEEK IMPLEMENTATION:
  public synchronized E peek() {
      int len = size();
      if (len == 0) throw new EmptyStackException();
      return elementAt(len - 1);    ← Vector.elementAt(lastIndex)
  }

  TOP OF STACK = last element of the underlying array
  BOTTOM       = first element (index 0)

SEARCH IMPLEMENTATION:
  public synchronized int search(Object o) {
      int i = lastIndexOf(o);     ← O(n) scan from end
      if (i >= 0) return size() - i;   ← converts to 1-based from top
      return -1;
  }
  Returns 1 for the top element, 2 for the next, -1 if absent.
  This is O(n) and not available on the Deque interface.

SYNCHRONISATION:
  All five Stack-specific methods are themselves synchronised.
  All inherited Vector methods are also synchronised.
  Every single push(), pop(), peek() acquires the object lock —
  even in single-threaded code with zero contention.

Core Operations with Examples

The Five Stack Methods

Output:
=== push() ===
push(First)  : First
push(Second) : Second
push(Third)  : Third
Stack after 3 pushes: [First, Second, Third]
(last element = top of stack)

=== peek() ===
peek()  : Third
stack unchanged: [First, Second, Third]

=== pop() ===
pop()   : Third
pop()   : Second
Stack after 2 pops: [First]

=== empty() ===
empty() : false
After final pop, empty(): true

=== EmptyStackException ===
pop() on empty stack throws EmptyStackException
peek() on empty stack throws EmptyStackException

=== search() ===
Stack (bottom→top): [10, 20, 30, 40]
search(40) : 1
search(30) : 2
search(10) : 4
search(99) : -1

Stack vs ArrayDeque — Why ArrayDeque Is Preferred

Output:
=== Performance: 2,000,000 push + pop operations ===
Stack (Vector-based): 198 ms
ArrayDeque          : 61 ms
Overhead            : ~3.2x

=== Encapsulation: List method leakage on Stack ===
Stack before: [Bottom, Middle, Top]
After add(0,...): [INJECTED_AT_BOTTOM, Bottom, Middle, Top]
peek() sees: Top

=== ArrayDeque push/pop/peek only ===
peek(): Top
pop() : Top

=== Bracket matching (ArrayDeque as stack) ===
  ({[]})                     → balanced
  ((a + b) * [c - d])        → balanced
  {x + (y * z}               → NOT balanced
  ((()))                     → balanced
  ([{)}])                    → NOT balanced

Basic Example

The classic real-life analogy for a stack is a pile of plates — you add a plate on top, and you also remove from the top. java.util.Stack provides exactly this behaviour with push(), pop(), and peek().

Output

Stack: [Plate 1, Plate 2, Plate 3]
Top plate (peek): Plate 3
Removing: Plate 3
Removing: Plate 2
Removing: Plate 1
Is stack empty now? true

How it works:

1. ›push() adds each plate to the top of the stack, so the stack fills up as [Plate 1, Plate 2, Plate 3] with Plate 3 at the top.
2. ›peek() looks at the top element (Plate 3) without removing it — the stack size stays 3.
3. ›The while loop keeps calling pop(), which removes and returns the top element each time — so plates come off in reverse order of how they were added (LIFO: Last-In, First-Out).
4. ›Once every plate has been popped, isEmpty() returns true.

Performance Considerations

search() is O(n) and rarely useful. The position-from-top value it returns is not stable between push/pop operations. It also holds the global lock for the duration of the scan. There is no equivalent in Deque — when element position is needed, that is a signal the data structure should be a different type.

The lock overhead compounds with algorithm complexity. An algorithm that calls push and pop O(n log n) times — like some sorting algorithms — pays the lock cost on each of those calls. With ArrayDeque, those same calls are bare array index operations. For stack-intensive algorithms, the difference is measurable.

Best Practices

Replace java.util.Stack with Deque<E> backed by ArrayDeque<E> in all new code. Deque<String> stack = new ArrayDeque<>() with push(), pop(), and peek() gives identical LIFO semantics with no lock overhead and no leaked List methods. Declare the variable as Deque<E> — not ArrayDeque<E> — so that swapping to a thread-safe Deque implementation requires changing only the constructor call.

Throw EmptyStackException or check with isEmpty() before popping in production code. pop() and peek() both throw EmptyStackException on an empty stack. Unlike ArrayDeque.pollFirst() which returns null for empty, ArrayDeque.pop() (which delegates to removeFirst()) throws NoSuchElementException. For safe pop patterns: if (!stack.isEmpty()) { value = stack.pop(); }. For algorithms that can tolerate null on empty: use stack.peek() which returns null on ArrayDeque when empty, unlike Stack.peek() which throws.

For expression evaluation and DFS algorithms, always use ArrayDeque. These are the two most common interview use cases for a stack. Bracket matching, postfix evaluation, iterative DFS — all of these work identically with ArrayDeque.push()/pop() as they would with Stack.push()/pop(), but without the lock cost. Interviewers who see ArrayDeque declared as Deque recognise it as the correct modern choice.

Never use Stack.search() in production code. The 1-based distance-from-top is not a stable property between push/pop operations. It is O(n) with a global lock. It exists for historical compatibility. Use contains() on the internal representation or redesign the data structure if position querying is genuinely needed.

Common Mistakes

Mistake 1 — Violating LIFO via Leaked List Methods

Mistake 2 — Popping Without Checking isEmpty()

Mistake 3 — Using Stack for Thread-Safe Concurrent Access

Mistake 4 — Iterating Stack Expecting LIFO Order

Output:
for-each: First Second Third
LIFO pop: Third Second First
ArrayDeque descending: Third Second First

Interview Questions

Q1. What is java.util.Stack in Java and what are its five methods?

java.util.Stack<E> is a LIFO (Last-In, First-Out) data structure that extends Vector<E>. It adds five methods: push(item) — adds to the top and returns the item; pop() — removes and returns the top element, throwing EmptyStackException if empty; peek() — returns the top element without removing it, throwing EmptyStackException if empty; empty() — returns true if the stack has no elements; search(object) — returns the 1-based position from the top, or -1 if not found (O(n) scan). All five methods inherit synchronisation from Vector.

Q2. Why is java.util.Stack considered a poor design?

Stack extends Vector, which causes two fundamental problems. First, every method acquires the object's global lock — push(), pop(), and peek() all hold a mutex in single-threaded code where no synchronisation is needed. Second, extending Vector means Stack inherits the entire List API: add(index, element), get(index), set(index, element), remove(index). These methods break LIFO semantics — stack.add(0, element) inserts at the bottom, not the top, and compiles without warning. Proper encapsulation of a LIFO structure should expose only push, pop, peek, and empty.

Q3. What is the recommended replacement for java.util.Stack in modern Java?

Deque<E> backed by ArrayDeque<E>. Declare as Deque<String> stack = new ArrayDeque<>() and use push(), pop(), peek(), and isEmpty(). push(e) maps to addFirst(e), pop() maps to removeFirst(), peek() maps to peekFirst(). ArrayDeque has no lock overhead, no leaked index-based methods (Deque does not extend List), and uses a compact circular array with better memory efficiency than Vector's doubling. The Java documentation explicitly recommends Deque implementations over Stack.

Q4. How does Stack implement push() and pop() internally?

push(item) calls Vector.addElement(item), which appends to the end of the backing array (position elementCount). pop() calls peek() to read the last element, then calls Vector.remove(size - 1) to remove it. peek() calls Vector.elementAt(size - 1) — reads the last array slot. The top of the Stack is always the last element of the underlying array. This means push is O(1) amortised (same as ArrayList's add()) and pop is O(1) (removes from the end, no shifting required).

Q5. What does Stack.search() return and why is it rarely used?

search(object) calls Vector.lastIndexOf(object) — a linear scan from the top of the backing array — and converts the result to a 1-based position from the top. Position 1 means the element is at the top, position 2 means second from top, and so on. It returns -1 if the element is not found. The method is rarely used because the distance from the top changes with every push and pop — it is not stable between operations. It is also O(n) with a global lock. There is no equivalent in Deque.

Q6. Describe three algorithms that use a Stack and show why ArrayDeque is the better choice for each.

Bracket matching: for each character in an expression, push opening brackets and pop when closing brackets are encountered. ArrayDeque.push()/pop() is 3x faster than Stack.push()/pop() for large expressions. Iterative DFS graph traversal: push unvisited neighbours, pop to get the next node to visit. ArrayDeque avoids lock acquisition on every node visit. Postfix expression evaluation: push operands, pop two when an operator is encountered, push the result. For large expressions (10,000+ tokens), the lock overhead on every push/pop with Stack accumulates. ArrayDeque handles all three with the same semantic code and zero lock overhead.

FAQs

Is java.util.Stack thread-safe?

Each individual method call is synchronised — no two threads can execute a push/pop/peek simultaneously. But compound operations are not atomic: a check !stack.isEmpty() followed by stack.pop() is a race condition because another thread can empty the stack between the two calls. For truly concurrent stack operations, use ArrayDeque with an external ReentrantLock around compound operations, or use java.util.concurrent.LinkedBlockingDeque for blocking semantics.

What is the difference between pop() and peek()?

pop() removes the top element from the stack and returns it — the stack's size decreases by 1. peek() returns the top element without removing it — the stack's size is unchanged. Both throw EmptyStackException when called on an empty stack. The equivalent on ArrayDeque: pop() → removeFirst() (throws on empty) or pollFirst() (returns null on empty). peek() → peekFirst() (returns null on empty) or getFirst() (throws on empty).

Can I iterate a Stack in LIFO order using for-each?

No. For-each on a Stack iterates from the bottom to the top (Vector order, not LIFO). To iterate in LIFO order: pop elements in a loop — destructive but correct. For non-destructive LIFO iteration: use stack.descendingIterator() (this is a Vector method returning an Iterator from top to bottom). ArrayDeque.descendingIterator() does the same for ArrayDeque.

Is java.util.Stack deprecated?

No — Stack has never been formally annotated with @Deprecated. The Javadoc notes that Deque should be used in preference, but the class remains fully functional for backward compatibility. IDE inspection tools flag Stack usage as a warning. Production codebases that depend on Stack continue to work.

What is the difference between ArrayDeque.push() and ArrayDeque.offer()?

ArrayDeque.push(element) inserts at the HEAD of the deque (equivalent to addFirst) — this is the stack-top position. ArrayDeque.offer(element) inserts at the TAIL (equivalent to addLast) — this is the queue-tail position. When using ArrayDeque as a stack, always use push()/pop()/peek(). When using it as a queue, use offer()/poll()/peek(). Mixing the two accidentally creates a structure that is neither a proper stack nor a proper queue.

Can java.util.Stack be used for DFS graph traversal?

Yes — any LIFO structure works for DFS. Push the start node, then while the stack is not empty: pop a node, mark it visited, push all unvisited neighbours. The most recently discovered neighbour is always explored next — depth-first. For this use case, ArrayDeque is faster and equally correct. The DFS implementation looks identical with either choice; the only difference is lock overhead per node visit.

Summary

java.util.Stack<E> implements LIFO semantics with five methods — push(), pop(), peek(), empty(), and search(). Its design flaw is inheriting from Vector, which adds global-lock synchronisation to every operation and leaks the entire List API onto a structure that should expose only stack operations. stack.add(0, element) inserting at the bottom compiles without warning and silently violates LIFO invariants.

Deque<E> backed by ArrayDeque<E> is the correct replacement: identical LIFO semantics through push()/pop()/peek(), zero lock overhead, and clean interface encapsulation — Deque does not extend List, so no index-based methods leak through. Declare as Deque<E>, instantiate with new ArrayDeque<>(), and the rest of the code is unchanged.

For interviews: know that Stack extends Vector (both are legacy), explain the two problems this causes (lock overhead, List method leakage), name ArrayDeque as the replacement, and be prepared to implement bracket matching, postfix evaluation, or DFS using Deque — the algorithm is identical, the choice of ArrayDeque signals modern Java knowledge.

What to Read Next