Card 09/ 09
Recap: Stacks and Queues
Newest first or oldest first, a deque for queues, and a ring buffer for a fixed size.
Stacks and Queues comes down to the seven ideas below, each listed with the card that covers it.
| The idea | Where |
|---|---|
| A stack hands back the newest item and a queue the oldest, and neither reaches the middle | Stacks and Queues: Last In First Out, First In First Out |
| Write a stack from its top and a queue from its front, so the next item to leave comes first | Trace a Sequence of Stack and Queue Operations |
| "Most recent unfinished" is the cue for a stack | Stack Example: Matching Brackets in an Expression |
| "First come, first served" is the cue for a queue, and a stack can starve the earliest item | Queue Example: Serving Print Jobs in Arrival Order |
| A list, an ArrayDeque or a TypeScript array is the stack; a deque, an ArrayDeque or a head index is the queue | Stack and Queue in Python, Java and TypeScript |
| Removing from the front of an array moves every element behind it, so a queue of n becomes O(n²) | Dequeuing From the Front of an Array |
| A ring buffer wraps head and tail with (index + 1) % capacity, and a count tells full from empty | Ring Buffers: A Queue in a Fixed Array |
The operations reduce to where each structure adds and removes, and what each costs when built on the storage that suits it; amortised means averaged over many pushes.
| Structure | Adds at | Removes from | Cost of each operation |
|---|---|---|---|
| Stack on a dynamic array | The end | The end | O(1), push O(1) amortised |
| Queue on a deque or a head index | The back | The front | O(1) |
| Queue on a ring buffer | The tail slot | The head slot | O(1), until it is full |
| Queue that removes at index 0 of an array | The back | The front, shifting the rest | Dequeue O(n) |
Together they let you choose the structure from the order a problem needs, trace it to its final state, and build it so that no operation moves an element it does not have to.
← → move through sections and cards