1 (a) 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
(i) Describe how “Octopus” is added to the given queue.
• EoQ pointer will move to point to location 4 // incremented EoQ (by 1)
• Data value "Octopus" will be stored in location pointed to be EoQ /location 4
(ii) Describe how the next item in the given queue is removed and stored in the variable
AnimalName.
• Value "Frog" // value pointed to by FoQ / location 0 is assigned to variable
AnimalName
• FoQ pointer will move to point to location 1 / point to "Cat" // incremented FoQ (by 1)
(iii) Describe the state of the queue when the front of queue and the end of queue pointers
have the same value.
There is only one data item in the queue
(b) Some operations are carried out on the original queue given in part (a).
(i) 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]
(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]
(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.
If incremented EoQ = FoQ then error condition: queue is full
Increment the EoQ
Manage wrap-around
2 (a) A program contains a 1D array DataItem with 100 elements.
State the one additional piece of information required before the array can be declared.
The data type (of the item to be stored)
(b) A programmer decides to implement a queue Abstract Data Type (ADT) in order to store
characters received from the keyboard. The queue will need to store at least 10 characters
and will be implemented using an array.
(i) Describe two operations that are typically required when implementing a queue.
State the check that must be carried out before each operation can be completed.
Operation: Add an item / Enqueue
Check: There are unused elements in the array // The queue is not full
Operation: Remove an item / Dequeue
Check: There are items in the array // The queue is not empty
(ii) Describe the declaration and initialisation of the variables and data structures used to
implement the queue.
Declare a (1D) array of size >= 10 of data type CHAR
Declare integer variable for FrontOfQueuePointer
Declare integer variable for EndOfQueuePointer
Initialise FrontOfQueuePointer and EndOfQueuePointer to represent an empty queue
Declare integer variable or NumberInQueue
Declare integer variable for SizeOfQueue to count / limit the max number of items allowed
// Reference to mechanism for defining 'wrap' of circular queue
Initialise SizeOfQueue // Initialise NumberInQueue
A program stores data in a text file. When data is read from the file, it is placed in a queue.
(a) The diagram below represents an Abstract Data Type (ADT) implementation of the queue.
Each data item is stored in a separate location in the data structure. During initial design, the
queue is limited to holding a maximum of 10 data items.
The operation of this queue may be summarised as follows:
• The Front of Queue Pointer points to the next data item to be removed.
• The End of Queue Pointer points to the last data item added.
• The queue is circular so that locations can be reused.
0
1
2
3
4
5 Red Front of Queue Pointer
6 Green
7 Blue
8 Pink End of Queue Pointer
9
(i) Describe how the data items Orange and Yellow are added to the queue shown in the
diagram.
Check that the queue is not full
EoQ pointer will move to point to location 9
Data item Orange will be stored in location referenced by EoQ pointer
EoQ pointer will move to point to location 0
Data item Yellow will be stored in location referenced by EoQ pointer
(ii) The following diagram shows the state of the queue after several operations have been
performed. All queue locations have been used at least once.
0 D4
1 D3 End of Queue Pointer
2 D27
3 D8
4 D33
5 D17 Front of Queue Pointer
6 D2
7 D1
8 D45
9 D60
State the number of data items in the queue.
(b) The design of the queue is completed and the number of locations is increased.
A function AddToQueue() has been written. It takes a string as a parameter and adds this to
the queue. The function will return TRUE if the string was added successfully.
A procedure FileToQueue() will add each line from the file to the queue. This procedure
will end when all lines have been added or when the queue is full.
Describe the algorithm for procedure FileToQueue().
Do not use pseudocode in your answer.
Open file in READ mode
Loop to EOF()// read / process all the lines in file
Loop will end when return value from AddToQueue() is FALSE / queue is full
Read a line from the file in a loop
Pass string to AddToQueue()// AddToQueue()is executed with
line as parameter
