Stacks, queues, deques and monotone structures

1. Stacks and the call stack analogy

   DSA Handbook - Foundations and linear patterns

   The LIFO contract; The call stack is the same data structure; LC 20 the deferred-match validator; What it actually costs (push amortized \(O(1)\), LC 20 \(O(n)\) time and space)

   Done
2. Queues, deques, and circular buffers

   DSA Handbook - Foundations and linear patterns

   The FIFO contract; The deque adds the back end; The circular buffer fixes the capacity; Why the patterns chapters teach the rest (LC 232 amortized queue); What it actually costs (list.pop(0) \(O(n)\) against deque \(O(1)\))

   Done
3. Monotonic stack

   DSA Handbook - Foundations and linear patterns

   The pattern (pop-while-violating then push); Why the work stays linear (\(2n\) aggregate); Worked example LC 739 on [73, 74, 75, 71, 69, 72, 76, 73]; Largest rectangle: the sentinel-pop trick; Two pitfalls (indices, not values)

   Done
4. Monotonic deque

   DSA Handbook - Foundations and linear patterns

   The invariant (decreasing indices, front is the \(\operatorname{argmax}\)); The pattern (drop-front, pop-tail, push, emit); Worked example LC 239 on [1, 3, -1, -3, 5, 3, 6, 7] with \(k = 3\); What it actually costs

   Depth · The cost table lists the max-heap with lazy deletion as \(O(n \log k)\) beside \(O(n)\) space. The space column is right: stale entries stay buried, so the heap can hold \(n\) entries and its worst case is \(O(n \log n)\).

   Done

Focus on

• Each index enters and leaves once: at most \(2n\) stack ops and at most \(2n\) deque ops. That is the whole linearity proof.
• Monotone structures store indices: values cannot report expiry.
• Deque order per slide: drop the expired front, pop smaller backs, push, emit the front.
• Python list is the stack and collections.deque is the queue. Swapped roles cost \(O(n)\) per op at the wrong end.

Reproduce closed-book

Traps

• Storing values instead of indices: equal values from different positions become indistinguishable and expiry breaks.
• Emitting before pushing or popping the wrong end: the order is drop-front, pop-back, push, emit.
• list.pop(0) as a queue (about 45x slower than deque per drain at \(n = 20000\) on the stated CPU and Python 3.13.14), and recursion past the default limit of 1000 frames, which raises RecursionError instead of growing.

Practice

Self-test

1. Prove the monotone stack is \(O(n)\).

   Show answer Got it Missed

2. Argue the two-stack queue is amortized \(O(1)\).

   Show answer Got it Missed

3. Why must the deque hold indices?

   Show answer Got it Missed

4. What does the heap alternative cost on sliding maximum, and when does the deque win?

   Show answer Got it Missed

Leads to

• 1.7 Two pointers and sliding windows Sliding windows reuse the deque discipline with a different trigger.
• 2.6 Heaps and priority queues Heaps are the \(O(n \log n)\) lazy-deletion alternative the deque beats on windows.

Comes after

• 1.2 Aggregate, accounting and potential amortized analysisThe two-stack queue is the next amortized argument.
• 1.4 Arrays, strings, locality and linked structuresStacks and queues pick their backing layout from this unit.
• 1.5 Hash tables: collisions, load factor, resizing and tombstonesThe LC 380 trick pairs a hash map with a dynamic array.
• 1.7 Two pointers and sliding windowsTrapping Rain Water meets both windows and monotone stacks.

Resources for this unit

• DSA Handbook - Foundations and linear patterns
  Handbook Academyprimarycourse
  Study Part 0, Part 1, Part 3 and Part 4 in order, plus the Part 5 Linked-list fundamentals chapter. Use the routing-rule pages for arrays versus lists, map choice, stack versus queue, two pointers, sliding windows and prefix methods before seeing solved code.