Ahead of the Stack

Extended Response12 MarksPremium

At the moment marathon runners cross the finishing line of a race, their names are added to a stack called RUNNERS.

For example, a diagram of RUNNERS below indicates “Ellie” has finished first and “Jessie” last. “Jessie” is at the top of the RUNNERS stack.

(a).

Using pseudocode, construct an efficient procedure that will search the stack RUNNERS for a name given via standard input. Once the given name is found, output the finishing place of the runner specified as a number. If a name is not found then the procedure should output the message "Runner not found".
Assume all names are unique, the number of elements in RUNNERS is unknown and RUNNERS may be emptied during the search process.

[6]For example, given an input string of "Joel" the procedure will output the number 2 to indicate Joel finished in 2nd place.

(b).

Outline why the use of a queue would make this algorithm simpler and more efficient than using a stack.

[2]In the same way as RUNNERS saves each runner's name, another stack called TIMES saves each runner's finishing time as they cross the finish line.

(c).

The results of a particular competition where 101 runners successfully finish a race are held in RUNNERS and TIMES. Given an empty 101x2 (row x column) 2D array called RESULTS, write pseudocode such that the first column contains the names of all those runners who finished the race and the second column contains their respective times in ascending rank order.

[3]For example, RESULTS[7][1] should contain the time of the runner who finished in 94th place, that is, having only ran faster than seven people (eighth last).

(d).

Using RESULTS, state the single line of pseudocode that represents the name of the runner with the median finishing time.

[1]