The diagram represents a queue Abstract Data Type (ADT). The organisation of this queue may be summarised as follows: • The FrontOfQueue pointer points to the next data item to be removed. • The EndOfQueue pointer points to the last data item added. [Figure showing Queue with elements D3, D4, D1, D2, D5 and pointers FrontOfQueue and EndOfQueue] The queue is implemented using three variables and a 1D array of eight elements as shown. The variable NumItems stores the number of items in the queue. The pointer variables store indices (index numbers) of the array.

1. (a)Complete the diagram to represent the state of the queue as shown above. Index 1 2 3 4 5 6 7 8 Array Variable FrontOfQueue EndOfQueue NumItems 5[3]
2. (b)A module AddTo() will add a value to the queue by manipulating the array and variables in part (a). The queue implementation is circular. When pointers reach the end of the queue, they will 'wrap around' to the beginning. Before a value can be added to the queue, it is necessary to check the queue is not full. The algorithm to add a value to the queue is expressed in six steps. Complete the steps. 1. If NumItems ................................ then jump to step 6. 2. Increment ................................ 3. If .................................... then set EndOfQueue to ................................ 4. Increment ................................ 5. Set the ................................ at the index stored in ................................ to the ................................ being added. 6. Stop.[6]

This question uses a diagram from the original paper, which isn't shown here. Open the full paper from the past papers archive to see it.