Dec1999 JP219 : Java Programming (Question 2)Suggested Solutions

(a)

One of the most important features of object oriented programming languages is the ability to design abstract data types .

Briefly explain the difference between an abstract data type and a primitive data type .
•An abstract data type is one where the the implementation of a data type is hidden behind its interface;(1 mark)
•A primitive data type is one which is native (built in)to the language.(1 mark)

[2]

(b)

You are required to implement a Queue abstract data type.

(i)Define a class,Queue ,which contains the following member variables:
•A protected statically sized array of 100 integers,called DataList ;
•A boolean variable Empty ,which is used to indicate if the queue is empty;
•Two iterators Front and Back ,which can be used to hold the array indexes of the front and back of the queue. [3 marks

class Queue {

protected int [100 ]DataList;
int front,back;
boolean Empty;

}

And the following marking scheme should be used:
•A correct array declaration;(1 mark)
•A correct Empty declaration;(1 mark)
•A correct front and back declaration;(1 mark)

(ii)Write a constructor method for your class,which will initialise every element of the DataList to zero,initialise the Front and Back iterators to zero,and initialise the Empty variable to indicate an empty queue.[3 marks ]
A sample definition of the constructor method follows:

Queue(){

Front=Back=0;

for(i=0;i<100;i++){
DataList [i ]=0;
}

}

And the following marking scheme should be used:
•Correctly initialising front and back ;(1 mark)
•A correct iteration statement,correctly bound by the array size;(1 mark)
•Initialising the array element on each iteration.(1 mark)

(iii)Write a method,called PeekHead ,the signature of which is given below,which is a member of your Queue class.The method should return the data element at the front of the queue,without removing the element,and return zero if the queue is empty.
int PeekHead(); [3 marks ]
A sample definition of PeekHead follows:

int PeekHead(){

if(!Empty)

return DataList [front ];

else

return 0;

}

And the following marking scheme should be used:
•A correctly structured conditional statement;(1 mark)
•Testing the non empty condition using Empty ;(1 mark)
•Returning the correctly indexed array element;(1 mark)

(iv)Write a method,called Add ,the signature of which is given below,which is a member of your Queue class.The method should add the element x to the Back of the queue if there is space,whilst ensuring that the Back iterator is correctly positioned.You should assume that there will always be space in the array for the element to be added.[4 marks ]
void Add(int x);
A sample definition of Add follows:

public void Add(int x){

if(Empty){

DataList [0 ]=x;
front=Back=0;
empty=False;

}else {

DataList [Back ]=x;
Back++;

}

}

And the following marking scheme should be used:
•A suitable conditional expression testing the Empty condition;(1 mark)
•Adding the item to the correct position in the array;(1 mark)
•Updating the iterators;(1 mark)
•Updating the Empty indicator if required.(1 mark)

[13]