w-12-amortized-queue-via-stacks.yml · YAML

# Amortized queue via two stacks: chapter 4.4 worked example: LC 232.
# Animates the inbox/outbox composition so the lazy transfer fires
# visibly only when outbox is empty AND a serve-side op is requested.
# The credit-balance badge makes the amortized accounting visible:
# each push deposits one credit on its element; the deposited credits
# pay for the inbox->outbox transfer when peek/pop demands it.

id: w-12-amortized-queue-via-stacks
title: "Amortized queue via two stacks (LC 232)"
type: single-panel
level: 1
modes: [preset, edit]

caps:
  ops_count: { min: 1, max: 12 }
  values: { min: -99, max: 99 }
  combined_size: { min: 0, max: 12 }
  # Hard cap keeps every preset under the 30-step ceiling. The canonical
  # 5-op input renders in 6 steps; an alternating-stress preset (10 ops)
  # renders in roughly 15.

commands:
  - name: pushInbox
    payload: { value: 'integer' }
    description: "Push value onto inbox. Increment credit balance by 1."
  - name: transfer
    payload: { drained: 'integer' }
    description: "Outbox is empty; drain inbox into outbox. Each transferred element flips its visual position; credit balance pays for the work."
  - name: popOutbox
    payload: { value: 'integer' }
    description: "Pop top of outbox; this is the FIFO front."
  - name: peekOutbox
    payload: { value: 'integer' }
    description: "Read top of outbox without removing; this is the FIFO front."
  - name: queryEmpty
    payload: { value: 'boolean' }
    description: "Check whether both stacks are empty."

static_fallback:
  generator: jsdom
  output: site/static/widgets/w-12-amortized-queue-via-stacks-fallback.svg
  keyframes_used: [0, 2, 3, 4]
  # Four stills: empty state at start; both pushes done (inbox=[1,2]);
  # transfer fired by peek (outbox=[2,1], peek returned 1); after pop
  # (outbox=[2], pop returned 1).

panels:
  default:
    chapter: "4.4"
    label: "LC 232 inbox/outbox trace"
    canonical_input: |
      ops = ["push 1", "push 2", "peek", "pop", "empty"]
    presets:
      - id: canonical
        label: "Canonical (LC 232 problem-page example)"
        input: { ops: ["push 1", "push 2", "peek", "pop", "empty"] }
      - id: alternating-stress
        label: "Alternating push/pop (transfer fires every pop)"
        input: { ops: ["push 1", "pop", "push 2", "pop", "push 3", "pop"] }
      - id: many-pushes-one-pop
        label: "Many pushes, then one pop (single transfer of n)"
        input: { ops: ["push 1", "push 2", "push 3", "push 4", "push 5", "pop"] }
    n_steps: 6
    # Trace generated by hand-tracing the verified Python reference at
    # content/dsa/part-4-stack-queue-patterns/04-queue-from-stacks/lc-232/sol.py
    # against the canonical input. Re-running the reference produces an
    # identical (inbox, outbox, return-value) sequence.
    keyframes:
      - step: 0
        kind: init
        state: { inbox: [], outbox: [], ret: null, credit_balance: 0 }
        narration: "Initial state. Both stacks are empty; the credit balance is 0. The FIFO contents (none) read as outbox.reversed() ++ inbox."
      - step: 1
        kind: pushInbox
        payload: { value: 1 }
        state: { inbox: [1], outbox: [], ret: null, credit_balance: 1 }
        narration: "push(1). The element lands on inbox in O(1). One amortized credit is deposited on element 1; it will pay for the future transfer."
      - step: 2
        kind: pushInbox
        payload: { value: 2 }
        state: { inbox: [1, 2], outbox: [], ret: null, credit_balance: 2 }
        narration: "push(2). Inbox is now [1, 2] from bottom to top. Credit balance is 2; one credit per element waiting to be transferred."
      - step: 3
        kind: transfer
        payload: { drained: 2 }
        state: { inbox: [], outbox: [2, 1], ret: 1, credit_balance: 0 }
        narration: "peek triggers the transfer because outbox is empty. Inbox drains into outbox: pop 2 from inbox, push to outbox; pop 1 from inbox, push to outbox. The deposited credits pay for the four stack ops. Outbox is now [2, 1] from bottom to top; the FIFO front is the top of outbox, which is 1. peek returns 1."
      - step: 4
        kind: popOutbox
        payload: { value: 1 }
        state: { inbox: [], outbox: [2], ret: 1, credit_balance: 0 }
        narration: "pop. Outbox is non-empty so no transfer fires. The top of outbox is 1; pop returns it. Outbox is now [2]; the FIFO front (and only element) is 2."
      - step: 5
        kind: queryEmpty
        payload: { value: false }
        state: { inbox: [], outbox: [2], ret: false, credit_balance: 0 }
        narration: "empty. Inbox is empty but outbox holds 2; the queue is not empty. Returns false."

notes: |
  The widget surfaces three things the chapter prose alone cannot:
  (1) the lazy invariant - transfer fires only at step 3, on the first
  serve-side op after outbox went empty, not on every push;
  (2) the order reversal during transfer - inbox [1, 2] becomes outbox
  [2, 1], so the FIFO front (1) ends up on top of outbox;
  (3) the credit balance dynamics - balance climbs on pushes, collapses
  to 0 when transfer cashes the credits, and stays at 0 on cheap
  outbox-only pops.

  Reduced-motion fallback uses keyframes 0, 2, 3, 4 (four stills:
  empty, both pushed, transfer fired, after pop). Keyframe 3 is the
  pedagogically critical state and is always included.