December 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 3

Total Marks: 15 Marks

• Question 1
• Question 2
• Question 4
• Question 5
• Cover Page

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 3

You are to implement a system which will manage patients in a doctor ’s waiting room. When a patient arrives in the waiting room,a record is entered in a queue which contains the patient ’s name,the order number in which they arrived in the waiting room, and their condition,which can take one of the following values: trivial , concerning , or critical . The following data type is used to store this information:

Briefly explain what is meant by a Circular Queue .

A Circular Queue is one where

•The rear of the queue can loop back round;(1 mark)

•So the rear of the queue can come back to the front.(1 mark)

[2]

Write a procedure, called AddPatient , the signature of which is given below,which takes a queue of patients and a new patient record, and adds the new record to the patient queue.The order number associated with a given patient is one greater than the order number associated with the previous patient.You may use the standard queue function EmptyQueue ,the signature of which is given above.

PROCEDURE AddPatient(VAR PatientQueue :Queue, Data :
Patient);

A sample definition of AddPatient follows:

PROCEDURE AddPatient(VAR PatientQueue : Queue, Data : Patient);
VAR NewNode : NodePtr;
BEGIN
       New(NewNode);
       NewNode ˆ.Data:= Data;
       Data.OrderNumber:=PatientQueue ˆ.Rear.Data.OrderNumber + 1;
       IF NOT EmptyQueue(PatientQueue) THEN
           PatientQueue.Rear ˆ.Next:= NewNode
       ELSE
           PatientQueue.Front:= NewNode;
       PatientQueue.Rear:= NewNode;
END;{ AddPatient }

The following marking scheme should be used:

•Initialising the OrderNumber of the node passed in;(1 mark)

•By correctly accessing and incrementing the value of the OrderNumber at the tail of the list.(1 mark)

•Allocating a new node to be added to the list;(1 mark)
•And initialising it with the values of the patient data passed in;
(1 mark)

•Correctly updating the Next pointer in the entry at the rear of the queue of the queue based on an IsEmpty condition;(1 mark)

•Correctly updating the Front and Rear queue pointers;(1 mark)

[6]

Write a function,called Emergencies ,the signature of which is given below, which will take as a parameter the patient queue, and will return a second queue which contains all of the patients whose conditions are Critical .These patients should be removed from the original queue.You can assume the standard queue function, RemovePatient , which removes and returns the patient at the head of the queue.

FUNCTION Emergencies(VAR PatientQueue : Queue): Queue;

A sample definition of Emergencies follows:

FUNCTION Emergencies(VAR PatientQueue : Queue): Queue;
VAR CurrentPatient : Patient;
VAR AQueue,BQueue : Queue;
BEGIN
      AQueue:= NULL;
      BQueue:= NULL;
      WHILE (NOT EmptyQueue(PatientQueue)) DO
      BEGIN
            CurrentPatient:= RemovePatient(PatientQueue);
            IF(CurrentPatient.Condition = Critical) THEN
                 AddPatient(AQueue, CurrentPatient)
            ELSE
                 AddPatient(BQueue, CurrentPatient);
      END;
      PatientQueue:= BQueue;
      Emergencies:= AQueue;
END;{ Emergencies }

The following marking scheme should be used:

•Declaring temporary variables for the current patient and both temporary queues;(1 mark)

•Declaring a loop structure,bounded by the non empty queue condition;(1 mark)

•Removing the head of the queue with RemovePatient and assigning it to the temporary CurrentPatient variable;(1 mark)

•Adding it to one queue with AddQueue if the condition is Critical ;(1 mark)

•And the other if it is not;(1 mark)

•Assigning the temporary queue containing non-critical patients to the reference parameter variable;(1 mark)

•And returning the temporary queue containing critical patients.
(1 mark)

[7]