How a Stack works in Java?

This next one in the series about core data structures in Java (yes, there’s been a tendency in my recent post, so it’s a series I guess) is about a classic data structure implementation. java.util.Stack is the de facto LIFO (last-in, first-out) implementation and the goto collection when you’re solving DSA problems on Leetcode and similar sites using java. This was my preferred collection when I needed a stack but with time I found out there are better choices for which I’ll argument myself here and in my future post about ArrayDeque . Still, when solving Leetcode problems that need a LIFO structure, using a Stack may suffice, but in real-world environments it’s not the best choice.

java.util.Stack is a class from the earlier versions of java that implements a LIFO data structure. Historically, he’s extending java.util.Vector which means:

• all operations are synchronized, meaning they use a single global lock in concurrent workflows. This may bring lock contention allowing access to your Stack only to a single thread at a time.

Stack is basically just a wrapper around java.util.Vector . This roughly means that its operations add and remove elements at the end of a Vector. The “top of the stack” in this case the last element of the Vector.

public class Stack<E> extends Vector<E> {
    public E push(E item) {
        addElement(item);
        return item;
    }

    public synchronized E pop() {
        int len = size();
        E obj = peek();
        removeElementAt(len - 1);
        return obj;
    }

    public synchronized E peek() {
        int len = size();
        return elementAt(len - 1);
    }
}

Here are the operations Stack supports:

• E push(E item) — adds an element at the end of the Vector. It could trigger a resize. The time complexity is amortized O(1) .
• E pop() — removes the last element from the Vector and returns it. Time complexity is O(1) but has synchronization overhead
• E peek() — returns the element at the top of the stack but doesn’t remove it from the underlying Vector
• int search(Object o) — returns the 1-based position of an element’s location on the stack. The topmost element has a position of 1. It returns the distance from the top of the stack to the first occurence of the object.

How a stack works

In which situations is appropriate to use a stack?

• DFS traversal of graphs (trees, matrices etc.)
• string parsing and tokenization related problems (check Evaluate Reverse Polish Notation from Leetcode)
• Undo functionality — for example, in text editors or the back buttons of web browsers
• backtracking
• recursion — problems that can be solved using a recursion can use a stack, as well

In the case of Java applications using java.util.Stack may bring overhead due to thread contention and its global lock. After all, it’s a wrapper around a Vector — here’s more information why this brings over head.

Get Tsvetomir Denchev’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

You might prefer using ArrayDeque in a non-thread safe environment and ConcurrentLinkedQueue in a multi-threaded logic.

Deque<E> stack = new ArrayDeque<>();
stack.push(e);
stack.pop();
stack.peek();

Deque<E> stack = new ConcurrentLinkedDeque<>();

java.util.Stackis a legacy LIFO implementation built on top of Vector. While its core operations are constant time, global synchronization and outdated design make it inferior to modern alternatives like ArrayDeque for most real-world use cases.