Java Stacks and Queues

A stack and a queue are two of the most fundamental data structures in computer science, and Java ships with several ready-made implementations of both. A stack is a Last-In-First-Out (LIFO) structure — the last item you add is the first one you remove — while a queue is First-In-First-Out (FIFO) — items come out in the same order they went in. You’ll reach for stacks when building undo history, evaluating expressions, or rewriting recursion iteratively, and for queues when scheduling tasks, doing breadth-first search, or modeling any producer/consumer pipeline. This lesson covers Java’s stack and queue types in depth: the classic java.util.Stack class, the modern Queue and Deque interfaces, how each is implemented internally, and the mistakes that trip up nearly every beginner.

Overview: How Stacks and Queues Work

Stack: Last-In-First-Out (LIFO)

A stack is built around one rule: whatever you insert last is removed first. Picture a stack of plates — you can only take from the top, and you can only add to the top. The two operations that define this behavior are traditionally called push (add to the top) and pop (remove and return the top item), with peek letting you look at the top without removing it. Any correct stack implementation just needs constant-time access to one end of the underlying storage; it doesn’t matter whether that storage is an array or a linked list, as long as insert and remove at that one end are O(1).

Queue: First-In-First-Out (FIFO)

A queue flips the access pattern: the first item inserted is the first one removed, exactly like a line at a checkout counter. Two ends matter here — new items join at the back (enqueue) and items leave from the front (dequeue). In modern Java the vocabulary for this is offer (add to the back) and poll (remove from the front), with peek again inspecting the front without removing it.

Choosing a Java implementation

Java gives you several concrete types for these ideas, and picking the right one matters:

• java.util.Stack is the original stack class from Java 1.0. It extends Vector, so every method is synchronized (thread-safe, but with locking overhead you rarely need in single-threaded code) and it’s backed by a resizable array. It still works correctly, but the JDK’s own documentation recommends avoiding it in new code.
• java.util.Queue is an interface, not a class — you never write new Queue<>(). It’s implemented by LinkedList (a doubly linked list of nodes) and by PriorityQueue (a binary heap that dequeues in priority order rather than insertion order).
• java.util.Deque (double-ended queue, pronounced "deck") supports insertion and removal at both ends. Its main implementation, ArrayDeque, is backed by a resizable circular array. It is the modern, recommended way to get either stack or queue behavior in Java, since it has no synchronization overhead and is generally faster than both Stack and LinkedList.

Because a Deque can add and remove at both ends in O(1), it naturally supports stack semantics (push/pop map to addFirst/removeFirst) and queue semantics (offer/poll map to addLast/removeFirst) at the same time. That’s why modern Java code almost always reaches for ArrayDeque instead of the legacy Stack class, even when the goal is purely LIFO behavior.

Syntax

Stack<Type> stack = new Stack<>();       // legacy LIFO
Queue<Type> queue = new LinkedList<>();  // FIFO via an interface
Deque<Type> deque = new ArrayDeque<>();  // modern, double-ended

Type	Method	Effect
Stack	push(e)	Adds e to the top
Stack	pop()	Removes and returns the top item; throws EmptyStackException if empty
Stack	peek()	Returns the top item without removing it; throws if empty
Stack	search(e)	1-based distance of e from the top, or -1 if absent
Queue	offer(e) / add(e)	Adds e to the back; offer returns false instead of throwing when the queue is full-capacity (rare for unbounded queues)
Queue	poll() / remove()	Removes and returns the front item; poll returns null instead of throwing on empty, remove throws
Queue	peek() / element()	Returns the front item without removing it; peek returns null, element throws
Deque (as stack)	push(e) / pop()	Alias for addFirst(e) / removeFirst()
Deque (as queue)	offer(e) / poll()	Alias for offerLast(e) / pollFirst()

Notice the pattern: the older methods (add, remove, element) throw exceptions on failure, while the newer Queue/Deque methods (offer, poll, peek) return a special value (false or null) instead. Prefer the offer/poll/peek family unless you specifically want a thrown exception to signal a bug.

Examples

Example 1: Basic stack operations

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped: " + stack.pop());
        System.out.println("Stack after pop: " + stack);
        System.out.println("Is empty? " + stack.isEmpty());
        System.out.println("Search for 10: " + stack.search(10));
    }
}

Output:

Top element: 30
Popped: 30
Stack after pop: [10, 20]
Is empty? false
Search for 10: 2

Three integers are pushed, so the stack holds [10, 20, 30] with 30 on top. peek() reports 30 without removing it, then pop() removes and returns 30, leaving [10, 20]. Finally, search(10) counts positions from the top: 20 is 1 away, 10 is 2 away, so it returns 2.

Example 2: Basic queue operations with LinkedList

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("Alice");
        queue.offer("Bob");
        queue.offer("Charlie");
        System.out.println("Front of queue: " + queue.peek());
        System.out.println("Dequeued: " + queue.poll());
        System.out.println("Queue after poll: " + queue);
        System.out.println("Is empty? " + queue.isEmpty());
    }
}

Output:

Front of queue: Alice
Dequeued: Alice
Queue after poll: [Bob, Charlie]
Is empty? false

LinkedList implements Queue, so offer appends to the back and poll removes from the front. Alice was enqueued first, so she’s both the item peek() reports and the one poll() removes — classic FIFO order.

Example 3: A realistic use — balanced brackets checker

Stacks are the natural tool for matching nested pairs, such as validating that brackets in an expression are balanced. Each opening bracket is pushed; each closing bracket must match whatever is currently on top.

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static boolean isBalanced(String expr) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : expr.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char open = stack.pop();
                if ((c == ')' && open != '(') ||
                    (c == ']' && open != '[') ||
                    (c == '}' && open != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String[] tests = { "{[()]}", "([)]", "((a+b)*(c-d))" };
        for (String test : tests) {
            System.out.println(test + " -> " + isBalanced(test));
        }
    }
}

Output:

{[()]} -> true
([)] -> false
((a+b)*(c-d)) -> true

Here Deque is used purely as a stack via push/pop, which is exactly the modern replacement for java.util.Stack. The first test nests all three bracket types correctly. The second test fails because ) arrives while [ is on top — a mismatch. The third test proves the algorithm ignores non-bracket characters and still validates correctly, which is how a real expression parser would use this technique.

How It Works Step by Step (Under the Hood)

ArrayDeque stores elements in a plain array along with two indices, head and tail, that track the logical front and back. Pushing to the front decrements head (wrapping around to the end of the array like a clock face — this is the "circular" part), and adding to the back increments tail, both modulo the array length. Because there’s no shifting of existing elements, every add/remove at either end is O(1). When the array fills up, ArrayDeque allocates a new array (typically double the size), copies the existing elements into contiguous order, and resets the indices — the same doubling strategy ArrayList uses for growth.

LinkedList (used as a Queue) stores each element in its own node object holding references to the previous and next node. Adding to the back just allocates a new node and relinks two pointers; removing from the front unlinks the head node and lets the garbage collector reclaim it. This means no resizing ever happens, but every element costs extra memory for its node object and two pointers, and traversal has worse cache locality than a contiguous array.

java.util.Stack, because it extends Vector, is backed by an array just like ArrayDeque, but every single method call (push, pop, peek, size…) is wrapped in a synchronized block. In a single-threaded program that lock is pure overhead: it’s acquired and released millions of times for no benefit, which is the main reason the JDK team now steers developers toward ArrayDeque for stack use.

Common Mistakes

Mistake 1: Popping or peeking without checking for empty

Calling pop() or peek() on an empty Stack throws EmptyStackException at runtime — a very common bug when a loop drains a stack one element too many times.

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        try {
            System.out.println("Popping: " + stack.pop());
        } catch (Exception e) {
            System.out.println("Error: " + e);
        }
    }
}

Output:

Error: java.util.EmptyStackException

The fix is to always check isEmpty() before popping or peeking (or, if you’re using a Deque/Queue, prefer the null-returning poll()/peek() methods over the exception-throwing ones):

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        if (!stack.isEmpty()) {
            System.out.println("Popping: " + stack.pop());
        } else {
            System.out.println("Stack is empty, nothing to pop.");
        }
    }
}

Output:

Stack is empty, nothing to pop.

Mistake 2: Using ArrayList as a queue

An ArrayList compiles fine as a stand-in for a queue, and remove(0) does remove the front element — but it’s an anti-pattern. Removing index 0 forces every remaining element to shift left by one, making each dequeue an O(n) operation instead of O(1).

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> queue = new ArrayList<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        int front = queue.remove(0);
        System.out.println("Removed: " + front);
        System.out.println("Queue: " + queue);
    }
}

Output:

Removed: 1
Queue: [2, 3]

The result looks identical to a real queue, which is exactly why this mistake is easy to miss in small tests — it only becomes a performance problem once the queue grows large. Use a genuine Queue/Deque implementation instead, which removes from the front in O(1):

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        int front = queue.poll();
        System.out.println("Removed: " + front);
        System.out.println("Queue: " + queue);
    }
}

Output:

Removed: 1
Queue: [2, 3]

Best Practices

• Prefer ArrayDeque over java.util.Stack for LIFO behavior — it’s faster and has no unnecessary synchronization.
• Prefer ArrayDeque or LinkedList over ArrayList for FIFO behavior — never call remove(0) on an ArrayList in a loop.
• Use the offer/poll/peek family when you want a null/false return on failure, and the add/remove/element family only when a thrown exception is genuinely the behavior you want.
• Always check isEmpty() (or use the non-throwing methods) before removing from a stack or queue whose contents you’re not certain about.
• Reach for PriorityQueue when items need to come out in priority order rather than insertion order — it’s still a Queue, but backed by a binary heap.
• For multithreaded producer/consumer scenarios, use a concurrent type like ConcurrentLinkedQueue or a BlockingQueue implementation instead of manually synchronizing a plain Queue.
• When declaring variables, code to the interface (Queue<T> or Deque<T>) rather than the concrete class, so you can swap implementations later without changing calling code.

Practice Exercises

1. Write a method reverse(String s) that reverses a string by pushing each character onto a Deque<Character> and then popping them back off into a new string. Test it with "hello" and confirm the output is "olleh".
2. Simulate a simple print queue: enqueue five job names (strings) into a Queue<String>, then dequeue and print each one with its position number (job 1, job 2, …) until the queue is empty.
3. Extend the balanced-brackets checker from Example 3 so it also reports the index of the first mismatched closing bracket when the expression is invalid, instead of just returning false.

Summary

• A stack is LIFO (last in, first out); a queue is FIFO (first in, first out).
• java.util.Stack is legacy, synchronized, and array-backed via Vector — usable, but no longer recommended.
• Queue and Deque are interfaces; common implementations are LinkedList (linked nodes), ArrayDeque (circular array), and PriorityQueue (binary heap).
• ArrayDeque is the modern, fast, non-synchronized choice for both stack and queue behavior.
• Exception-throwing methods (pop, add, remove, element) fail loudly on empty/full; the offer/poll/peek family fails quietly by returning false/null.
• Never use ArrayList.remove(0) as a queue dequeue — it’s O(n) per call.
• Always guard pop()/peek() with an isEmpty() check, or use the null-returning alternatives, to avoid runtime exceptions.