Dec1999 OP216 : Object Oriented Programming (Question 2)Suggested Solutions

template <class T> class Queue { private:
	//Some private declarations
public:
	Queue();
	void AddToBack(T);	//Add an item to the end of the queue.
	T RemoveFromFront();	//Remove an item from the front of the queue.
	int Length();	//Return the length of the queue.
	int Empty();	//Return 1 if the queue is empty,otherwise return 0.
};

(a)

Template classes are an example of polymorphism .Explain what is meant by polymorphism .

Polymorphism
•allows different data types to be used where others are expected;(1 mark)
•or allows functions to perform similar logical tasks where implementations are different.(1 mark)

[2]

(b)

Declare a pointer to an object of type Queue ,with an integer template type.

Queue*MyQueue;

[1]

(c)

Show how this object can be allocated using the new operator.

MyQueue=new Queue();[1 mark ]

[1]

(d)

Write a polymorphic iterative function,called RemoveItemN ,the signature of which is given below,which takes a reference to a queue Q and an integer x ,and will remove and return the x ’th item from the queue Q .The rest of the queue should remain unchanged.You should assume that counting queue elements starts at zero,and you may use the functions which have been declared in the class Queue .

template <class T>
T RemoveItemN(Queue<T>&Q);

A sample definition of RemoveItemN follows:

template <class T>
T RemoveItemN(Queue<T>\&Q,int x)
{
	T element;
	Queue<T>P;
	int counter=0;
	while(!Q.Empty()){
		if(counter!=x)
			P.AddToBack(Q.RemoveFromFront());

		else
			element=Q.RemoveFromFront();
	}
	=P;
	return element;
}

And the following marking scheme should be used:
•Declaring a local temporary variable for the element,and one for a local queue
copy;(1 mark)
•Declaring a suitable iterative structure,guarded with an empty test on the queue
or by queue length;(1 mark)
•Adding the element removed from the original queue to the new queue when the
test condition is not true;(1 mark)
•Storing the element removed from the queue when the test condition is true;
(1 mark)
•Equating the old queue to the resultant new queue;(1 mark)
•Returning the temporarily stored element.

[6]

(e)

Write a polymorphic recursive function,called Reverse ,the signature of which is given below,which takes a reference to a queue Q and reverses the queue.To reverse a queue,items should be recursively removed from the queue,and then added to the queue as the recursive stack is unwound.You may use the functions which have been declared in the class Queue .

template <class T>
T Reverse(Queue<T>&Q);

A sample definition of Reverse follows:

template <class T>
void Reverse(Queue<T>&Q)
{
	T element;
	if(!Q.Empty()){
	while(!Q.Empty()){
		element=Q.RemoveFromFront();
		Reverse(Q);
		Q.AddToBack(element);
	}
}

And the following marking scheme should be used:
•Declaring a local temporary variable of the template type to hold the removed
element;(1 mark)
•Guarding the recursion with an empty test on the queue;(1 mark)
•Removing,and storing the element at the front of the queue;(1 mark)
•Then recursing with the remainder of the queue;(1 mark)
•Adding the element back to the queue after the recursive call;(1 mark)

[5]