Stack vs Queue in Java — LIFO, FIFO, and Why to Use ArrayDeque Instead

Stack is LIFO — last-in, first-out. Queue is FIFO — first-in, first-out. Deque supports both (double-ended queue).

Don't use `java.util.Stack`

• Legacy (Java 1.0)
• All methods synchronized — slow in single-threaded code
• Extends Vector — bloated API including get(int), random-access, set(int, e)
• Javadoc itself says 'use Deque instead'
• Same for Vector and Hashtable — never use in new code

Use ArrayDeque — modern replacement

As a stack (LIFO)

• push(e) — add to front
• pop() — remove from front
• peek() — inspect front
• All O(1) amortized

As a queue (FIFO)

• offer(e) — add to back
• poll() — remove from front
• peek() — inspect front
• All O(1) amortized

Why ArrayDeque over LinkedList

• Array-backed, cache-friendly
• No pointer-chasing
• Lower memory overhead per element
• Circular buffer internally
• LinkedList works as deque but is strictly worse for stack/queue use

Two method families — error handling

Throwing

• add(e), remove(), element()
• Throw IllegalStateException / NoSuchElementException
• Use when empty/full is exceptional

Special-value

• offer(e), poll(), peek()
• Return false / null on failure
• Use for normal flow
• BFS: while ((Node n = q.poll()) != null) {...} — loop exits naturally

Deque convention

• push(e) = addFirst(e)
• pop() = removeFirst()
• peek() = peekFirst()
• offer(e) = offerLast(e)
• poll() = pollFirst()
• So stack ops are at the front; queue offer adds to back, poll removes from front

Use cases

Stack (LIFO)

• Undo/redo (two stacks)
• Function call evaluation
• DFS (or recursion, which uses call stack)
• Parenthesis matching
• Expression evaluation (postfix, infix)

Queue (FIFO)

• Task scheduling
• BFS
• Buffer / pipeline
• Producer-consumer

PriorityQueue

• Smallest element first (min-heap)
• Comparator.reverseOrder() for max-heap
• offer/poll: O(log n); peek: O(1)
• contains: O(n) — common trap
• Not thread-safe — use PriorityBlockingQueue

Concurrent alternatives

ConcurrentLinkedQueue

• Lock-free, CAS-based
• Unbounded FIFO
• High-throughput

ConcurrentLinkedDeque

• Same design, both ends

LinkedBlockingQueue

• Optionally bounded
• Blocks on full/empty via put/take
• Classic producer-consumer

ArrayBlockingQueue

• Bounded fixed-size
• Array-backed
• Good for back-pressure

SynchronousQueue

• Zero-capacity hand-off
• Each put waits for a take
• Used in cached thread pool

PriorityBlockingQueue

• Concurrent priority queue

DelayQueue

• Elements with delay; poll returns only expired
• For scheduled tasks

Decision matrix

• LIFO stack → Deque stack = new ArrayDeque<>(), use push/pop/peek
• FIFO queue → Queue q = new ArrayDeque<>(), use offer/poll/peek
• Priority smallest first → PriorityQueue<> min-heap
• Priority largest first → PriorityQueue<>(Comparator.reverseOrder())
• Concurrent FIFO → ConcurrentLinkedQueue
• Concurrent deque → ConcurrentLinkedDeque
• Bounded producer-consumer → LinkedBlockingQueue or ArrayBlockingQueue
• Hand-off → SynchronousQueue
• Delayed tasks → DelayQueue
• Never → Stack, Vector, Hashtable

Common traps

1. Using `Stack` class

• Legacy, synchronized, API bloat
• Use ArrayDeque

2. Using LinkedList as stack/queue

• Works but suboptimal
• ArrayDeque is faster (cache locality)

3. `PriorityQueue.contains` is O(n)

• Not O(log n)
• No hash index

4. Mixing offer/poll with add/remove

• Different error behavior (return value vs throw)
• Pick one style per context

5. Not knowing push/pop are at the front in Deque

• Counterintuitive but standard
• push = addFirst, not addLast

Recommendation: For LIFO stacks, use `Deque stack = new ArrayDeque<>()` with push/pop/peek. For FIFO queues, use `Queue q = new ArrayDeque<>()` with offer/poll/peek. Never use the legacy `Stack` class — it's synchronized, extends Vector, and exposes dangerous random-access methods; the Javadoc itself recommends Deque. Never use `LinkedList` as a stack or queue — `ArrayDeque` has far better cache locality (contiguous memory, no pointer chasing) and lower memory overhead. Prefer `offer`/`poll`/`peek` (return special value on fail) over add/remove/element (throw) for normal flow; the special-value variants compose better with loops. For priority (smallest-first or custom order), use `PriorityQueue` — but remember `contains` is O(n), not O(log n). For concurrent scenarios: `ConcurrentLinkedQueue` for lock-free FIFO, `LinkedBlockingQueue` for bounded producer-consumer, `ConcurrentLinkedDeque` for bi-directional lock-free, `SynchronousQueue` for direct hand-off. Know the Deque convention: push(e) = addFirst(e), pop() = removeFirst() — stack ops operate at the front. Use BFS with Queue and DFS with Stack (or recursion) — the standard algorithmic pairings. The mental model: Deque is the universal tool — it's both a stack and a queue; ArrayDeque is the fast default; specialized implementations only when concurrency, priority, blocking, or delay semantics are needed.