Dec 1998 AP207: Advanced Programming Techniques (Question 3)

(a)	Define and explain the properties of a queue abstract data type. In particular, identify any error conditions that may be raised when manipulating a queue.	[3]
	Properties of a queue A queue is a first-in first-out data structure. data is added to the rear of the queue. data is taken from the front of the queue. Data is only accessible from the front of the queue. it is an error to deQueue from an empty queue. one mark for each point, up to a maximum of three marks.
(b)	Identify and explain the differences between a dynamic and a static implementation of a queue.	[2]
	Differences between a dynamic and static queue. *A dynamic queue can grow* during program execution, whereas static implementation stays the same size. A dynamic queue can shrink during program execution, whereas static implementation stays the same size. A dynamic implementation will use pointers to heap allocated memory, whereas a static queue will use an array and array subscripting. Dynamic queues only use the storage that is required, whereas a static queue may not and lead to wasted memory. A dynamic queue requires little arrangement for insertion and deletion, whereas a static queue may** one mark for each point, up to a maximum of two marks.
(c)	This question is concerned with the implementation of a doctors waiting room queuing system. On entry to the clinic, a patient receives a patient-number that identifies their position within the queue. The following data-type is used as a representation of the clinic's queue: TYPE Patient = RECORD name: String[20]; id: Integer; END NodeType = ^Node; Node = RECORD next: NodeType; data: Patient; END; QueueType = RECORD front: NodeType; rear: NodeType; END; where front points to the first element in the queue; rear pointers to the last element added to the queue; and the next field of a Node points from older elements in the queue to newer ones. i.e., Write a function MaxPatientId, that has the type shown below, that returns the largest patient identifier (i.e., the id field of the type Patient) within a queue. If the queue is empty, the function should return zero. FUNCTION MaxPatientId(queue: QueueType):Integer;	[4]
	A definition of MaxPatientId follows: FUNCTION MaxPatientId(queue:QueueType):Integer; VAR ptr: NodeType; BEGIN MaxPatientId := 0; ptr := queue^.front; WHILE (ptr <> NIL) DO BEGIN IF (ptr^.data.id > MaxPatientId) THEN MaxPatientID := ptr^.data.id; ptr := ptr->next; END END one mark for returning zero if the queue is empty. one mark for iterating down the queue one mark for updating the return parameter if a larger patient id is found. one mark for correct pointer/structure dereferencing.
(d)	If the queue shown above were passed to the procedure unknown with the string "John", then the state of the queue would be changed. Re-draw the queue to show the effect of calling the procedure on the queue. PROCEDURE unknown(VAR queue: QueueType; name: String[20]); VAR temp: NodeType; BEGIN New(temp); temp^.data.name := name; temp^.data.id := MaxPatientId(queue) + 1; temp^.next := Nil; queue.rear^.next := temp; queue.rear := temp; END;	[2]
	A picture of the updated queue: one mark adding the entry of the rear if the queue. one mark for having a patient of 5 for the new element
(e)	The procedure unknown is not well-defined if an empty queue is passed as an argument. Rewrite the procedure so that it can take either an empty or non-empty queue.	[3]
	PROCEDURE unknown(VAR queue: QueueType; newp: String[20]); VAR temp: NodeType; BEGIN New(temp); temp^.data.name := name; temp^.data.id := MaxPatientID(queue) + 1; temp^.next := Nil; IF queue.front = Nil THEN queue.front := temp; ELSE queue.rear^.next := temp; queue.rear := temp; END; one mark for checking if the front is NIL. one mark for updating the front pointer one mark for updating rear^.next only if rear is non-empty.
(f)	Write a function deQueue, with type shown below, that returns True and copies the patient information from the front of the queue into the variable x if the queue if non-empty; and returns False otherwise. FUNCTION deQueue(queue:QueueType; VAR x: Patient):Boolean;	[6]
	A definition of deQueue follows: PROCEDURE deQueue(queue: QueueType; VAR x:Patient):Boolean; VAR temp: NodeType; BEGIN IF (queue.front = Nil) THEN deQueue : = False; ELSE BEGIN deQueue := True; temp := queue.front; x := temp^.data; IF (temp^.next = Nil) THEN BEGIN queue.front := Nil; queue.rear := Nil; END ELSE queue.front := temp^.next; Dispose(temp); END END one mark for returning False if the queue is empty. one mark for returning True is the queue is non-empty. one mark for updating x with the name from the front of the queue. one mark for updating the front and back of the queue with Nil if the queue only contains one element. one mark for updating the front of the queue to point to the second element in the queue. one mark for disposing of the front element.