10.4. Introduction to Abstract Data Types (ADT)
A subsection of Computer Science, 9618, through 10. Data Types and Structures
Listing 3 of 3 questions
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. Write the pseudocode to declare MaxSize, FrontPointer, RearPointer, Length and Queue. Complete the following pseudocode for the function Dequeue to remove the front item from the queue. FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING > 0 THEN Item ← IF Length = 0 THEN CALL Initialise // reset the pointers ELSE IF FrontPointer > MaxSize THEN ← 1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty – error!" Item ← "" ENDIF RETURN Item ENDFUNCTION Explain how a new element can be added to the queue if it is implemented using two stacks.
9618_s23_qp_31
THEORY
2023
Paper 3, Variant 1
View
The pseudocode shown represents a queue Abstract Data Type (ADT) with procedures for initialisation and to add new items. It is incomplete. CONSTANT MaxLength = 50 DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER DECLARE Queue : ARRAY[0 : MaxLength – 1] OF STRING // initialisation of queue PROCEDURE Initialise FrontPointer ‑1 ENDPROCEDURE // adding a new item to the queue PROCEDURE Enqueue(NewItem : STRING) IF THEN RearPointer IF RearPointer > MaxLength – 1 THEN RearPointer ENDIF Length Length + 1 ENDIF ENDPROCEDURE Study the pseudocode and insert the identifiers to complete this table. Identifier Data type Description STRING An array to store the contents of the queue. INTEGER Points to the last item of the queue. INTEGER Indicates the number of items in the queue. INTEGER Points to the first item of the queue. Complete the given pseudocode. Explain the reasons why a queue ADT works better than a stack ADT in organising print jobs.
9618_s23_qp_32
THEORY
2023
Paper 3, Variant 2
View
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. Write the pseudocode to declare MaxSize, FrontPointer, RearPointer, Length and Queue. Complete the following pseudocode for the function Dequeue to remove the front item from the queue. FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING > 0 THEN Item ← IF Length = 0 THEN CALL Initialise // reset the pointers ELSE IF FrontPointer > MaxSize THEN ← 1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty – error!" Item ← "" ENDIF RETURN Item ENDFUNCTION Explain how a new element can be added to the queue if it is implemented using two stacks.
9618_s23_qp_33
THEORY
2023
Paper 3, Variant 3
View
Questions Discovered
3