Stack vs Queue
A stack when the most recent item is the one you need next, which is what nesting, undo and backtracking all look like. A queue when items should be handled in arrival order, which is what fairness and level-by-level exploration look like.
The mechanical difference is one line: a stack returns what you added last, a queue returns what you added first. The useful difference is what each shape models. Nesting is a stack, because an inner bracket must close before an outer one. Distance is a queue, because everything one step away must be handled before anything two steps away.
Side by side
| Dimension | Stack | Queue |
|---|---|---|
| Order | Last in, first out | First in, first out |
| Operations | push, pop, peek | offer, poll, peek |
| Graph traversal | Depth-first | Breadth-first |
| Models | Nesting, recursion, undo | Arrival order, distance, scheduling |
| Java type | ArrayDeque, not the legacy Stack class | ArrayDeque or LinkedList |
| Recursion link | The call stack is one | No equivalent, must be explicit |
When to pick each
Stack
- Matching or nesting: brackets, expression parsing, decoding nested strings.
- Monotonic problems, where you hold indices whose answer is still unknown until something larger or smaller arrives.
- Converting a recursive algorithm to an iterative one, since the stack is what the recursion was using implicitly.
Queue
- Breadth-first search and anything measuring distance in steps.
- Level-by-level processing of a tree.
- Producer and consumer handoffs, where arrival order is the fairness guarantee.
Using java.util.Stack. It extends Vector, so every operation is synchronised and slower, and it iterates bottom to top, which is the opposite of pop order and has surprised a great many people mid-debug. ArrayDeque is the current recommendation for both stacks and queues, and the Javadoc for Stack says so itself.
Questions people ask
Can you build one from the other?
Yes, and it is a common interview question. A queue from two stacks pours one into the other to reverse the order, and only pours when the output stack is empty, which makes it amortised O(1) per operation.
Why does swapping the structure turn DFS into BFS?
Because the traversal code is otherwise identical. Both pull a node, record it, and add its neighbours. A stack hands back the most recently added neighbour, taking you deeper; a queue hands back the oldest, keeping you at the current distance.
Which should I use for an undo feature?
A stack, since undo always applies to the most recent action. Redo is a second stack that fills as you undo and is cleared as soon as a new action is performed.