Pseudocode is to be written to implement a queue Abstract Data Type (ADT) with items of the string data type. This will be implemented using the information in the table. Identifier Data type Description FrontPointer INTEGER points to the start of the queue RearPointer INTEGER points to the end of the queue Length INTEGER the current size of the queue Queue STRING 1D array to implement the queue A constant, with identifier MaxSize, limits the size of the queue to 60 items.

Mark scheme

Marking points from the official mark scheme (May/June 2023). The mark or mark type is shown in brackets.

1. [3] (a) One mark per mark point (Max 3) • correctly defined constant • correctly defined array • three correctly defined integers CONSTANT MaxSize = 60 DECLARE Queue : ARRAY[1:60] OF STRING // DECLARE Queue : ARRAY[0:59] OF STRING // DECLARE Queue : ARRAY[1:MaxSize] OF STRING // DECLARE Queue : ARRAY[0:MaxSize – 1] OF STRING DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER
2. [4] (b) One mark for each correctly completed line (Max 4) FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING IF Length > 0 THEN Item ← Queue[FrontPointer] FrontPointer ← FrontPointer + 1 Length ← Length – 1 IF Length = 0 THEN CALL Initialise // procedure to reset the pointers ELSE IF FrontPointer > MaxSize THEN FrontPointer ← 1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty - error!" Item ← "" ENDIF RETURN Item ENDFUNCTION
3. [4] (c) One mark per mark point (Max 4) MP1 (Two stacks are required) so that the second stack can reverse the order of the first stack. MP2 Stack 1 operates as the queue with the newest elements at the bottom. Stack 2 is empty. MP3 To add an element, pop all the elements from stack 1 and push onto stack 2. MP4 Push the new element onto either stack. MP5 Pop all the elements of stack 2 back onto stack 1.