Skip to content
AITroveRead. Build. Understand.
Reading list

Stacks and Queues

Ordering contracts for undo, buffering, and scheduling.

Ordering contracts for undo, buffering, and scheduling. Work through the operation contract, runnable case, and cost before selecting the structure for a real workload.

Lessons

Practice and next steps

Monotonic deques: maintain a sliding minimum in linear time

Bounded thread queues: separate FIFO removal from task completion

Bounded queues: close, wake waiters, and drain accepted work

CAS queue protocol: link, help, and reclaim safely

Hashed timing wheels: bucket incident expiries by tick

Two-stack window aggregation: keep FIFO order under a monoid

Persistent two-list queues: fork FIFO dispatch history

Curriculum

Ordering contracts for undo, buffering, and scheduling.

  1. 1Stacks: last-in-first-out for reversible edits
  2. 2Queues: preserve arrival order without front shifts
  3. 3Ring buffers: make capacity and overwrite rules explicit
  4. 4Monotonic deques: maintain a sliding minimum in linear time
  5. 5Bounded thread queues: separate FIFO removal from task completion
  6. 6Bounded queues: close, wake waiters, and drain accepted work
  7. 7CAS queue protocol: link, help, and reclaim safely
  8. 8Hashed timing wheels: bucket incident expiries by tick
  9. 9Two-stack window aggregation: keep FIFO order under a monoid
  10. 10Persistent two-list queues: fork FIFO dispatch history
Storage details