April 1999
AP207: ADVANCED PROGRAMMING TECHNIQUES

QUESTION 2

Total Marks: 20 Marks

 Click here to access other questions

GRADE B
Sample student's solutions are indicated in green.
Return to Question 2

 
(a) Identify and explain the difference between a stack and a queue. [2]
Stack is LIFO.
Queue is FIFO.

 
(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 occurred;
  • 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]
procedure popQueue(Var queue: queuetype; var datum :integer);
var temp : nodetype;
Begin
        is isempty(queue.front) = true then
              error
        else
              begin
                   temp : = queue.front;
                   datum:=temp^.data;
                   queue.front :=temp^.next;
                  dispose(temp);
               if isempty(queue.front) = true
                     then queue.rear := nil
                   end;
             end;
end;

 
(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]
procedure addQueue(Var queue: queuetype; datum :integer);
var temp : nodetype;
Begin
     new(temp);
     temp^.data :=datum;
     temp^.next = nil;
    queue.rear^.next:=temp;
    queue.rear :=temp;
    if queue.front = nil then
          queue.front := temp;
end;

 
(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]
procedure NpopQueue(Var queue:queuetype; Var N:Integer; Bar datum:Integer);
var temp : node type;
count : integer;
no : integer;
Begin
    for (count = 1;  count =< N) do
       Begin
             popQueue(queue.datum);
             count :=count + 1;
             end;
           no:= 0;
           temp : = queue.front;
           while not isempty (temp)
          Begin temp : = temp^.next;
               no:= not 1;
         end;
           N : = no;
end;

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

PROCEDURE reverseQueue(VAR queue : queueType);

 [5]
procedure reverseQueue(var queue:queuetype);
var temp : queuetype;
dummy : integer;
Begin
    if not isempty(queue) then
         Begin
         popQueue (queue, dummy);
         reversequeue (queue);
         addQueue (temp, dummy);
         end

Assumed temp has been initialise Queue(temp).