168: DSA - Stacks, Queues, and Linked Lists
Learning outcomes
- select a stack or queue from required access order;
- manipulate linked-list pointers safely;
- use monotonic stacks for next-greater problems.
Practice
Implement a queue with two stacks, reverse a linked list, detect a cycle, and solve daily temperatures with a monotonic stack. Draw pointer changes before running code and test one-node and empty structures.
Lesson and worked examples
For a two-stack queue, push onto in; on dequeue, move items to out only when out is empty. Each item crosses stacks at most once per direction, so m operations cost O(m) total, or amortized O(1) each. For reversal, start previous = null; save next, point current.next backward, then advance both pointers. The list 1 -> 2 -> 3 becomes 3 -> 2 -> 1 without losing 2.
For cycle detection, advance slow one edge and fast two; equality proves a cycle, while fast reaching null proves none. For daily temperatures, keep decreasing temperatures' indices. When today is warmer, pop each resolved index and compute the distance. Equal temperatures should remain or be popped consistently with the stated “strictly warmer” contract.
Tests and rubric
Test empty and one-node structures, queue FIFO order across transfers, repeated transfers, a two-node cycle, a self-cycle, a broken tail, duplicate temperatures, strictly increasing/decreasing temperatures, and equal temperatures. Score 2 points each for pointer safety, amortized argument, monotonic-stack invariant, O(1) list space, and focused tests. Include a diagram or trace for one pointer mutation.
Checkpoint
Explain why a queue built with two stacks is amortized O(1), and which pointer must change first when reversing a list.
Pointer safety
When reversing a list, save current.next before replacing it. Then point current.next to previous, advance previous, and advance current. Losing the saved successor disconnects the remainder of the list. Cycle detection uses two speeds because a fast pointer eventually laps a slow pointer inside a cycle.
Review questions
When is an array better than a linked list? What does “amortized” hide in the two-stack queue? Which monotonic property makes the daily-temperatures stack correct?