Aug 1997 AP207: Advanced Programming Techniques (Question 5) Suggested Solutions

5.	(a) Identify and explain the difference between a stack and queue abstract data-type.			[2]
	A stack is a last-in first out data structure,			[1]
	whereas a queue is a first in first out			[1]
	[2 marks]

	(b) Given the following type definition for a queue:

		Where Front points to the first element in the queue and Rear points to the last element added to the queue. It is assumed that the Next field of a Node points from newer elements in the queue to older ones.
		(i) Write a function sizeQueue that takes a queue of type QueueType as its argument, and returns an integer that identifies the number of elements in the queue.		[5]
		A definition of sizeQueue follows:

			one mark for a correct function definition.
			one mark for creating a temporary variable of type NodeType, and assigning it to queue.Front.
			one mark for iterating down the queue, until the end of the queue is found.
			one mark for incrementing a size counter whilst walking down the queue.
			one mark for correct program structure (semicolons and grouping)
		do not deduct marks for trivial syntactic errors when marking the above points.
		[5 marks]
		(ii) Write a procedure enQueue that takes two arguments: (i) a queue of type QueueType; and (ii) an integer to be added to the queue. The effect of the procedure is to alter the queue argument by adding the integer parameter to the queue.		[6]
		A definition of enQueue follows:

			one mark for a correct function definition.
			one mark for allocating a new node type with New.
			one mark for assigning todata to Data field of the new node type.
			one mark for assigning the old rear of the queue to the Next field of the new node type.
			one mark for updating the Rear field of queue to the new node type.
			one mark for checking if the original queue was empty, so that a reference from the front of the queue to the new node can be made.
			do not deduct marks for trivial syntactic errors when marking the above points.
		[6 marks]
		(iii) Write a procedure deQueue that takes a non-empty queue of type QueueType as its argument. The effect of the procedure is to alter the queue by removing an element.		[7]
		A definition of deQueue follows:

			one mark for a correct procedure definition.
			one mark for defining a temporary variable of type Nodetype, and assigning it to the element at the front of the queue.
			one mark for iterating down the queue until the front of the queue is found.
			two marks for ensuring that after iterating down to the front of the queue, that a handle to the second oldest element in the queue is recorded.
			one mark for assigning the second oldest element in the queue to the field that represents the front of the queue.
			one mark for assigning the Rear field of the queue to Nil if there was only one element in the queue originally.
			do not deduct marks for trivial syntactic errors when marking the above points.
		[7 marks]