Stacks & Queues
Beginner · 12 min read · Data Structures Basics, Linear Structures
Last-in-first-out and first-in-first-out, deques, and how both are built on arrays.
Stacks and queues are arrays or lists with a rule about which element leaves next. That restriction is the point: it makes the right element available in O(1) without searching.
Picture it
How they work
Stack on an array. The top is the end of the array. push writes at size and increments it; pop decrements size and returns that element. Nothing shifts, so both are O(1):
Types
A priority queue is called a queue, but it isn't FIFO. It's a heap, with O(log n) operations.
Operations and their cost
(O(1) for array-backed versions is amortised: they occasionally grow.)
In Java
Recognising stack and queue problems
Patterns that use stacks and queues
Interview questions
- How does an array-based queue avoid shifting elements on every poll?
- Why does recursion relate to stacks?
Further reading
Key takeaways
- Stack = LIFO (push, pop and peek at the top); queue = FIFO (offer at the back, poll at the front); all O(1).
- On arrays: a stack uses the end of the array; a queue uses a circular buffer with a wrapping head.
- Use ArrayDeque for both in Java; avoid Stack; a priority queue is a heap, O(log n).
- Stack signals: most recent, matching, nesting, undo. Queue signals: arrival order, levels, fewest steps.