Unit 03
Stacks & Queues
Both restrict how you can add and remove elements, and that restriction is the whole point — it gives you a predictable order of access for free.
// a stack reverses arrival order, a queue preserves it
What they are
A stack only lets you add or remove from one end — the "top" — so the last thing you added is the first thing you remove (Last In, First Out). A queue lets you add at one end (the rear) and remove from the other (the front), so the first thing added is the first thing removed (First In, First Out).
Why they're useful
- Stacks model "undo" history, function call tracking (the call stack), and matching brackets or parentheses in an expression.
- Queues model task scheduling, handling requests in the order they arrive, and breadth-first traversal of trees and graphs.
Where they struggle
- Both deliberately restrict access — you can't reach into the middle without breaking the abstraction, so they're the wrong tool when you need arbitrary access.
- A naive queue built on an array can be slow to dequeue unless implemented carefully (e.g. with a circular buffer or a linked list).
Time complexity
| Operation | Stack | Queue |
|---|---|---|
| Insert (push / enqueue) | O(1) | O(1) |
| Remove (pop / dequeue) | O(1) | O(1) |
| Access middle element | Not supported | Not supported |