Stacks, queues, and ArrayDeque
LIFO, FIFO, and why java.util.Stack is a historical mistake you should avoid.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Two disciplines, one class
A stack is Last-In-First-Out — the last thing you pushed is the next thing you pop. A queue is First-In-First-Out — the first thing you offered is the first thing you poll. ArrayDeque implements both. Which behavior you get depends on which methods you call: push/pop for stack, offer/poll for queue.
ArrayDeque under the hood
ArrayDeque is a circular buffer — a resizable array with head and tail indices that wrap around. Adds and removes at either end are O(1) amortized, iteration is cache-friendly, and there's no per-element allocation. It has no capacity limit (it grows) and no synchronization (it's fast).
Why not java.util.Stack
java.util.Stack from Java 1.0 extends Vector, which means every operation is synchronized — a performance hit — and the class inherits Vector's awkward API. Its iteration order is bottom-to-top, the opposite of what you probably want. The Javadoc itself now recommends ArrayDeque.
Balanced-parentheses example
A classic stack application: scan a string, push every opener, pop and match every closer. If the stack is empty when you need to pop, or non-empty at the end, the string is unbalanced.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Queues in the JDK
For an ordinary FIFO queue, ArrayDeque is the answer. For a bounded, thread-safe queue, use ArrayBlockingQueue. For a priority queue (smallest first), use PriorityQueue. For a producer-consumer pipeline across threads, LinkedBlockingQueue and ConcurrentLinkedQueue cover most cases.