Computer Science (AS & A Level) · May / June 2025 · Paper 21 · Question 5

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 Final state of the stack when the items have been reversed: top-of-stack pointer 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. item 6 item 5 item 4 item 3 item 2 item 1 item 1 item 2 item 3 item 4 item 5 item 6 11 [7]

Read automatically from the paper; the printed page above is exact.