Q$1($a$)$

Jo has represented each stack of tyres as a stack ADT using the Linked Stack

implementation $($see $7\mathrm{.}1\mathrm{.}3).$ Each element in the stack is an integer representing the tyre diameter in millimetres. The whole shop is represented as a dictionary of stacks, with the stack being the value and the key being one or more uppercase letters which Jo uses to identify the stack. The following code creates two stacks of tyres $($STACK$\_$A and STACK$\_$B$)$ and adds some sample tyres to them.

tyre$\_$shop $=$ diet$()$

tyre$\_$shop$[\text{'}$STACK$\_$A$\text{'}]=$ LinkedStack$()$

tyre$\_$shop$[\text{'}$STACK$\_$A$\text{'}].$push$(330)$

tyre$\_$shop$[\text{'}$STACK$\_$A$\text{'}].$push$(310)$

tyre$\_$shop$[\text{'}$STACK$\_$B$\text{'}]=$ LinkedStack$()$

tyre$\_$shop$[\text{'}$STACK$\_$B$\text{'}].$push$(410)$

The results of this are illustrated below:

Stack A: Stack B:

$310$mm tyre

$330$mm tyre $410$mm tyre

When a new tyre is received into stock, Jo needs to identify the most suitable of the existing stacks to put it on$.$ Jo does this by applying two rules:

$1.$ The diameter of the top tyre must be as close as possible to the new tyre without being smaller than the new tyre.

$2.$ The candidate stack must be as short as possible.

Rule $1$ takes priority over rule $2.$

Example:

$$ Stack C contains $3$ tyres, the top one being $200$mm$.$

$$ Stack D contains $2$ tyres, the top one being $300$mm$.$

$$ Stack E contains $4$ tyres, the top one being $200$mm$.$

Note this example discounts stacks A and B from the prior example. If the new tyre was $190$mm$,$ Jo would choose stack C since:

$$ The top tyre on the stack is the closest size to the new tyre without being smaller

than it$.$

$$ It is shorter than the other potential stack, E$.$

$$ Stack D is discounted as$,$ although it is shorter than the other stacks, it does not

meet the criteria of rule $1.$ Note that if stack E were only $3$ tyres high, then Jo's method would give both stack C and stack E as options.

Q$1($a$)($i$)$ Outline an algorithm in English which will return a list of the stack keys which are suitable candidates for the new tyre to be placed on$,$ according to Jo's rules above.