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.
Related lessons & next topics
Keep going — these pair well with Stacks, queues, and ArrayDeque.
- § 6.01 · Data Structures in JavaArrays and ArrayList — the workhorses
Fixed-size arrays vs dynamic ArrayList. Memory layout, amortized O(1) append, and when each one shines.
Beginner · 22 min - § 6.02 · Data Structures in JavaLinkedList and the Deque interface
Doubly-linked nodes, O(1) insert at either end, and why LinkedList is almost never the right choice.
Beginner · 20 min - § 6.04 · Data Structures in JavaHashMap, equals, and hashCode
How hashing works, why you must override equals and hashCode together, and the load factor that keeps lookups O(1).
Intermediate · 28 min - § 6.05 · Data Structures in JavaTreeMap, TreeSet, and ordered structures
Red-black trees under the hood. O(log n) sorted access, range queries, and floor/ceiling lookups.
Intermediate · 26 min