Trace lab in Queues and Fair Scheduling

Mission

Process enqueue and dequeue commands and report removals.

Learning outcome: Trace FIFO command execution

Correctness contract

Invariant: Dequeue returns the oldest live item while preserving the relative order of all others.

Required technique: Use FIFO enqueue/dequeue operations and define empty dequeue as the literal EMPTY.

Complexity target: time O(commands); space O(n).

Input and output

Input: An operation count q followed by q commands; enq has one integer argument and deq has none. Whitespace may be spaces or line breaks.

Output: Print each dequeue result in order, using EMPTY for underflow, separated by single spaces. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• The stream contains exactly the declared number of complete commands.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Use FIFO enqueue/dequeue operations and define empty dequeue as the literal EMPTY.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

5 enq 1 enq 2 deq enq 3 deq

Sample output

1 2

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Enqueue joins the rear and dequeue removes the oldest live value; an empty dequeue produces EMPTY. Input `5 enq 1 enq 2 deq enq 3 deq` therefore produces `1 2`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.