Stacks and queues are both abstract data types. A stack uses a top-of-stack pointer to indicate the location of the last item added to the stack. A queue uses two pointers: • a front pointer to indicate the location of the next item to be removed from the queue • a rear pointer to indicate the location of the next item to be added to the queue. A queue can be used to reverse the items stored on a stack. For example, if a stack contains six items: Initial state of the stack: top-of-stack pointer item 6 item 5 item 4 item 3 item 2 item 1 Final state of the stack when the items have been reversed: top-of-stack pointer item 1 item 2 item 3 item 4 item 5 item 6 Describe how the queue could be used to reverse the items that are currently stored on the stack. Your description must include how the pointers are used in both the stack and queue. Assume: • The stack initially contains an unknown number of items. • The queue can store all the items currently stored on the stack. • The queue is initially empty.

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.