Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 4 / b / Solution

A fixed-size array cannot implement unbounded successful insertion. Either specify a bounded double-ended queue with an extra not-full insertion precondition, or retain the unbounded interface and specify a possible full-capacity failure. Silently overwriting an endpoint would change the stated behavior. Here use the bounded contract, with a fixed positive capacity MAX and abstract state $|s|\le MAX$. Both additions require $|s|<MAX$; the other postconditions remain unchanged. The class declaration in part (c) is interpreted as implementing this explicitly revised contract, rather than as a behavioral subtype of the unrestricted contract in part (a).

The concrete state is an array a of length MAX, a first-position index head, and an occupied-entry count size. Its representation invariant isThe abstraction function is $s(k)=a((head+k)\mathrm{mod}MAX)$ for $0\le k<size$. Unoccupied slots are unconstrained. Storing size distinguishes empty and full states even though their two circular endpoint positions coincide. MAX=1 is valid. Using a circular buffer avoids shifting entries and makes every endpoint operation constant time.