April 1999
AP207: ADVANCED PROGRAMMING TECHNIQUES

QUESTION 2

Total Marks: 20 Marks

 Click here to access other questions

Click to access
SAMPLE STUDENT'S SOLUTIONS
for Question 2

 
(a) Identify and explain the difference between a stack and a queue.

 

 [2]
(b) Assume the following definition of a queue data type:

TYPE
   NodeType = ^Node;
   Node     = RECORD
                 Next : NodeType;
                 Data : Integer;
              END;

   QueueType = RECORD
                  Front : NodeType;
                  Rear   : NodeType;
               END;

Here, Front points to the first element in the queue, Rear points to the last element added to the queue, and the Next field of a node points from the older element in the queue to the next newer element in the queue.

Furthermore, you can assume the existence of the following functions and procedures:

  • PROCEDURE Error;
    Can be called when an error has occured;
  • PROCEDURE initialiseQueue(VAR queue : QueueType);
    Can be called to initialise the queue queue;
  • FUNCTION isEmpty (queue: QueueType) : BOOLEAN;
    Can be called to test if the queue queue is empty. Returns TRUE if the queue is empty, FALSE otherwise

 
(i) Write a procedure popQueue - with the prototype given below -   which will remove and return the oldest element in a queue. You should call the procedure Error if there is not an item in the queue to be popped.

PROCEDURE popQueue(VAR queue : QueueType;
VAR datum : Integer);

 

 [4]
(ii) Write a procedure addQueue - with the prototype given below - which will add an element to a queue.

PROCEDURE addQueue(Var queue: QueueType;
datum : Integer);

 

 [4]
(iii) Write a procedure NpopQueue - with the prototype given below - which will attempt to remove N items from a queue, and return the N'th item. When the procedure returns, the parameter N should hold the value of the number of remaining items to be popped.

PROCEDURE NpopQueue(VAR queue : QueueType; VAR N:Integer;VAR datum : Integer);

 

 [5]
(iv) Write a recursive procedure reverseQueue - with the prototype given below - which will reverse the queue queue.

PROCEDURE reverseQueue(VAR queue : queueType);

 [5]