December 1998
AP207: ADVANCED PROGRAMMING TECHNIQUES

QUESTION 3

Total Marks: 20 Marks

 Click here to access other questions

Click to access
SUGGESTED SOLUTIONS
for 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]
(b) Identify and explain the differences between a dynamic and a static implementation of a queue.

 

 [2]
(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.,

pic2.gif (2243 bytes)

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]
(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]
(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]
(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]