Day 25/90: Queue & Stack -- Why I Stopped Using java.util.Stack
90 Day Java Challenge: Zero to Production
I inherited a service that ran a depth-first walk over a dependency graph, built around a java.util.Stack. It worked. But profiling a slow request showed time spent inside synchronized methods -- on a path that only ever ran on one thread. The stack was paying for locks nothing needed.
The inheritance that costs you
java.util.Stack extends Vector. Every Vector method is synchronized, so push, pop, and peek each grab a monitor lock on every call. Single-threaded, that lock is never contended -- it is pure overhead.
The worse part is the inherited API. Because a Stack is a Vector is a List, every List method is public on your "stack":
import java.util.Stack; Stack<String> stack = new Stack<>(); stack.push("a"); stack.push("b"); stack.add(0, "bottom"); // insert at the BOTTOM of a stack String mid = stack.get(0); // random access into a stack stack.remove("a"); // delete a non-top element A stack should make exactly one promise -- last in, first out, touched only at the top. java.util.Stack hands callers a dozen ways to break it. The type meant to enforce the discipline is the type that violates it.
ArrayDeque: one class, both shapes
The Java docs recommend ArrayDeque over Stack for a stack, and over LinkedList for a queue. It is array-backed, unsynchronized, and does not extend List. The Deque interface gives you both shapes from one object.
As a stack, use push / pop / peek -- all operating on the front:
import java.util.ArrayDeque; import java.util.Deque; Deque<String> stack = new ArrayDeque<>(); stack.push("first"); stack.push("second"); stack.push("third"); System.out.println(stack.pop()); // third (last in, first out) System.out.println(stack.peek()); // second (top, not removed) As a queue, use offer / poll / peek -- add at the back, remove from the front:
import java.util.ArrayDeque; import java.util.Deque; Deque<String> queue = new ArrayDeque<>(); queue.offer("first"); queue.offer("second"); queue.offer("third"); System.out.println(queue.poll()); // first (first in, first out) System.out.println(queue.peek()); // second (head, not removed) Same class. The only difference is which methods you call. If push and offer feel vague, the explicit names addFirst / pollFirst and addLast / pollFirst say which end you mean.
The null contract: signal vs throw
Deque exposes two parallel method families that differ in how they report failure:
import java.util.ArrayDeque; import java.util.Deque; Deque<String> q = new ArrayDeque<>(); System.out.println(q.poll()); // null -- empty, no exception System.out.println(q.peek()); // null -- empty, no exception q.remove(); // throws NoSuchElementException offer / poll / peek return null or false when the operation cannot proceed. add / remove / element throw. Use the returning forms when empty is an expected state your loop handles; use the throwing forms when empty means a bug you want loud. And note: ArrayDeque rejects null elements outright (it throws NullPointerException on insert), precisely so a null from poll always means "empty."
ArrayDeque vs LinkedList, and PriorityQueue
Both implement Deque, so why prefer ArrayDeque? Memory layout. ArrayDeque keeps elements in a contiguous, growable circular array -- cache-friendly, zero per-element allocation. LinkedList allocates a two-pointer node per element, scattered across the heap, paying a cache miss on every link traversal. For ordinary stack and queue work, ArrayDeque is faster and lighter. Reach for LinkedList only when you need List indexing alongside deque behavior.
When you want elements out in priority order instead of LIFO or FIFO, use PriorityQueue -- a heap that polls smallest-first:
import java.util.PriorityQueue; PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.offer(5); pq.offer(1); pq.offer(3); System.out.println(pq.poll()); // 1 System.out.println(pq.poll()); // 3 System.out.println(pq.poll()); // 5 Only the polling is ordered -- iterating a PriorityQueue gives you heap order, not sorted order.
The takeaway
java.util.Stack is a class to retire. It carries Vector's locks and Vector's API into a place that wanted neither. ArrayDeque covers both stack and queue cleanly, beats LinkedList on speed and memory, and lets you choose your failure mode. Yesterday was maps and their ordering contracts; today the container's order is the whole point -- so picking the structure is just picking the order you actually want.
