/solve-maths-mem · foundations
Coding a queue
CLRS Exercise 10.1-4, in Python that runs in your browser: “Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue” [CLRS, 3rd ed., §10.1].
CLRS's queue
(array queue, one slot left free) [CLRS, 3rd ed., §10.1]
$$Q[0],\dots,Q[n-1];\qquad \mathrm{empty}\iff \mathrm{head}=\mathrm{tail};\qquad \mathrm{full}\iff(\mathrm{tail}+1)\bmod n=\mathrm{head};\qquad \#\text{items}=(\mathrm{tail}-\mathrm{head})\bmod n\le n-1.$$CLRS index slots from 1; here from 0, as in Python. \(n\) is the capacity \(c\) of Foundations, and tail is its \(t\).
(how many fit?) predict
With \(n=6\), how many enqueues on a new queue succeed before an overflow?
5. A sixth item would make tail = head, which already means empty (Foundations). Test 2 below checks this with \(n=4\): three enqueues, then Overflow.
Exercise 10.1-4
(detect overflow and underflow) code
Fill in the two TODOs so that every test passes. Raise Overflow() or Underflow(); a refused operation must leave the queue unchanged.
All \(n\) slots
(keep the size instead of tail) transfer
Store size (\(\ell\) on Foundations) instead of tail, so that all \(n\) slots hold items. The same tests run, now with \(n\) items allowed.
How interactive coding exercises are designed
| design | what the learner gets | here |
|---|---|---|
| automatic assessment by tests [Ihantola et al.] | which test fails | 5 tests, one per mistake |
| feedback on the mistake [Keuning et al.] | where it fails and what was expected | step, expected, got |
| program visualization [Guo; Sorva et al.] | the program's state after each step | your array, head and tail, drawn |
| predict before running [Sentance et al.] | a prediction to check | |
| start from given code: use, modify, create [Lee et al.; Parsons & Haden] | less to write at first | starter code with TODOs, then from a skeleton |
| Python in the browser [Miller & Ranum; Pyodide] | no installation | Pyodide in a Web Worker, stopped after 6 s |
| random tests against a model [Claessen & Hughes] | cases nobody wrote by hand | test 5: 200 random operations |
Your code is saved in this browser only. Python (Pyodide v0.26.4) loads from cdn.jsdelivr.net on the first run.