The diagram below represents a queue Abstract Data Type (ADT) that can hold a maximum of eight items. The operation of this queue may be summarised as follows: • The front of queue pointer points to the next item to be removed. • The end of queue pointer points to the last item added. • The queue is circular so that empty storage elements can be reused. 0 Frog ← Front of queue pointer 1 Cat 2 Fish 3 Elk ← End of queue pointer 4 5 6 7 Describe how “Octopus" is added to the given queue.

1. (a)(i)The diagram below represents a queue Abstract Data Type (ADT) that can hold a maximum of eight items. The operation of this queue may be summarised as follows: • The front of queue pointer points to the next item to be removed. • The end of queue pointer points to the last item added. • The queue is circular so that empty storage elements can be reused. 0 Frog ← Front of queue pointer 1 Cat 2 Fish 3 Elk ← End of queue pointer 4 5 6 7 Describe how “Octopus" is added to the given queue.[2]
2. (a)(ii)Describe how the next item in the given queue is removed and stored in the variable AnimalName.[2]
3. (a)(iii)Describe the state of the queue when the front of queue and the end of queue pointers have the same value.[1]
4. (b)(i)Some operations are carried out on the original queue given in part (a). The current state of the queue is: 0 Frog 1 Cat 2 Fish 3 Elk 4 5 6 7 Complete the diagram to show the state of the queue after the following operations: Add "Wasp", "Bee” and “Mouse”, and then remove two data items.[3]
5. (b)(ii)The state of the queue after other operations are carried out is shown: 0 Frog 1 Cat 2 Fish 3 Elk ← Front of queue pointer 4 Wasp 5 Bee 6 Mouse ← End of queue pointer 7 Ant Complete the following diagram to show the state of the queue after the following operations: Remove one item, and then add "Dolphin" and "Shark”. 0 1 2 3 4 5 6 7[2]
6. (c)The queue is implemented using a 1D array. Describe the algorithm that should be used to modify the end of queue pointer when adding an item to the queue. Your algorithm should detect any potential error conditions.[3]

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.